BridgeCut: A New Algorithm for Balanced Partitioning of Signed Networks

Abstract Structural analysis of signed networks is an important issue with many applications in the field of complex networks. In this context, balance theory is the main framework that leads naturally to partitioning balanced graphs into two parts with entirely positive edges in each part and only negative edges between them. However, real-world signed networks rarely have a perfectly balanced structure, and detecting near-balanced partitions can be formulated as an optimization problem with different objective functions. However, as an NP-Hard problem with many applications, different approaches have been proposed to it. Nevertheless, many methods ignore negative links and divide the graph into parts considering only positive edges. Emphasizing the importance of negative links and their properties in the partition scheme, we present a new approach, inspired by the Girvan-Newman community detection algorithm, called BridgeCut, in which the negative edges as the bridge set between the two parts are determined in a constructive algorithm. Sorted by edge betweenness, every negative edge is evaluated whether to be selected as a member of the bridge set or not, based on a balance improvement index. Analyzing the time complexity of this algorithm, it is implemented on some benchmark datasets and the results confirm its satisfactory performance. We further extend some measures to evaluate signed links' properties in relevance to their position and role in the whole structure.

BridgeCut: A New Algorithm for Balanced Partitioning of Signed Networks Institutional Repository Document