ABCD: Algorithm for Balanced Component Discovery in Signed Networks

The largest balanced element in signed graphs plays a vital role in helping researchers understand the fundamental structure of the graph, as it reveals valuable information about the complex relationships between vertices in the network. The challenge is an NP-hard problem; there is no current baseline to evaluate state-of-the-art signed graphs derived from real networks. A scalable state-of-the-art approach for the maximum balanced subgraph detection in the network of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">any</i> size is proposed. This approach finds the largest balanced subgraph by considering only the top <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> balanced states with the lowest frustration index. The ABCD method efficiently selects the largest possible subset from an extensive signed network with millions of vertices and edges, and the size of the discovered subset is double that of the state-of-the-art in a similar time frame.