Axioms for clustering simple unweighted graphs: No impossibility result
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).
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}
}
EUVIMED