BGN: Identifying Influential Nodes in Complex Networks via Backward Generating Networks

Identifying influential nodes in complex networks is of great significance. During recent decades, numerous methods regarding influential nodes identification or important nodes ranking have been developed. However, most of the existing methods either have low ranking accuracy or cannot be extended to large-scale networks. To address these issues, we propose a novel greedy algorithm named backward generating networks (BGNs) to identify influential nodes more accurately and more efficiently. BGN seeks to get the order of importance of nodes by minimizing the unique robustness value, which is an effective and brand-new metric to evaluate the importance of each node locally or the entire ranking results globally. The unique robustness measurement is rooted in the well-known percolation theory that with a certain fraction of nodes in a network being removed, the network collapses as much as possible. That is, the giant connected component in the collapsed network gets as small as possible. Therefore, BGN aims at finding a node sequence such that the giant connected component reduces in the steepest way. To this end, instead of deleting nodes from the network forwardly, BGN chooses to reconstruct the network by gradually adding nodes to an empty network according to the requirement that the giant connected component grows as slow as possible. We further propose heap-BGN to speed up BGN, and initial-BGN to make BGN produce more accurate results by proper initial rankings. Extensive experiments on four real-world networks and four synthetic networks demonstrate that BGN can outperform the state-of-the-art baseline algorithms, in terms of both ranking accuracy and computational efficiency.