Studies reveal the mechanisms behind tumor metastasis and how to stymie it. But primary tumors still get the lion’s share of researchers’ attention.
Image courtesy of Science Source/Phanie.
New Research In
Physical Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
Contributed by H. Eugene Stanley, December 31, 2017 (sent for review August 31, 2017; reviewed by Marc Barthelemy and Zoltán Toroczkai)
Significance
Identification and quantification of influential spreaders in social networks are challenging due to the gigantic network sizes and limited availability of the entire structure. Here we show that such difficulty can be overcome by reducing the problem scale to a local one, which is essentially independent of the entire network. This is because in viral spreading the characteristic spreading size does not depend on network structure outside the local environment of the seed spreaders. Our approach may open the door to solve various big data problems such as false information surveillance and control, viral marketing, epidemic control, and network protection.
Abstract
Measuring and optimizing the influence of nodes in big-data online social networks are important for many practical applications, such as the viral marketing and the adoption of new products. As the viral spreading on a social network is a global process, it is commonly believed that measuring the influence of nodes inevitably requires the knowledge of the entire network. Using percolation theory, we show that the spreading process displays a nucleation behavior: Once a piece of information spreads from the seeds to more than a small characteristic number of nodes, it reaches a point of no return and will quickly reach the percolation cluster, regardless of the entire network structure; otherwise the spreading will be contained locally. Thus, we find that, without the knowledge of the entire network, any node’s global influence can be accurately measured using this characteristic number, which is independent of the network size. This motivates an efficient algorithm with constant time complexity on the long-standing problem of best seed spreaders selection, with performance remarkably close to the true optimum.
Footnotes
↵1Y.H., S.J., Y.J., L.F., H.E.S., and S.H. contributed equally to this work.
- ↵2To whom correspondence may be addressed. Email: huyanq{at}mail.sysu.edu.cn or hes{at}bu.edu.
Author contributions: Y.H., L.F., and S.H. designed research; Y.H., S.J., and Y.J. performed research; Y.H., S.J., H.E.S., and S.H. analyzed data; and Y.H., L.F., H.E.S., and S.H. wrote the paper.
Reviewers: M.B., Centre Commissariat à l’Energie Atomique; and Z.T., University of Notre Dame.
The authors declare no conflict of interest.
This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1710547115/-/DCSupplemental.
Published under the PNAS license.
Log in using your username and password
Purchase access
You may purchase access to this article. This will require you to create an account if you don't already have one.
Local structure can identify and quantify influential global spreaders in large scale social networks
More Articles of This Classification
Physical Sciences
Related Content
Cited by...
- No citing articles found.
Similar Articles
You May Also be Interested in
Both social and engineering factors must be further explored and scrutinized across the globe—as should notions of justice related to flooding impacts and responses.
Image courtesy of Shutterstock.com/Ekaterina Pokrovsky.
Blair Hedges discusses the state of Haiti's remaining forests and the consequences to biodiversity.
A study uncovers genetic evidence of early colonization of Jamaica by primates and suggests that adaptation can shape species morphology in novel environments, even when species come from morphologically conservative families.
Image courtesy of Lorraine Meeker (American Museum of Natural History, New York).
Researchers report that some moth species use sound absorbing-scales to avoid detection by bats and suggest that the findings could aid the design of biologically inspired sound absorbers for an array of applications, including noise mitigation and building acoustics.
Image courtesy of Thomas R. Neil.
