Fighting Opinion Control in Social Networks via Link Recommendation

TitleFighting Opinion Control in Social Networks via Link Recommendation
Publication TypeConference Paper
Year of Publication2019
AuthorsAmelkin V, Singh AK
Conference NameACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'19)
Date Published08/2019
PublisherACM
Conference LocationAnchorage, AK
Keywordscentrality optimization, link recommendation, Markov chain, mean first passage time, network design, opinion control, random walk, social network
Abstract

The process of opinion formation is inherently a network process, with user opinions in a social network being driven to a certain average opinion. One simple and intuitive incarnation of this opinion attractor is the average π ⊺x of user opinions xi weighted by the users’ eigenvector centralities πi . This value is a lucrative target for control, as altering it essentially changes the mass opinion in the network. Since any potentially malicious influence upon the opinion distribution in a society is undesirable, it is important to design methods to prevent external attacks upon it.

In this work, we assume that the adversary aims to maliciously change the network’s average opinion by altering the opinions of some unknown users. We, then, state an NP-hard problem of disabling such opinion control attempts via strategically altering the network’s users’ eigencentralities by recommending a limited number of links to the users. Relying on Markov chain theory, we provide perturbation analysis that shows how eigencentrality and, hence, our problem’s objective change in response to a link’s addition to the network. The latter leads to the design of a pseudolinear-time heuristic, relying on efficient estimation of mean first passage times in Markov chains. We have confirmed our theoretical and algorithmic findings, and studied effectiveness and efficiency of our heuristic in experiments with synthetic and real networks.

DOI10.1145/3292500.3330960
Refereed DesignationRefereed