Prediction and Clustering in Signed Networks: A Local to Global
  Perspective
  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.
