On the Non-Progressive Spread of Influence through Social Networks

MohammadAmin Fazli, Mohammad Ghodsi, Jafar Habibi, Pooya Jalaly Khalilabadi, Vahab Mirrokni, Sina Sadeghian Sadeghabad

Abstract

The spread of influence in social networks is studied in two main categories: the progressive model and the non-progressive model. While progressive models are suitable for modeling the spread of influence in monopolistic settings, non-progressive models are more appropriate for modeling non-monopolistic settings, such as the diffusion of competing technologies. Despite extensive work on progressive models, non-progressive models remain under-explored. 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 $\tau$ if and only if a majority of its neighbors were infected at time $\tau-1$. Our goal in the 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 MinPTS is NP-hard for a restricted family of graphs, it admits an improved constant-factor approximation algorithm for power-law graphs. We derive lower and upper bounds in terms of the minimum and maximum degree of nodes and propose a natural greedy algorithm. Experimental evaluation shows its superior performance compared to traditional heuristics on real-world and random power-law graphs. Finally, we show that the non-progressive model converges in at most $O(|E(G)|)$ steps.

Introduction

Most research on viral diffusion assumes a progressive model: once a node adopts a behavior or product, it remains in that state indefinitely. However, in many real-world scenarios—such as choosing between competing messaging apps or social platforms—influence is non-progressive. Users may switch back and forth based on the current preferences of their social circle. This paper addresses the dynamics of such systems under a strict majority threshold rule, where a node's state at any given time is determined by the majority state of its neighbors in the previous time step.

The MinPTS Problem

The core challenge identified is the Minimum Perfect Target Set (MinPTS) problem. In this framework, we seek the smallest possible set of "seed" nodes that, when initially infected, will eventually lead to a stable state where every node in the network is infected.

This problem is fundamentally different from progressive influence maximization. Because nodes can "recover" or switch back to an uninfected state if their neighbors change, the strategy for selecting seeds must be more robust. The authors demonstrate that this problem is NP-hard for general graphs through a reduction from the Minimum Dominating Set problem, necessitating the development of specialized approximation algorithms.

Theoretical Framework and Convergence

A significant contribution of this work is the analysis of the system's stability. In non-progressive models, there is a theoretical risk of infinite oscillation, where nodes flip states forever. By employing potential functions—specifically by tracking the number of edges connecting nodes with different states—the authors prove that the system must converge to either a stable state or a cycle of length two within $O(|E(G)|)$ steps.

Furthermore, the authors simplify the bounding process by proving that bounds derived for bipartite graphs can be generalized to all graph topologies (Lemma 1). They establish a lower bound for the target set size at $\frac{2n}{\Delta(G)+1}$, where $\Delta(G)$ is the maximum degree in the network.

The Greedy NPPTS Algorithm

To solve the MinPTS problem efficiently, the authors propose the Greedy NPPTS algorithm. This approach leverages the structural properties of the network, particularly the degree distribution. The algorithm sorts vertices and iteratively evaluates whether a node should be included in the seed set based on its neighbors' connectivity.

This algorithm is particularly effective for power-law graphs, which are ubiquitous in social media and communication networks. In these "rich-get-richer" structures, the high frequency of low-degree nodes allows the greedy approach to achieve a constant-factor approximation of the optimal solution.

Experimental Evaluation

The authors tested the Greedy NPPTS algorithm against several real-world datasets and synthetic power-law graphs:

  • Social Networks: Epinions (trust networks) and Slashdot (friend/foe networks).
  • Information Networks: Arxiv (citation/collaboration) and Amazon (co-purchasing).

The results highlight a critical failure in traditional influence heuristics. Common strategies like targeting "High-Degree" nodes or those with high "Centrality" perform poorly in non-progressive settings. In the Epinions network, for instance, these standard heuristics often required infecting nearly 100% of the network to achieve total spread. In contrast, the Greedy NPPTS algorithm required only approximately 35% of the nodes to reach the same outcome.

Conclusion and Future Work

This research demonstrates that while non-progressive influence spread is computationally difficult in the general sense, the specific topology of real-world social networks (power-law distributions) provides a pathway for highly efficient approximation. The Greedy NPPTS algorithm significantly outperforms standard heuristics by accounting for the possibility of nodes reverting their state.

Future research directions include:

  1. General Thresholds: Moving beyond the strict majority rule to linear threshold models where nodes have varying levels of resistance to change.
  2. Budget Constraints: Solving the "Maximum Active Set" problem, where the goal is to maximize the final number of infected nodes given a fixed budget of $k$ initial seeds.
  3. Clustered Topologies: Investigating how community structures and high clustering coefficients affect the performance of the greedy approach compared to power-law assumptions.

Summary updated

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 $τ$ iff a majority of its neighbors are infected at time $τ-1$. Our goal in the \textit{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.
BibTeX
@inproceedings{fazli2012non,
  author = {MohammadAmin Fazli and Mohammad Ghodsi and Jafar Habibi and Pooya Jalaly Khalilabadi and Vahab Mirrokni and Sina Sadeghian Sadeghabad},
  title = {{On the Non-Progressive Spread of Influence through Social Networks}},
  booktitle = {LATIN},
  year = {2012},
  doi = {10.1007/978-3-642-29344-3\_27},
}
Figure