Social Balance Theory for Signed Network Analysis : A Global Approach
Primary researcher(s): Kai-Yang Chiang, Cho-Jui Hsieh, Nagarajan Natarajan, Inderjit Dhillon, Ambuj Tewari, Joyce Whang
Project SummaryThe 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 project, we exploit both local as well as global aspects of social balance theory for two fundamental problems: sign prediction and clustering.
- Local Methods for Sign Prediction
Based on the balance theory in social networks, we propose measures of social imbalance (MOIs), a simple sign prediction method for a given measure that quantifies the degree of imbalance. While the imbalance measure based on triads has already been studied, the sign patterns of local cycles can be also used to obtain a more general measure of imbalance. As a result, an infinite-order version of the measure for sign prediction leads to a familiar proximity measure for (unsigned) networks called Katz measure, which establishes a connection between link prediction in unsigned networks and sign prediction in signed network.
- Global Methods for Sign Prediction — Low Rank Modeling
We developed a completely global approach based on the global structure of balanced signed networks. We appeal to the global clusterability of complete weakly balanced networks to develop our global approach. Broadly, we show that such networks have low rank adjacency matrices, so that we can solve the sign prediction problem by reducing it to a low rank matrix completion problem.
- Clustering Signed Networks by Matrix Completion:
The low rank modeling approach can also be used for the clustering of signed networks. Our clustering method proceeds as follows. First, we use a low-rank matrix completion algorithm on its adjacency matrix. Then we cluster the top-k eigenvectors of the completed matrix using any feature-based clustering algorithm. By doing so, we show that under the same assumptions that guarantee the recovery of signed networks, the true clusters can be identified from the top-k eigenvectors.
- Clustering Signed Networks using Balanced Normalized Cut:
We investigated spectral clustering algorithms for signed graphs. We show that there is a fundamental weakness when we directly extend the signed Laplacian to the k-way clustering problem. To overcome this weakness, we formulate new k-way objectives for signed networks. In particular, we propose a criterion that is analogous to the normalized cut, called balance normalized cut, which is not only theoretically sound but also experimentally eﬀective in k-way clustering. In addition, we prove that these objectives are equivalent to weighted kernel k-means objectives by choosing an appropriate kernel matrix. Employing this equivalence, we develop a multilevel clustering framework for signed networks.
- Prediction and Clustering in Signed Networks: A Local to Global Perspective (pdf)
K. Chiang, C. Hsieh, N. Natarajan, A. Tewari, I. Dhillon.
Journal of Machine Learning Research (JMLR) 15, pp. 1177-1213, March 2014.
- Scalable Clustering of Signed Networks using Balance Normalized Cut (pdf, slides)
K. Chiang, J. Whang, I. Dhillon.
In ACM Conference on Information and Knowledge Management (CIKM), pp. 615-624, October 2012. (Oral)
- Low-Rank Modeling of Signed Networks (pdf)
C. Hsieh, K. Chiang, I. Dhillon.
In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2012.
- Exploiting Longer Walks for Link Prediction in Signed Network (pdf)
K. Chiang, I. Dhillon, N. Natarajan, A. Tewari.
In ACM Conference on Information and Knowledge Management (CIKM), pp. 1157-1162, October 2011.