Prediction and Clustering in Signed Networks: A Local to Global Perspective

Abstract

The study of social networks is a burgeoning research area. However, most existing work deals with networks that simply encode whether relationships exist or not. In contrast, relationships in signed networks can be positive ("like", "trust") or negative ("dislike", "distrust"). The theory of social balance shows that signed networks tend to conform to some local patterns that, in turn, induce certain global characteristics. In this paper, we exploit both local as well as global aspects of social balance theory for two fundamental problems in the analysis of signed networks: sign prediction and clustering. Motivated by local patterns of social balance, we first propose two families of sign prediction methods: measures of social imbalance (MOIs), and supervised learning using high order cycles (HOCs). These methods predict signs of edges based on triangles and \ell-cycles for relatively small values of \ell. Interestingly, by examining measures of social imbalance, we show that the classic Katz measure, which is used widely in unsigned link prediction, actually has a balance theoretic interpretation when applied to signed networks. Furthermore, motivated by the global structure of balanced networks, we propose an effective low rank modeling approach for both sign prediction and clustering. For the low rank modeling approach, we provide theoretical performance guarantees via convex relaxations, scale it up to large problem sizes using a matrix factorization based algorithm, and provide extensive experimental validation including comparisons with local approaches. Our experimental results indicate that, by adopting a more global viewpoint of balance structure, we get significant performance and computational gains in prediction and clustering tasks on signed networks. Our work therefore highlights the usefulness of the global aspect of balance theory for the analysis of signed networks.

References in corpus (1)

• Modularity and community structure in networks

Cited by in corpus (16)

• Balance in signed networks
• PU Learning for Matrix Completion
• Node and layer eigenvector centralities for multiplex networks
• Clustering with Noisy Queries
• Signed Graph Analysis for the Interpretation of Voting Behavior
• Classification from Pairwise Similarity and Unlabeled Data
• Regularized spectral methods for clustering signed networks
• Advances in Scaling Community Discovery Methods for Signed Graph Networks
• Fast Low-Rank Matrix Estimation without the Condition Number
• Evaluating balance on social networks from their simple cycles
• Accelerated and Inexact Soft-Impute for Large-Scale Matrix and Tensor Completion
• Efficient Inexact Proximal Gradient Algorithm for Nonconvex Problems
• SNE: Signed Network Embedding
• Negative Link Prediction in Social Media
• Learning of Generalized Low-Rank Models: A Greedy Approach
• Investigating Negative Interactions in Multiplex Networks: A Mutual Information Approach