Voter model on signed social networks

Yanhua Li, Wei Chen, Yajun Wang, Zhi Li Zhang

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


Online social networks (OSNs) are becoming increasingly popular and are generating great interest in the study of the influence diffusion and influence maximization with applications to online viral marketing. Existing studies focus on social networks with only friendship relations, whereas the foe or enemy relations that commonly exist in many OSNs, e.g., Epinions and Slashdot, are completely ignored. In this study, we make the first attempt to investigate the influence diffusion and influence maximization in OSNs with both friend and foe relations, which are modeled using positive and negative edges on signed networks. In particular, we extend the classic voter model to signed networks and analyze the dynamics of influence diffusion of two opposite opinions. We first provide systematic characterization of both short-term and long-term dynamics of influence diffusion in this model and illustrate that the steady state behaviors of the dynamics depend on three types of graph structures, which we refer to as balanced graphs, anti balanced graphs, and strictly unbalanced graphs. We then apply our results to solve the influence maximization problem and develop efficient algorithms to select initial seeds of one opinion that maximize either its short-term influence coverage or long-term steady state influence coverage. Extensive simulation results on both synthetic and real-world networks, such as Epinions and Slashdot, confirm our theoretical analysis on influence diffusion dynamics, and demonstrate the efficacy of our influence maximization algorithm over other heuristic algorithms.

Original languageEnglish (US)
Pages (from-to)93-133
Number of pages41
JournalInternet Mathematics
Issue number2
StatePublished - Jan 1 2015

Bibliographical note

Funding Information:
Yanhua Li and Zhi-Li Zhang were supported in part by DoD ARO MURI Award W911NF-12-1-0385, DTRA grant HDTRA1-09-1-0050, and NSF grants CNS-1017092, CNS-10171647, and CNS-1117536.

Publisher Copyright:
© Taylor & Francis Group, LLC.


Dive into the research topics of 'Voter model on signed social networks'. Together they form a unique fingerprint.

Cite this