What the study found
The study proposes a maximal balanced (gamma1, gamma2)-quasi-clique (MBQC) model for signed graphs, where signed graphs are networks with positive and negative edges. The authors state that this model preserves quasi-completeness and aligns with structural balance theory.
Why the authors say this matters
The authors say this matters because existing quasi-clique definitions and algorithms were designed for unsigned graphs, while many real-world networks are signed graphs. The study suggests MBQC provides a quasi-clique model tailored to signed graphs.
What the researchers tested
The researchers formulated the problem of enumerating MBQCs in a signed graph and proved it is NP-hard, meaning it is computationally difficult in general. They then developed a branch-and-bound algorithm, a search method that systematically explores possibilities while pruning unlikely ones, with additional techniques to improve efficiency.
What worked and what didn't
The abstract reports that the proposed algorithms were optimized with several carefully crafted pruning techniques. It also says extensive experiments on real-world datasets demonstrated the efficiency, scalability, and effectiveness of the MBQC model and algorithms, but it does not give specific numerical comparisons in the abstract.
What to keep in mind
The abstract does not provide detailed experimental results, dataset descriptions, or exact performance measures. It also states that the enumeration problem is NP-hard, so the task is difficult in general even though the proposed method is reported to work well in experiments.
Key points
- The paper proposes a maximal balanced (gamma1, gamma2)-quasi-clique model for signed graphs.
- Signed graphs are described as networks with positive and negative edges.
- The authors say the model preserves quasi-completeness and fits structural balance theory.
- MBQC enumeration is proved to be NP-hard.
- A branch-and-bound algorithm with pruning techniques was developed and tested on real-world datasets.
Disclosure
- Research title:
- Balanced quasi-clique model for signed graphs
- Authors:
- Jie Gao, Jia Hu, Fei Hao, Geyong Min, Lei Liu
- Institutions:
- Shaanxi Normal University, Shandong University, University of Exeter, University of Exeter, University of Exeter
- Publication date:
- 2026-04-07
- DOI:
- 10.1145/3806834
- OpenAlex record:
- View
Get the weekly research newsletter
Stay current with scholarly research without reading academic papers — one filtered digest, every Friday.