EUVIMEDEUVIMED entdecken
Crossref

Aggregating Maximal Cliques in Real-World Graphs

Noga Alon, Sabyasachi Basu, Shweta Jain, Haim Kaplan, Jakub Łącki, Blair D. Sullivan

Proceedings of the VLDB Endowment · 01.05.2026 · 19 (9) · 2183-2195

DOI: 10.14778/3819518.3819543 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 19.08.2026. Verfasst von Noga Alon und 5 weiteren Autor:innen. Die Arbeit nennt 54 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Maximal clique enumeration is a fundamental graph mining task, but its utility is often limited by computational intractability and highly redundant output. To address these challenges, we introduce ρ-dense aggregators , a novel approach that succinctly captures maximal clique structure. Instead of listing all cliques, we identify a small collection of clusters with edge density at least ρ that collectively contain every maximal clique. In contrast to maximal clique enumeration, we prove that for all ρ < 1, every graph admits a ρ -dense aggregator of sub-exponential size, n O (log 1 / ρ n ), and provide an algorithm achieving this bound. For graphs with bounded degeneracy, a typical characteristic of real-world networks, our algorithm runs in near-linear time and produces near-linear size aggregators. We also establish a matching lower bound on aggregator size, proving our results are essentially tight. In an empirical evaluation on real-world networks, we demonstrate significant practical benefits for the use of aggregators: our algorithm is consistently faster than the state-of-the-art clique enumeration algorithm, with median speedups over 2.5× for ρ = 0.1 (and over 300× in an extreme case), while delivering a much more concise structural summary.

Zitieren

APA

Alon, N., Basu, S., Jain, S., Kaplan, H., Łącki, J., & Sullivan, B. D. (2026). Aggregating Maximal Cliques in Real-World Graphs. Proceedings of the VLDB Endowment, 19(9), 2183-2195. https://doi.org/10.14778/3819518.3819543

Vancouver

Alon N, Basu S, Jain S, Kaplan H, Łącki J, Sullivan BD. Aggregating Maximal Cliques in Real-World Graphs. Proceedings of the VLDB Endowment. 2026;19(9):2183-2195. doi:10.14778/3819518.3819543

BibTeX
@article{Alon2026,
  author = {Alon, Noga and Basu, Sabyasachi and Jain, Shweta and Kaplan, Haim and Łącki, Jakub and Sullivan, Blair D.},
  title = {Aggregating Maximal Cliques in Real-World Graphs},
  journal = {Proceedings of the VLDB Endowment},
  year = {2026},
  volume = {19},
  number = {9},
  pages = {2183--2195},
  doi = {10.14778/3819518.3819543}
}
Kostenlos starten →