What the study found
The study proposes a maximal balanced quasi-clique (MBQC) model for signed graphs and formulates the problem of enumerating all maximal balanced quasi-cliques. The authors report that they prove this enumeration problem is NP-hard and develop a branch-and-bound algorithm with additional pruning techniques.
Why the authors say this matters
The authors say this is relevant because quasi-clique models have mainly been designed for unsigned graphs, while many real-world networks are signed graphs with positive and negative edges. The study suggests the MBQC model is intended to match both quasi-completeness and structural balance theory for signed graphs.
What the researchers tested
The researchers introduced the MBQC model for signed graphs, proved the related enumeration problem is NP-hard, and designed a branch-and-bound algorithm to enumerate all maximal balanced quasi-cliques. They also added carefully crafted techniques to prune unpromising search spaces and tested the approach on real-world datasets.
What worked and what didn't
The abstract states that extensive experiments on real-world datasets demonstrated the efficiency, scalability, and effectiveness of the MBQC model and algorithms. It also states that the algorithm was further optimized with pruning techniques, but it does not provide comparative details or specific cases where the approach did not work.
What to keep in mind
The available summary does not describe detailed experimental settings, dataset names, or quantitative results. It also does not state specific limitations beyond noting that the enumeration problem is NP-hard.
Key points
- The paper proposes a maximal balanced quasi-clique model for signed graphs.
- The authors say the model aligns quasi-completeness with structural balance theory.
- The enumeration problem for maximal balanced quasi-cliques is proved NP-hard.
- A branch-and-bound algorithm with pruning techniques was developed to enumerate all maximal balanced quasi-cliques.
- Experiments on real-world datasets are reported to show efficiency, scalability, and effectiveness.
Disclosure
- Research title:
- Algorithm enumerates maximal balanced quasi-cliques in signed graphs
- Publication date:
- 2026-04-07
- DOI:
- 10.1145/3806834
- OpenAlex record:
- View
Get the weekly research newsletter
Stay current with peer-reviewed research without reading academic papers — one filtered digest, every Friday.