EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Axioms for clustering simple unweighted graphs: No impossibility result

James Willson, Tandy Warnow

PLOS Complex Systems · 2024

DOI: 10.1371/journal.pcsy.0000011 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PLOS Complex Systems, 2024. Verfasst von James Willson und 1 weiteren Autor:innen. Die Arbeit nennt 21 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In 2002, Kleinberg proposed three axioms for distance-based clustering, and proved that it was impossible for a clustering method to satisfy all three. While there has been much subsequent work examining and modifying these axioms for distance-based clustering, little work has been done to explore axioms relevant to the graph partitioning problem when the graph is unweighted and given without a distance matrix. Here, we propose and explore axioms for graph partitioning for this case, including modifications of Kleinberg’s axioms and three others: two axioms relevant to the “Resolution Limit” and one addressing well-connectedness. We prove that clustering under the Constant Potts Model satisfies all the axioms, while Modularity clustering and iterative k -core both fail many axioms we pose. These theoretical properties of the clustering methods are relevant both for theoretical investigation as well as to practitioners considering which methods to use for their domain science studies.

Zitieren

APA

Willson, J., & Warnow, T. (2024). Axioms for clustering simple unweighted graphs: No impossibility result. PLOS Complex Systems. https://doi.org/10.1371/journal.pcsy.0000011

Vancouver

Willson J, Warnow T. Axioms for clustering simple unweighted graphs: No impossibility result. PLOS Complex Systems. 2024. doi:10.1371/journal.pcsy.0000011

BibTeX
@article{Willson2024,
  author = {Willson, James and Warnow, Tandy},
  title = {Axioms for clustering simple unweighted graphs: No impossibility result},
  journal = {PLOS Complex Systems},
  year = {2024},
  doi = {10.1371/journal.pcsy.0000011}
}
Kostenlos starten →