EUVIMEDDescubrir EUVIMED
Crossref

Rank-based linkage I: triplet comparisons and oriented simplicial complexes

R. W. R. Darling, Will Grilliette, Adam Logan

Compositionality · 2026-03-20 · Volume 8 (2026)

DOI: 10.46298/compositionality-8-2 ↗

At a glance

Journal article in Compositionality, published online on 2026-03-20. Written by R. W. R. Darling and 2 co-authors.

ResumenDatos bibliográficosCiteRelated studies

Abstract (original language)

Rank-based linkage is a new tool for summarizing a collection $S$ of objects according to their relationships. These objects are not mapped to vectors, and ``similarity'' between objects need be neither numerical nor symmetrical. All an object needs to do is rank nearby objects by similarity to itself, using a Comparator which is transitive, but need not be consistent with any metric on the whole set. Call this a ranking system on $S$. Rank-based linkage is applied to the $K$-nearest neighbor digraph derived from a ranking system. Computations occur on a 2-dimensional abstract oriented simplicial complex whose faces are among the points, edges, and triangles of the line graph of the undirected $K$-nearest neighbor graph on $S$. In $|S| K^2$ steps it builds an edge-weighted linkage graph $(S, \mathcal{L}, σ)$ where $σ(\{x, y\})$ is called the in-sway between objects $x$ and $y$. Take $\mathcal{L}_t$ to be the links whose in-sway is at least $t$, and partition $S$ into components of the graph $(S, \mathcal{L}_t)$, for varying $t$. Rank-based linkage is a functor from a category of ``out-ordered'' digraphs to a category of partitioned sets, with the practical consequence that augmenting the set of objects in a rank-respectful way gives a fresh clustering which does not ``rip apart'' the previous one. The same holds for single linkage clustering in the metric space context, but not for typical optimization-based methods. Orientation sheaves play in a fundamental role and ensure that partially overlapping data sets can be ``glued'' together. Open combinatorial problems are presented in the last section. 39 pages, 13 figures

Cite

APA

Darling, R. W. R., Grilliette, W., & Logan, A. (2026). Rank-based linkage I: triplet comparisons and oriented simplicial complexes. Compositionality, Volume 8 (2026). https://doi.org/10.46298/compositionality-8-2

Vancouver

Darling RWR, Grilliette W, Logan A. Rank-based linkage I: triplet comparisons and oriented simplicial complexes. Compositionality. 2026;Volume 8 (2026). doi:10.46298/compositionality-8-2

BibTeX
@article{Darling2026,
  author = {Darling, R. W. R. and Grilliette, Will and Logan, Adam},
  title = {Rank-based linkage I: triplet comparisons and oriented simplicial complexes},
  journal = {Compositionality},
  year = {2026},
  volume = {Volume 8 (2026)},
  doi = {10.46298/compositionality-8-2}
}
Start for free →