期刊
IEEE ACCESS
卷 6, 期 -, 页码 59949-59962出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/ACCESS.2018.2875247
关键词
Influential nodes; node ranking; robustness value; complex networks; network science
资金
- National Key Research and Development Program of China [2018YFB1004804]
- National Natural Science Foundation of China [61722214, 11801595]
- Guangdong Province Universities and Colleges Pearl River Scholar Funded Scheme (2016)
- Natural Science Foundation of Guangdong [2018A030310076]
- CCF Opening Project of Information System
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据