44
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Identifying Influential Nodes in Large-Scale Directed Networks: The Role of Clustering

      research-article
      1 , 3 , 1 , 2 , 3 , * , 1
      PLoS ONE
      Public Library of Science

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          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 nodes, more than 15 times faster than PageRank.

          Related collections

          Most cited references11

          • Record: found
          • Abstract: found
          • Article: found
          Is Open Access

          Epidemic spreading in scale-free networks

          The Internet, as well as many other networks, has a very complex connectivity recently modeled by the class of scale-free networks. This feature, which appears to be very efficient for a communications network, favors at the same time the spreading of computer viruses. We analyze real data from computer virus infections and find the average lifetime and prevalence of viral strains on the Internet. We define a dynamical model for the spreading of infections on scale-free networks, finding the absence of an epidemic threshold and its associated critical behavior. This new epidemiological framework rationalize data of computer viruses and could help in the understanding of other spreading phenomena on communication and social networks.
            Bookmark
            • Record: found
            • Abstract: found
            • Article: not found

            The spread of behavior in an online social network experiment.

            How do social networks affect the spread of behavior? A popular hypothesis states that networks with many clustered ties and a high degree of separation will be less effective for behavioral diffusion than networks in which locally redundant ties are rewired to provide shortcuts across the social space. A competing hypothesis argues that when behaviors require social reinforcement, a network with more clustering may be more advantageous, even if the network as a whole has a larger diameter. I investigated the effects of network structure on diffusion by studying the spread of health behavior through artificially structured online communities. Individual adoption was much more likely when participants received social reinforcement from multiple neighbors in the social network. The behavior spread farther and faster across clustered-lattice networks than across corresponding random networks.
              Bookmark
              • Record: found
              • Abstract: found
              • Article: not found

              Coevolutionary games--a mini review.

              Prevalence of cooperation within groups of selfish individuals is puzzling in that it contradicts with the basic premise of natural selection. Favoring players with higher fitness, the latter is key for understanding the challenges faced by cooperators when competing with defectors. Evolutionary game theory provides a competent theoretical framework for addressing the subtleties of cooperation in such situations, which are known as social dilemmas. Recent advances point towards the fact that the evolution of strategies alone may be insufficient to fully exploit the benefits offered by cooperative behavior. Indeed, while spatial structure and heterogeneity, for example, have been recognized as potent promoters of cooperation, coevolutionary rules can extend the potentials of such entities further, and even more importantly, lead to the understanding of their emergence. The introduction of coevolutionary rules to evolutionary games implies, that besides the evolution of strategies, another property may simultaneously be subject to evolution as well. Coevolutionary rules may affect the interaction network, the reproduction capability of players, their reputation, mobility or age. Here we review recent works on evolutionary games incorporating coevolutionary rules, as well as give a didactic description of potential pitfalls and misconceptions associated with the subject. In addition, we briefly outline directions for future research that we feel are promising, thereby particularly focusing on dynamical effects of coevolutionary rules on the evolution of cooperation, which are still widely open to research and thus hold promise of exciting new discoveries. Copyright (c) 2009 Elsevier Ireland Ltd. All rights reserved.
                Bookmark

                Author and article information

                Contributors
                Role: Editor
                Journal
                PLoS One
                PLoS ONE
                plos
                plosone
                PLoS ONE
                Public Library of Science (San Francisco, USA )
                1932-6203
                2013
                31 October 2013
                : 8
                : 10
                : e77455
                Affiliations
                [1 ]Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, People’s Republic of China
                [2 ]Institute of Information Economy, Alibaba Business College, Hangzhou Normal University, Hangzhou, People’s Republic of China
                [3 ]Department of Physics, University of Fribourg, Fribourg, Switzerland
                University of Maribor, Slovenia
                Author notes

                Competing Interests: The authors have declared that no competing interests exist.

                Conceived and designed the experiments: DBC LL TZ. Performed the experiments: DBC HG. Analyzed the data: DBC HG LL. Contributed reagents/materials/analysis tools: DBC LL TZ. Wrote the paper: DBC LL TZ.

                Article
                PONE-D-13-27921
                10.1371/journal.pone.0077455
                3814409
                24204833
                c8624de9-54cd-4984-9c3c-59898078bfca
                Copyright @ 2013

                This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

                History
                : 24 June 2013
                : 4 September 2013
                Page count
                Pages: 10
                Funding
                This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 11222543, 90924011, 60903073 and 11205042, and the International Scientific Cooperation and Communication Project of Sichuan Province in China under Grant No. 2010HH0002. D.B.C. acknowledges the Huawei university-enterprise cooperation project YBCB2011057. L.L. acknowledges the research start-up fund of Hangzhou Normal University under Grant Nos. 2011QDL29 and 2011QDL31. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
                Categories
                Research Article

                Uncategorized
                Uncategorized

                Comments

                Comment on this article