2024/11/07 by Abhiram Manohara, Manohara, Abhiram, Ahad N. Zehmakan +1 · 1 citation
Economics, Econometrics and Finance · Physics and Astronomy · #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems #Opinion Dynamics and Social Influence #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2411.04564
openalex publication_date 2024/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.