Journal article

Identifying influential nodes in large-scale directed networks: the role of clustering

  • Chen, Duan-Bing Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China - Department of Physics, University of Fribourg, Switzerland
  • Gao, Hui Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China
  • Lü, Linyuan Institute of Information Economy, Alibaba Business College, Hangzhou Normal University, China - Department of Physics, University of Fribourg, Switzerland
  • Zhou, Tao Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China
Show more…
    31.10.2013
Published in:
  • PLoS ONE. - 2013, vol. 8, no. 10, p. e77455
English Identifying influential nodes in very large-scale directed networks is a big challenge relevant to disparate applications, such as accelerating information propagation, controlling rumors and diseases, designing search engines, and understanding hierarchical organization of social and biological networks. Known methods range from node centralities, such as degree, closeness and betweenness, to diffusion-based processes, like PageRank and LeaderRank. Some of these methods already take into account the influences of a node’s neighbors but do not directly make use of the interactions among it’s neighbors. Local clustering is known to have negative impacts on the information spreading. We further show empirically that it also plays a negative role in generating local connections. Inspired by these facts, we propose a local ranking algorithm named ClusterRank, which takes into account not only the number of neighbors and the neighbors’ influences, but also the clustering coefficient. Subject to the susceptible-infected-recovered (SIR) spreading model with constant infectivity, experimental results on two directed networks, a social network extracted from delicious.com and a large-scale short-message communication network, demonstrate that the ClusterRank outperforms some benchmark algorithms such as PageRank and LeaderRank. Furthermore, ClusterRank can also be applied to undirected networks where the superiority of ClusterRank is significant compared with degree centrality and k-core decomposition. In addition, ClusterRank, only making use of local information, is much more efficient than global methods: It takes only 191 seconds for a network with about 10⁷ nodes, more than 15 times faster than PageRank.
Faculty
Faculté des sciences et de médecine
Department
Département de Physique
Language
  • English
Classification
Physics
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/303398
Statistics

Document views: 34 File downloads:
  • zho_iin.pdf: 29