On the Troll-Trust Model for Edge Sign ...
Type de document :
Rapport de recherche: Autre communication scientifique (congrès sans actes - poster - séminaire...)
Titre :
On the Troll-Trust Model for Edge Sign Prediction in Social Networks
Auteur(s) :
Le Falher, Géraud [Auteur]
Machine Learning in Information Networks [MAGNET]
Cesa-Bianchi, Nicolò [Auteur]
Dipartimento di Scienze dell'Informazione [Milano]
Gentile, Claudio [Auteur]
Universitá degli Studi dell’Insubria = University of Insubria [Varese] [Uninsubria]
Vitale, Fabio [Auteur]
Aalto University School of Science and Technology [Aalto, Finland]
Machine Learning in Information Networks [MAGNET]
Machine Learning in Information Networks [MAGNET]
Cesa-Bianchi, Nicolò [Auteur]
Dipartimento di Scienze dell'Informazione [Milano]
Gentile, Claudio [Auteur]
Universitá degli Studi dell’Insubria = University of Insubria [Varese] [Uninsubria]
Vitale, Fabio [Auteur]
Aalto University School of Science and Technology [Aalto, Finland]
Machine Learning in Information Networks [MAGNET]
Institution :
INRIA Lille
Date de publication :
2016
Discipline(s) HAL :
Informatique [cs]/Intelligence artificielle [cs.AI]
Résumé en anglais : [en]
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 ...
Lire la suite >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 proba-bilistic 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.Lire moins >
Lire la suite >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 proba-bilistic 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.Lire moins >
Langue :
Anglais
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-01425137/document
- Accès libre
- Accéder au document
- http://arxiv.org/pdf/1606.00182
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01425137/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01425137/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- paper.pdf
- Accès libre
- Accéder au document
- 1606.00182
- Accès libre
- Accéder au document