Local structure can identify and quantify influential global spreaders in large scale social networks
arXiv:1509.03484 · doi:10.1073/pnas.1710547115
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 social network is a global process, it is commonly believed that measuring the influence of nodes inevitably requires the knowledge of the entire network. Employing percolation theory, we show that the spreading process displays a nucleation behavior: once a piece of information spread 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 entire network, any nodes' 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.
arXiv comment6 pages, 5 figures, Proceedings of the National Academy of Sciences of the United States of America (PNAS), July 3, 2018
References in corpus (21)
- Statistical physics of social dynamics
- Epidemic processes in complex networks
- Random graphs with arbitrary degree distributions and their applications
- The spread of epidemic disease on networks
- Identification of influential spreaders in complex networks
- Who is the best connected scientist? A study of scientific coauthorship networks
- Network robustness and fragility: Percolation on random graphs
- Critical phenomena in complex networks
- Influence maximization in complex networks through optimal percolation
- Prediction and predictability of global epidemics: the role of the airline transportation network
- Understanding the spreading patterns of mobile phone viruses
- Percolation Critical Exponents in Scale-Free Networks
- Generic scale of the "scale-free" growing networks
- Absence of influential spreaders in rumor dynamics
- Bootstrap Percolation on Complex Networks
- Traffic-driven Epidemic Spreading in Finite-size Scale-Free Networks
- The Role of Social Networks in Information Diffusion
- Eradicating Catastrophic Collapse in Interdependent Networks via Reinforced Nodes
- Branching Dynamics of Viral Information Spreading
- Locating privileged spreaders on an Online Social Network
- Statistical Mechanics of the Minimum Dominating Set Problem
Cited by in corpus (21)
- Percolation on complex networks: Theory and application
- Coevolution spreading in complex networks
- Fast influencers in complex networks
- Systematic comparison between methods for the detection of influential spreaders in complex networks
- Dynamic vaccination in partially overlapped multiplex network
- Optimal interlayer structure for promoting spreading of SIS model in two-layer networks
- Criticality in spreading processes without time-scale separation and the critical brain hypothesis
- Spreading dynamics of information on online social networks
- Non-trivial Resource Amount Requirement in the Early Stage for Containing Fatal Diseases
- Beyond network centrality: Individual-level behavioral traits for predicting information superspreaders in social media
- Influence maximization on temporal networks
- A generalized linear threshold model for an improved description of the spreading dynamics
- Community detection based on first passage probabilities
- A Weighted and Normalized Gould-Fernandez brokerage measure
- Predicting Nodal Influence via Local Iterative Metrics
- Beyond the Coverage of Information Spreading: Analytical and Empirical Evidence of Re-exposure in Large-scale Online Social Networks
- Detecting and modelling real percolation and phase transitions of information on social media
- Quantifying the temporal stability of international fertilizer trade networks
- Maximizing spreading influence via measuring influence overlap for social networks
- From Symbols to Embeddings: A Tale of Two Representations in Computational Social Science
- Directionality reduces the impact of epidemics in multilayer networks