Maximal Balanced Quasi-Clique Enumeration in Signed Graphs
ACM Transactions on Knowledge Discovery from Data · 30.06.2026 · 20 (5) · 1-36
DOI: 10.1145/3806834 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Knowledge Discovery from Data, online erschienen am 20.05.2026. Verfasst von Jie Gao und 4 weiteren Autor:innen. Die Arbeit nennt 52 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: UK Research and Innovation, EU Horizon Europe.
Abstract (Originalsprache)
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 modeled 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 \( (\gamma_{1},\gamma_{2}) \) -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 MBQCs 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 MBQCs 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.
Förderung
- UK Research and Innovation
- EU Horizon Europe
Zitieren
APA
Gao, J., Hu, J., Hao, F., Min, G., & Liu, L. (2026). Maximal Balanced Quasi-Clique Enumeration in Signed Graphs. ACM Transactions on Knowledge Discovery from Data, 20(5), 1-36. https://doi.org/10.1145/3806834
Vancouver
Gao J, Hu J, Hao F, Min G, Liu L. Maximal Balanced Quasi-Clique Enumeration in Signed Graphs. ACM Transactions on Knowledge Discovery from Data. 2026;20(5):1-36. doi:10.1145/3806834
BibTeX
@article{Gao2026,
author = {Gao, Jie and Hu, Jia and Hao, Fei and Min, Geyong and Liu, Lei},
title = {Maximal Balanced Quasi-Clique Enumeration in Signed Graphs},
journal = {ACM Transactions on Knowledge Discovery from Data},
year = {2026},
volume = {20},
number = {5},
pages = {1--36},
doi = {10.1145/3806834}
}
EUVIMED