Social Balance Theory for Signed Network Analysis : A Global Approach

Social Balance Theory for Signed Network Analysis : A Global Approach

Project Summary

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 project, we exploit both local as well as global aspects of social balance theory for two fundamental problems: sign prediction and clustering.

Project Description

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

    local_pattern

    Local patterns like triads and cycles can be either balanced or unbalanced. As people believe that balanced patterns are tend to present more than unbalanced patterns, MOIs predict the sign of edges by encoding such local balance information.

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

    An illustrative example that the adjacency matrix of a complete weakly-balaned network is low rank.

    sign_pred_result

    By considering global structure of signed network using our low rank modeling approach (LR-ALS), accuracy of sign prediction could be improved among various datasets.

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

    LR_clustering_result

    By performing matrix completion before clustering (LR-SVP), one can derive a more accurate clustering result than traditional clustering method with signed Laplacian, in both non-noisy and noisy cases.

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

    sign_clustering_result

    A clustering on a massive 20-balanced signed graph derived from our multilevel clustering algorithm. Most positive edges are within clusters (left) and most negative edges are between clusters (right).

Main Publications