Scaling frustration index and balanced state discovery for real signed graphs

Abstract

—Structural balance modeling for signed graph networks presents how to model the sources of conflicts. The state-of-the-art has focused on computing the frustration index of a signed graph as a critical step toward solving problems in social and sensor networks and for scientific modeling. However, the proposed approaches do not scale to modern large, sparse signed networks. Also, they do not address that there is more than one way in some networks to reach a consensus with the minimum number of edge-sign switches needed. We propose an efficient, balanced state discovery heuristic algorithm that will discover the nearest balanced state for any size of the graph network and approximate the frustration of the network. The speedup of the proposed method is around 300 times faster than the state-of-the-art for signed graphs with hundreds of thousands of edges. The technique successfully scales to find the balanced states and the frustration index of networks with millions of nodes and edges in real time where state-of-the-art fails.