Maximal Balanced Quasi-Clique Enumeration in Signed Graphs

Quasi-clique is one of the most fundamental models for characterizing cohesive subgraphs in network analysis. However, existing quasi-clique definitions and identification algorithms are designed for unsigned graphs, while many real-world networks are modelled as signed graphs with positive and negative edges representing cooperative and adversarial interactions between entities. Therefore, it remains an open problem to define a quasi-clique model tailored for signed graphs. Motivated by this, we propose the maximal balanced quasi-clique (MBQC) model, which not only preserves the essence of quasi-completeness but also aligns with the foremost structural balance theory for signed graphs. Specifically, we formulate the problem of maximal balanced quasi-cliques enumeration in a given signed graph and prove its NP-hardness. To address this problem, we devise a novel branch-and-bound algorithm to efficiently enumerate all maximal balanced quasi-cliques in a signed graph, which is further optimized with several carefully-crafted techniques to prune unpromising search spaces and enhance enumeration efficiency. Extensive experiments on real-world datasets demonstrate the efficiency, scalability and effectiveness of our MBQC model and algorithms.