# A Generalisation of Voter Model: Influential Nodes and Convergence Properties

arXiv: https://arxiv.org/abs/2411.04564 · HTML: https://mlsanity.com/paper/2411.04564/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 69 references that are in the map.
- First posted on arXiv 7 Nov 2024.

## Builds on (most cited first, 17 of 17)

- [Social Influence and the Collective Dynamics of Opinion Formation](https://mlsanity.com/paper/1311.3475/) (2013)
- [From Competition to Complementarity: Comparative Influence Diffusion and Maximization](https://mlsanity.com/paper/1507.00317/) (2015)
- [Convergence of Opinion Diffusion is PSPACE-complete](https://mlsanity.com/paper/1912.09864/) (2019)
- [Opinion Dynamics with Varying Susceptibility to Persuasion](https://mlsanity.com/paper/1801.07863/) (2018)
- [Opinion Forming in Erdos-Renyi Random Graph and Expanders](https://mlsanity.com/paper/1805.12172/) (2018)
- [Recent advances in opinion propagation dynamics: A 2020 Survey](https://mlsanity.com/paper/2004.05286/) (2020)
- [Majority Opinion Diffusion in Social Networks: An Adversarial Approach](https://mlsanity.com/paper/2012.03143/) (2020)
- [Hyperbolic Graph Generator](https://mlsanity.com/paper/1503.05180/) (2015)
- [Opinion Diffusion and Campaigning on Society Graphs](https://mlsanity.com/paper/2010.00651/) (2020)
- [Majority Vote in Social Networks: Make Random Friends or Be Stubborn to Overpower Elites](https://mlsanity.com/paper/2109.14265/) (2021)
- [A Fast Algorithm for Moderating Critical Nodes via Edge Removal](https://mlsanity.com/paper/2309.06392/) (2023)
- [Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes](https://mlsanity.com/paper/2302.06760/) (2023)
- [Do Stubborn Users Always Cause More Polarization and Disagreement? A Mathematical Study](https://mlsanity.com/paper/2410.22577/) (2024)
- [Asynchronous Majority Dynamics in Preferential Attachment Trees](https://mlsanity.com/paper/1907.05823/) (2019)
- [Maximizing the Probability of Fixation in the Positional Voter Model](https://mlsanity.com/paper/2211.14676/) (2022)
- [Graph-Based Generalization of Galam Model: Convergence Time and Influential Nodes](https://mlsanity.com/paper/2312.12811/) (2023)
- [Viral Marketing in Social Networks with Competing Products](https://mlsanity.com/paper/2312.15819/) (2023)

## Abstract (arXiv)

Consider an undirected graph G, representing a social network, where each node is blue or red, corresponding to positive or negative opinion on a topic. In the voter model, in discrete time rounds, each node picks a neighbour uniformly at random and adopts its colour. Despite its significant popularity, this model does not capture some fundamental real-world characteristics such as the difference in the strengths of individuals connections, individuals with neutral opinion on a topic, and individuals who are reluctant to update their opinion. To address these issues, we introduce and study a generalisation of the voter model. Motivating by campaigning strategies, we study the problem of selecting a set of seeds blue nodes to maximise the expected number of blue nodes after some rounds. We prove that the problem is NP- hard and provide a polynomial time approximation algorithm with the best possible approximation guarantee. Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms. We also investigate the convergence properties of the model. We prove that the process could take an exponential number of rounds to converge. However, if we limit ourselves to strongly connected graphs, the convergence time is polynomial and the period (the number of states in convergence) divides the length of all cycles in the graph.