EUVIMEDEUVIMED entdecken
Crossref

Exact and rapid linear clustering of networks with dynamic programming

Alice Patania, Antoine Allard, Jean-Gabriel Young

Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · 2023-07 · 479 (2275)

DOI: 10.1098/rspa.2023.0159 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, online erschienen am 19.07.2023. Verfasst von Alice Patania und 2 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 50 Literaturangaben. Gefördert von: James S. McDonnell Foundation, Fonds de recherche du Québec – Nature et technologies, Canada First Research Excellence Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the problem of clustering networks whose nodes have imputed or physical positions in a single dimension, for example prestige hierarchies or the similarity dimension of hyperbolic embeddings. Existing algorithms, such as the critical gap method and other greedy strategies, only offer approximate solutions to this problem. Here, we introduce a dynamic programming approach that returns provably optimal solutions in polynomial time— O ( n 2 ) steps—for a broad class of clustering objectives. We demonstrate the algorithm through applications to synthetic and empirical networks, and show that it outperforms existing heuristics by a significant margin, with a similar execution time.

Förderung

  • James S. McDonnell Foundation
  • Fonds de recherche du Québec – Nature et technologies
  • Canada First Research Excellence Fund
  • Natural Sciences and Engineering Research Council of Canada

Zitieren

APA

Patania, A., Allard, A., & Young, J. (2023). Exact and rapid linear clustering of networks with dynamic programming. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 479(2275). https://doi.org/10.1098/rspa.2023.0159

Vancouver

Patania A, Allard A, Young J. Exact and rapid linear clustering of networks with dynamic programming. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2023;479(2275). doi:10.1098/rspa.2023.0159

BibTeX
@article{Patania2023,
  author = {Patania, Alice and Allard, Antoine and Young, Jean-Gabriel},
  title = {Exact and rapid linear clustering of networks with dynamic programming},
  journal = {Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences},
  year = {2023},
  volume = {479},
  number = {2275},
  doi = {10.1098/rspa.2023.0159}
}
Kostenlos starten →