A Generalisation of Voter Model: Influential Nodes and Convergence Properties
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.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Multi-Winner Voting with Argumentative Ballots
We introduce multi-winner voting with argumentative ballots (MVArg) and investigate theoretical properties. As our conceptual contribution, we generalise approval ballots to argumentative ballots, thereby allowing voters…
Federated Learning with Nonvacuous Generalisation Bounds
We introduce a novel strategy to train randomised predictors in federated learning, where each node of the network aims at preserving its privacy by releasing a local predictor but keeping secret its training dataset wit…
Federated LearningInfluential News and Policy-making
It is believed that interventions that change the media's costs of misreporting can increase the information provided by media outlets. This paper analyzes the validity of this claim and the welfare implications of those…
Identifying Influential Nodes in Two-mode Data Networks using Formal Concept Analysis
Identifying important actors (or nodes) in a two-mode network often remains a crucial challenge in mining, analyzing, and interpreting real-world networks. While traditional bipartite centrality indices are often used to…
Forecasting elections results via the voter model with stubborn nodes
In this paper we propose a novel method to forecast the result of elections using only official results of previous ones. It is based on the voter model with stubborn nodes and uses theoretical results developed in a pre…