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:
- General Thresholds: Moving beyond the strict majority rule to linear threshold models where nodes have varying levels of resistance to change.
- 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.
- Clustered Topologies: Investigating how community structures and high clustering coefficients affect the performance of the greedy approach compared to power-law assumptions.
Summary updated