On the non-progressive spread of influence through social networks

DOI10.1007/978-3-642-29344-3_27zbMATH Open1353.68302arXiv1106.3826OpenAlexW2147658677MaRDI QIDQ2894476FDOQ2894476

Authors: Mohammad Ghodsi, Jafar Habibi, Pooya Jalaly Khalilabadi, Sina Sadeghian Sadeghabad, MohammadAmin Fazli, Vahab S. Mirrokni 

Publication date: 29 June 2012

Published in: LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Abstract: The spread of influence in social networks is studied in two main categories: the progressive model and the non-progressive model (see e.g. the seminal work of Kempe, Kleinberg, and Tardos in KDD 2003). While the progressive models are suitable for modeling the spread of influence in monopolistic settings, non-progressive are more appropriate for modeling non-monopolistic settings, e.g., modeling diffusion of two competing technologies over a social network. Despite the extensive work on the progressive model, non-progressive models have not been studied well. In this paper, we study the spread of influence in the non-progressive model under the strict majority threshold: given a graph $G$ with a set of initially infected nodes, each node gets infected at time $au$ iff a majority of its neighbors are infected at time $au-1$. Our goal in the extit{MinPTS} problem is to find a minimum-cardinality initial set of infected nodes that would eventually converge to a steady state where all nodes of $G$ are infected. We prove that while the MinPTS is NP-hard for a restricted family of graphs, it admits an improved constant-factor approximation algorithm for power-law graphs. We do so by proving lower and upper bounds in terms of the minimum and maximum degree of nodes in the graph. The upper bound is achieved in turn by applying a natural greedy algorithm. Our experimental evaluation of the greedy algorithm also shows its superior performance compared to other algorithms for a set of real-world graphs as well as the random power-law graphs. Finally, we study the convergence properties of these algorithms and show that the non-progressive model converges in at most $O(|E(G)|)$ steps.

Full work available at URL: https://arxiv.org/abs/1106.3826

Recommendations

• On non-progressive spread of influence through social networks
• On the approximability of influence in social networks
• Diffusion in social networks with competing products
• scientific article
• Social networks with competing products

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Approximation algorithms (68W25)

Cited In (8)

• On non-progressive spread of influence through social networks
• How to choose friends strategically
• Complexity of equilibrium in competitive diffusion games on social networks
• Social percolation and the influence of mass media
• Some results on non-progressive spread of influence in graphs
• Whom to befriend to influence people
• Influence Diffusion in Social Networks
• Influence Diffusion in Social Networks under Time Window Constraints

This page was built for publication: On the non-progressive spread of influence through social networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2894476)