A graph with positive and negative signs on the edges is called a signed graph. A signed graph (network) is balanced if its set of vertices can be partitioned into two subsets such that each negative (positive) edge joins vertices belonging to different subsets (same subset) [1]. If a signed network satisfies the same condition when partitioned into k subsets, it is clusterable (k-balanced) [2]. Signed networks representing real data often do not satisfy these conditions [3]. This motivates analyzing them based on their distance to balance and clusterability. Among different methods for measuring such distance is the minimum number of edges whose removal makes a network balanced (frustration index L(G) [4]), k-balanced for the given value k (k-clusterability index Ck(G) [5]) or clusterable (clusterability index C(G) [6]). These measures are complementary, giving different perspectives on balance as a multi-faceted property of signed networks. Fig. 1(A) shows an example signed graph in which the dotted (solid) lines represent negative (positive) edges. Balance can be evaluated using 3-cycles (B), bi-partitioning (C), or k-partitioning (D). The first approach, (Fig. 1B), involves identifying triangle 1-4-5 as unbalanced and triangle 1-3-4 as balanced and only provides limited insight into the overall structure. The second approach, (Fig. 1C), involves finding a bi-partitioning of vertices {{1, 2, 3}, {4, 5}} (shown by green and purple colors in Fig. 1C) which minimizes the total number of intra-group negative and inter-group positive edges to 1 (L(G) = 1). The last approach, (Fig. 1D), involves finding an optimal k-partitioning for the vertices {{1, 2, 3}, {4}, {5}} which satisfies the conditions of generalized balance (C(G) = 0, k∗ = 3).
