Percolation Threshold for Competitive Influence in Random Networks

Abstract

In this paper, we propose a new averaging model for modeling the competitive influence of $K$ candidates among $n$ voters in an election process. For such an influence propagation model, we address the question of how many seeded voters a candidate needs to place among undecided voters in order to win an election. We show that for a random network generated from the stochastic block model, there exists a percolation threshold for a candidate to win the election if the number of seeded voters placed by the candidate exceeds the threshold. By conducting extensive experiments, we show that our theoretical percolation thresholds are very close to those obtained from simulations for random networks and the errors are within $10\%$ for a real-world network.

arXiv comment11 pages, 9 figures, this article is the complete version (with proofs) of the IEEE Global Communications Conference 2019 review paper

References in corpus (5)

• Fast algorithm for detecting community structure in networks
• Statistical Mechanics of Community Detection
• Influence maximization in complex networks through optimal percolation
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Opinion Dynamics in Social Networks with Hostile Camps: Consensus vs. Polarization