Keynote: Structural analysis of signed networks by optimally clustering them using integer programming models

Presentation Slides (PDF)

Abstract

A signed network is one with positive and negative edges. We analyze signed networks from the perspective of balance theory. A signed network is strongly balanced (weakly balanced) if its nodes can be partitioned into k≤2 clusters (k clusters) such that positive edges are within the clusters and negative edges are between the clusters. We use mathematical programming models to optimally cluster the nodes of a network by minimizing the total number of intra-cluster negative and inter-cluster positive edges.

These optimization models cluster a network into clusters of nodes that are internally cohesive and mutually divisive. The optimal partitions of a network allow us to quantify the extent to which it is weakly or strongly balanced. In other words, we measure the distance of a network to weak and strong balance in terms of the minimum number of edges whose sign change leads to weak and strong balance respectively.

The concepts of strong and weak balance in signed networks can be extended to applications beyond the classic friend-enemy interpretation of balance theory in the social context. Through extensive computational analysis, we explore common structural patterns across a range of networks representing philosophers and Wikipedia editors to Bitcoin traders and US Congress legislators. This talk provides an overview of using integer programming to develop exact graph optimization models and algorithms for signed networks. A wide range of use cases will be discussed for signed networks from sociology, biology, chemistry and physics to finance, international relations, and political science.

Relevant publications

arxiv.org/abs/1509.04037 arxiv.org/abs/1710.09876 arxiv.org/abs/1611.09030 arxiv.org/abs/1712.04628 arxiv.org/abs/1906.01696 arxiv.org/abs/2105.01913 arxiv.org/abs/2005.09925