Identifying Large Structural Balanced Cliques in Signed Graphs

Signed graphs have been used to capture the polarity of relationships through positive/negative edge signs. In this paper, we consider balanced cliques — a clique is balanced if its vertex set $C$ can be partitioned into $C_{L}$ and $C_{R}$ such that all negative edges are between $C_{L}$ and $C_{R}$ — and study the problems of maximum balanced clique computation and large balanced clique enumeration. Our main idea is a novel graph reduction that transforms a balanced clique problem over a signed graph $G$ to problems over small subgraphs of $G$ . Specifically, for each vertex $u$ in $G$ , we extract the subgraph $G_{u}$ of $G$ induced by $V_{L} \cup V_{R}$ ; $V_{L}$ is $u$ and $u$ 's positive neighbors while $V_{R}$ is $u$ 's negative neighbors. Then, we remove from $G_{u}$ all positive edges between $V_{L}$ and $V_{R}$ and all negative edges between vertices of the same set; denote the resulting graph of discarding edge signs as $g_{u}$ . We show that all balanced cliques containing $u$ in $G$ can be found by processing $g_{u}$ . Due to the small size and no edge signs, large cliques containing $u$ in $g_{u}$ can be efficiently identified. Experimental results on real signed graphs demonstrated the advantages of our techniques.