A Generalisation of Voter Model: Influential Nodes and Convergence Properties
This work addresses modeling social network opinion dynamics for researchers in network science, but it is incremental as it builds upon the existing voter model framework.
The authors tackled the limitations of the classic voter model by introducing a generalization that accounts for factors like connection strengths and neutral opinions, proving NP-hardness for seed selection and providing a polynomial-time approximation algorithm with optimal guarantees, which outperformed other algorithms in experiments.
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.