Local structure can identify and quantify influential global spreaders in large scale social networks

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.

6 pages, 5 figures, Proceedings of the National Academy of Sciences of the United States of America (PNAS), July 3, 2018

References in corpus (10)

• Statistical physics of social dynamics
• Epidemic processes in complex networks
• 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
• 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
• 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