On the troll-trust model for edge sign prediction in social networks

Géraud Le Falher, Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

4 Downloads (Pure)

Abstract

In the problem of edge sign prediction, we are given a directed graph (representing a social network), and our task is to predict the binary labels of the edges (i.e., the positive or negative nature of the social relationships). Many successful heuristics for this problem are based on the troll-trust features, estimating at each node the fraction of outgoing and incoming positive/negative edges. We show that these heuristics can be understood, and rigorously analyzed, as approximators to the Bayes optimal classifier for a simple probabilistic model of the edge labels. We then show that the maximum likelihood estimator for this model approximately corresponds to the predictions of a Label Propagation algorithm run on a transformed version of the original social graph. Extensive experiments on a number of real-world datasets show that this algorithm is competitive against state-of-the-art classifiers in terms of both accuracy and scalability. Finally, we show that troll-trust features can also be used to derive online learning algorithms which have theoretical guarantees even when edges are adversarially labeled.

Original languageEnglish
Title of host publicationProceedings of the 20th International Conference on Artificial Intelligence and Statistics
PublisherJMLR
Pages402-411
Publication statusPublished - 1 Jan 2017
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Artificial Intelligence and Statistics - Hyatt Pier 66 Hotel, Fort Lauderdale, United States
Duration: 20 Apr 201722 Apr 2017
Conference number: 20

Publication series

NameProceedings of Machine Learning Research
PublisherPMLR
Volume54
ISSN (Electronic)2640-3498

Conference

ConferenceInternational Conference on Artificial Intelligence and Statistics
Abbreviated titleAISTATS
CountryUnited States
CityFort Lauderdale
Period20/04/201722/04/2017

Fingerprint Dive into the research topics of 'On the troll-trust model for edge sign prediction in social networks'. Together they form a unique fingerprint.

Cite this