Influence maximization in noisy networks

Abstract

We consider the problem of identifying the most influential nodes for a spreading process on a network when prior knowledge about structure and dynamics of the system is incomplete or erroneous. Specifically, we perform a numerical analysis where the set of top spreaders is determined on the basis of prior information that is artificially altered by a certain level of noise. We then measure the optimality of the chosen set by measuring its spreading impact in the true system. Whereas we find that the identification of top spreaders is optimal when prior knowledge is complete and free of mistakes, we also find that the quality of the top spreaders identified using noisy information doesn't necessarily decrease as the noise level increases. For instance, we show that it is generally possible to compensate for erroneous information about dynamical parameters by adding synthetic errors in the structure of the network. Further, we show that, in some dynamical regimes, even completely losing prior knowledge on network structure may be better than relying on certain but incomplete information.

arXiv comment7 pages, 5 figures + appendix

References in corpus (12)

• Epidemic processes in complex networks
• Identification of influential spreaders in complex networks
• Self-similar community structure in organisations
• Influence maximization in complex networks through optimal percolation
• Detecting and Tracking the Spread of Astroturf Memes in Microblog Streams
• Network structure from rich but noisy data
• A measure of individual role in collective dynamics
• Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach
• Leveraging percolation theory to single out influential spreaders in networks
• Fundamental difference between superblockers and superspreaders in networks
• Uncertainty Reduction for Stochastic Processes on Complex Networks
• Emergence of coexisting percolating clusters in networks

Cited by in corpus (3)

• Systematic comparison between methods for the detection of influential spreaders in complex networks
• Immunization Strategies in Networks with Missing Data
• Influence maximization on temporal networks