6
6.0

Jun 29, 2018
06/18

by
Géraud Le Falher; Fabio Vitale

texts

#
eye 6

#
favorite 0

#
comment 0

We address the problem of classifying the links of signed social networks given their full structural topology. Motivated by a binary user behaviour assumption, which is supported by decades of research in psychology, we develop an efficient and surprisingly simple approach to solve this classification problem. Our methods operate both within the active and batch settings. We demonstrate that the algorithms we developed are extremely fast in both theoretical and practical terms. Within the...

Topics: Social and Information Networks, Physics and Society, Physics, Computing Research Repository,...

Source: http://arxiv.org/abs/1602.08986

42
42

Sep 21, 2013
09/13

by
Nicolo Cesa-Bianchi; Claudio Gentile; Fabio Vitale; Giovanni Zappella

texts

#
eye 42

#
favorite 0

#
comment 0

We present very efficient active learning algorithms for link classification in signed networks. Our algorithms are motivated by a stochastic model in which edge labels are obtained through perturbations of a initial sign assignment consistent with a two-clustering of the nodes. We provide a theoretical analysis within this model, showing that we can achieve an optimal (to whithin a constant factor) number of mistakes on any graph G = (V,E) such that |E| = \Omega(|V|^{3/2}) by querying...

Source: http://arxiv.org/abs/1301.4767v2

76
76

Sep 21, 2013
09/13

by
Nicolo Cesa-Bianchi; Claudio Gentile; Fabio Vitale; Giovanni Zappella

texts

#
eye 76

#
favorite 0

#
comment 0

Motivated by social balance theory, we develop a theory of link classification in signed networks using the correlation clustering index as measure of label regularity. We derive learning bounds in terms of correlation clustering within three fundamental transductive learning settings: online, batch and active. Our main algorithmic contribution is in the active setting, where we introduce a new family of efficient link classifiers based on covering the input graph with small circuits. These are...

Source: http://arxiv.org/abs/1301.4769v2

42
42

Sep 21, 2013
09/13

by
Nicolo Cesa-Bianchi; Claudio Gentile; Fabio Vitale; Giovanni Zappella

texts

#
eye 42

#
favorite 0

#
comment 0

We investigate the problem of active learning on a given tree whose nodes are assigned binary labels in an adversarial way. Inspired by recent results by Guillory and Bilmes, we characterize (up to constant factors) the optimal placement of queries so to minimize the mistakes made on the non-queried nodes. Our query selection algorithm is extremely efficient, and the optimal number of mistakes on the non-queried nodes is achieved by a simple and efficient mincut classifier. Through a simple...

Source: http://arxiv.org/abs/1301.5112v1

59
59

Sep 21, 2013
09/13

by
Fabio Vitale; Nicolo Cesa-Bianchi; Claudio Gentile; Giovanni Zappella

texts

#
eye 59

#
favorite 0

#
comment 0

Predicting the nodes of a given graph is a fascinating theoretical problem with applications in several domains. Since graph sparsification via spanning trees retains enough information while making the task much easier, trees are an important special case of this problem. Although it is known how to predict the nodes of an unweighted tree in a nearly optimal way, in the weighted case a fully satisfactory algorithm is not available yet. We fill this hole and introduce an efficient node...

Source: http://arxiv.org/abs/1301.5160v2

51
51

Sep 23, 2013
09/13

by
Nicolo' Cesa-Bianchi; Claudio Gentile; Fabio Vitale; Giovanni Zappella

texts

#
eye 51

#
favorite 0

#
comment 0

We investigate the problem of sequentially predicting the binary labels on the nodes of an arbitrary weighted graph. We show that, under a suitable parametrization of the problem, the optimal number of prediction mistakes can be characterized (up to logarithmic factors) by the cutsize of a random spanning tree of the graph. The cutsize is induced by the unknown adversarial labeling of the graph nodes. In deriving our characterization, we obtain a simple randomized algorithm achieving in...

Source: http://arxiv.org/abs/1212.5637v1

11
11

Aug 11, 2020
08/20

by
Nicol Cesa-Bianchi; Claudio Gentile; Fabio Vitale; Giovanni Zappella

data

#
eye 11

#
favorite 0

#
comment 0

Source: http://academictorrents.com/details/66ed1109aa9929c9eb1c24516b32955b7150b2f3

3
3.0

Jun 29, 2018
06/18

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

texts

#
eye 3

#
favorite 0

#
comment 0

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...

Topics: Social and Information Networks, Computing Research Repository, Learning

Source: http://arxiv.org/abs/1606.00182