Signed network analysis has attracted increasing attention in recent years. This is in part because research on signed network analysis suggests that negative links have added value in the analytical process. A major impediment in their effective use is that most social media sites do not enable users to specify them explicitly. In other words, a gap exists between the importance of negative links and their availability in real data sets. Therefore, it is natural to explore whether one can predict negative links automatically from the commonly available social network data. In this paper, we investigate the novel problem of negative link prediction with only positive links and content-centric interactions in social media. We make a number of important observations about negative links, and propose a principled framework NeLP, which can exploit positive links and content-centric interactions to predict negative links. Our experimental results on real-world social networks demonstrate that the proposed NeLP framework can accurately predict negative links with positive links and content-centric interactions. Our detailed experiments also illustrate the relative importance of various factors to the effectiveness of the proposed framework.
Positive and negative link prediction infers new positive and negative links by giving a snapshot of a signed network, which has attracted increasing attention in recent years @cite_9 . @cite_22 , an algorithm based on trust and distrust propagation is proposed to predict trust and distrust relations. @cite_17 , local-topology-based features based on balance theory are extracted to improve the performance of a logistic regression classifier in signed relation prediction. Features derived from longer cycles in signed networks can be used to improve the positive and negative link prediction performance @cite_21 . @cite_3 , a low-rank matrix factorization approach with generalized loss functions is proposed to predict trust and distrust relations.
@cite_22 @cite_9 @cite_21 @cite_3 @cite_17
2028513945 1964537599 2156273451 2019483176
Trust networks, where people leave trust and distrust feedback, are becoming increasingly common. These networks may be regarded as signed graphs, where a positive edge weight captures the degree of trust while a negative edge weight captures the degree of distrust. Analysis of such signed networks has become an increasingly important research topic. One important analysis task is that of sign inference, i.e., infer unknown (or future) trust or distrust relationships given a partially observed signed network. Most state-of-the-art approaches consider the notion of structural balance in signed networks, building inference algorithms based on information about links, triads, and cycles in the network. In this paper, we first show that the notion of weak structural balance in signed networks naturally leads to a global low-rank model for the network. Under such a model, the sign inference problem can be formulated as a low-rank matrix completion problem. We show that we can perfectly recover missing relationships, under certain conditions, using state-of-the-art matrix completion algorithms. We also propose the use of a low-rank matrix factorization approach with generalized loss functions as a practical method for sign inference - this approach yields high accuracy while being scalable to large signed networks, for instance, we show that this analysis can be performed on a synthetic graph with 1.1 million nodes and 120 million edges in 10 minutes. We further show that the low-rank model can be used for other analysis tasks on signed networks, such as user segmentation through signed graph clustering, with theoretical guarantees. Experiments on synthetic as well as real data show that our low rank model substantially improves accuracy of sign inference as well as clustering. As an example, on the largest real dataset available to us (Epinions data with 130K nodes and 840K edges), our matrix factorization approach yields 94.6 accuracy on the sign inference task as compared to 90.8 accuracy using a state-of-the-art cycle-based method - moreover, our method runs in 40 seconds as compared to 10,000 seconds for the cycle-based method. We consider the problem of link prediction in signed networks. Such networks arise on the web in a variety of ways when users can implicitly or explicitly tag their relationship with other users as positive or negative. The signed links thus created reflect social attitudes of the users towards each other in terms of friendship or trust. Our first contribution is to show how any quantitative measure of social imbalance in a network can be used to derive a link prediction algorithm. Our framework allows us to reinterpret some existing algorithms as well as derive new ones. Second, we extend the approach of (2010) by presenting a supervised machine learning based link prediction method that uses features derived from longer cycles in the network. The supervised method outperforms all previous approaches on 3 networks drawn from sources such as Epinions, Slashdot and Wikipedia. The supervised approach easily scales to these networks, the largest of which has 132k nodes and 841k edges. Most real-world networks have an overwhelmingly large proportion of positive edges and it is therefore easy to get a high overall accuracy at the cost of a high false positive rate. We see that our supervised method not only achieves good accuracy for sign prediction but is also especially effective in lowering the false positive rate. We study the problem of labeling the edges of a social network graph (e.g., acquaintance connections in Facebook) as either positive (i.e., trust, true friendship) or negative (i.e., distrust, possible frenemy) relations. Such signed relations provide much stronger signal in tying the behavior of online users than the unipolar Homophily effect, yet are largely unavailable as most social graphs only contain unsigned edges. We show the surprising fact that it is possible to infer signed social ties with good accuracy solely based on users' behavior of decision making (or using only a small fraction of supervision information) via unsupervised and semi-supervised algorithms. This work hereby makes it possible to turn an unsigned acquaintance network (e.g. Facebook, Myspace) into a signed trust-distrust network (e.g. Epinion, Slashdot). Our results are based on a mixed effects framework that simultaneously captures users' behavior, social interactions as well as the interplay between the two. The framework includes a series of latent factor models and it also encodes the principles of balance and status from Social psychology. Experiments on Epinion and Yahoo! Pulse networks illustrate that (1) signed social ties can be predicted with high-accuracy even in fully unsupervised settings, and (2) the predicted signed ties are significantly more useful for social behavior prediction than simple Homophily. A class of networks are those with both positive and negative links. In this manuscript, we studied the interplay between positive and negative ties on mesoscopic level of these networks, i.e., their community structure. A community is considered as a tightly interconnected group of actors; therefore, it does not borrow any assumption from balance theory and merely uses the well-known assumption in the community detection literature. We found that if one detects the communities based on only positive relations (by ignoring the negative ones), the majority of negative relations are already placed between the communities. In other words, negative ties do not have a major role in community formation of signed networks. Moreover, regarding the internal negative ties, we proved that most unbalanced communities are maximally balanced, and hence they cannot be partitioned into k nonempty sub-clusters with higher balancedness (k≥2). Furthermore, we showed that although the mediator triad ++- (hostile-mediator-hostile) is underrepresented, it constitutes a considerable portion of triadic relations among communities. Hence, mediator triads should not be ignored by community detection and clustering algorithms. As a result, if one uses a clustering algorithm that operates merely based on social balance, mesoscopic structure of signed networks significantly remains hidden.