Viral Marketing and Convergence Properties in Generalised Voter Model

Abhiram Manohara, Ahad N. ZehmakanIJCAI 2025 · DOI

TL;DR

This paper introduces a generalized Voter Model (GVM) that accounts for directed, weighted social networks and users with varying levels of opinion stubbornness. They tackle the viral marketing problem of maximizing blue node adoption, proving it's NP-hard but offering a near-optimal greedy algorithm. The work also analyzes the convergence properties of GVM, showing it can be exponential in general graphs but polynomial for strongly connected ones.

What Problem Does This Paper Address?

The original Voter Model (VM) is a foundational concept for understanding how opinions spread in social networks. In VM, nodes (users) randomly pick a neighbor and adopt their opinion (e.g., blue or red). However, this simple model fails to capture crucial real-world complexities: social connections aren't always mutual (directed graphs), some relationships are stronger than others (weighted graphs), and individuals might have no initial opinion or be resistant to changing their minds (stubbornness). This paper addresses these limitations by proposing a Generalized Voter Model (GVM) and then investigates two key problems within this more realistic framework: 1) how to strategically select initial "blue" users to maximize the spread of a positive opinion (viral marketing), and 2) how long it takes for opinions to stabilize in the network (convergence properties).

Methods

The authors introduce a Generalized Voter Model (GVM) that extends the classic Voter Model by incorporating:

  • Directed and Weighted Graphs: Edges can have directions (e.g., "following" on social media) and weights representing the strength of influence.
  • Uncolored Nodes: Users can start with no opinion.
  • Stubborn Nodes: Nodes with no outgoing edges are fixed in their opinion, mimicking resistance to change.

For the Adoption Maximization (AM) problem (viral marketing), they:

  • Prove NP-hardness: This establishes that finding the absolute best solution is computationally intractable for large networks.
  • Develop a Polynomial-Time Greedy Algorithm: This algorithm iteratively selects seed nodes that provide the largest marginal increase in expected blue nodes. The proof of its effectiveness relies on demonstrating that the objective function is monotone and submodular.
  • Establish a Lower Bound: They prove that no polynomial-time algorithm can achieve a better approximation ratio than $(1 - 1/e)$ unless a fundamental complexity hypothesis is violated, matching the theoretical guarantee of their greedy algorithm.

For Convergence Properties, they:

  • Analyze as a Markov Chain: The opinion dynamics are modeled as a Markov chain where states are colorings of the network.
  • Define Convergence Time and Period: Convergence time is how long it takes to reach a stable state, and convergence period is the size of the stable configurations.
  • Derive Bounds: They prove that convergence time and period can be exponential in general graphs but provide polynomial bounds for strongly connected graphs, relating them to the graph's cycle lengths.

Datasets

The paper uses several real-world social network datasets from the SNAP database for experimental evaluation:

  • Facebook 0
  • Twitter
  • Facebook 414
  • Wikipedia
  • Bitcoin OTC
  • Gnutella
  • Bitcoin Alpha

Key Insights and Ideas

  • Realism Matters: The GVM's ability to model directed, weighted networks with uncolored and stubborn nodes makes it a much more powerful tool for understanding real-world opinion dynamics than the basic Voter Model.
  • Viral Marketing is Hard, but Solvable (Approximately): The NP-hardness of maximizing blue node adoption highlights the challenge of strategic influence campaigns. However, the greedy algorithm provides a theoretically sound and practically effective solution with a strong approximation guarantee.
  • Network Structure Dictates Convergence: The convergence behavior of opinion dynamics is highly dependent on the network's structure. Strongly connected graphs offer more predictable and faster convergence, while general graphs can exhibit very slow or cyclical opinion patterns.
  • Cycles and Stubbornness Shape Dynamics: The presence of cycles and stubborn nodes significantly impacts how long it takes for opinions to stabilize and the nature of those stable states.

Key Results

  • Adoption Maximization: The proposed greedy algorithm achieves a $(1 - 1/e)$ approximation ratio for the Adoption Maximization problem, which is proven to be the best possible unless NP $\subseteq$ DTIME(n$^{O(\log \log n)}$). Experiments show it outperforms various centrality-based methods on real-world datasets.
  • Convergence Properties:
    • For strongly connected graphs, the convergence period divides the highest common divisor of all cycle lengths.
  • For strongly connected graphs, the convergence time is bounded by $O(\gamma n^3 \log(n))$, where $\gamma$ is related to the graph's period.
  • In general graphs, both convergence time and period can be exponentially large. For instance, a specific construction shows an exponential period of $2^{n-2}$.

Limitations and Future Work

  • Scalability of the Greedy Algorithm: While polynomial, the $O(n^3 k \tau)$ runtime of the greedy algorithm might still be too slow for extremely large real-world networks. Future work could explore faster approximation algorithms.
  • General Graph Convergence: The exponential bounds for convergence in general graphs are a significant limitation. Further research is needed to understand convergence behavior on more realistic, complex graph structures and to potentially find tighter bounds or specific conditions for faster convergence.
  • Model Extensions: The authors suggest exploring extensions such as loyal seed nodes (who never change their opinion) and optimizing average adoption over time rather than a fixed time $\tau$. Investigating convergence properties for different agent types and scenarios is also a promising avenue.

Summary updated

BibTeX
@inproceedings{manohara2025viral,
  author = {Abhiram Manohara and Ahad N. Zehmakan},
  title = {{Viral Marketing and Convergence Properties in Generalised Voter Model}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/442},
}
Figure