SLINK: An optimally efficient algorithm for the single-link cluster method

1973/01/01 by R. Sibson, Robin Sibson · 55 citations
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Theoretical and Computational Physics

paper · pdf · doi:10.1093/comjnl/16.1.30

Abstract

The SLINK algorithm carries out single-link (nearest-neighbour) cluster analysis on an arbitrary dissimilarity coefficient and provides a representation of the resultant dendrogram which can readily be converted into the usual tree-diagram. The algorithm achieves the theoretical order-of-magnitude bounds for both compactness of storage and speed of operation, and makes the application of the single-link method feasible for a number of OTU's well into the range 103 to 104. The algorithm is easily programmable in a variety of languages including FORTRAN.

Cited by

• Enhancing Noise Resilience in Face Clustering via Sparse Differential Transformer
• Methods of Hierarchical Clustering
• Big-Data Clustering: K-Means or K-Indicators?
• Hyperbolic Continuous Structural Entropy for Hierarchical Clustering
• Learning to Cluster Faces on an Affinity Graph
• Adaptive Correlated Monte Carlo for Contextual Categorical Sequence\n Generation
• A Groupwise Approach for Inferring Heterogeneous Treatment Effects in Causal Inference
• A Parameter-free Affinity Based Clustering
• WebFace260M: A Benchmark Unveiling the Power of Million-Scale Deep Face Recognition
• ELKI: A large open-source library for data analysis - ELKI Release 0.7.5 "Heidelberg"
• Rediscovering Recurring Routing Results
• A Linkage-based Doubly Imbalanced Graph Learning Framework for Face Clustering
• Distributed clustering in partially overlapping feature spaces
• Hybrid Graph Embeddings and Louvain Algorithm for Unsupervised Community Detection
• Structure-Aware Face Clustering on a Large-Scale Graph with \bf10⁷ Nodes
• Topological graph clustering with thin position
• Ultrametric Component Analysis with Application to Analysis of Text and\n of Emotion
• Ontology from Local Hierarchical Structure in Text
• Clustering with Temporal Constraints on Spatio-Temporal Data of Human Mobility
• Learning to Cluster Faces via Transformer
• Scene Text Detection and Recognition: The Deep Learning Era
• FaceGCD: Generalized Face Discovery via Dynamic Prefix Generation
• The NOESIS Network-Oriented Exploration, Simulation, and Induction System
• Multi-Community Spectral Clustering for Geometric Graphs
• Learned Sectors: A fundamentals-driven sector reclassification project
• Coarse-to-Fine Curriculum Learning
• OPTICS
• Comparison three methods of clustering: k-means, spectral clustering and hierarchical clustering
• Unsupervised Action Proposal Ranking through Proposal Recombination
• Density-Based Clustering with Kernel Diffusion
• SEQOPTICS: a protein sequence clustering system. [europepmc]
• Efficient algorithms for fast integration on large data sets from multiple sources. [europepmc]
• Clustering rfam 10.1: clans, families, and classes. [europepmc]
• Integral-geometry characterization of photobiomodulation effects on retinal vessel morphology. [europepmc]
• TE-Tracker: systematic identification of transposition events through whole-genome resequencing. [europepmc]
• A density-based clustering approach for identifying overlapping protein complexes with functional preferences. [europepmc]
• Inhibitory and excitatory axon terminals share a common nano-architecture of their Cav2.1 (P/Q-type) Ca(2+) channels. [europepmc]
• Robust tracking and quantification of C. elegans body shape and locomotion through coiling, entanglement, and omega bends. [europepmc]
• Structural Study of Heterogeneous Biological Samples by Cryoelectron Microscopy and Image Processing. [europepmc]
• Automatic detection and decoding of honey bee waggle dances. [europepmc]
• Divisive hierarchical maximum likelihood clustering. [europepmc]
• A Literature Review: Geometric Methods and Their Applications in Human-Related Analysis. [europepmc]
• The Application of Deep Learning in Cancer Prognosis Prediction. [europepmc]
• Data mining application to healthcare fraud detection: a two-step unsupervised clustering method for outlier detection with administrative databases. [europepmc]
• A community-driven resource for genomic epidemiology and antimicrobial resistance prediction of Neisseria gonorrhoeae at Pathogenwatch. [europepmc]
• A global resource for genomic predictions of antimicrobial resistance and surveillance of Salmonella Typhi at pathogenwatch. [europepmc]
• CATBOSS: Cluster Analysis of Trajectories Based on Segment Splitting. [europepmc]
• MulticlusterKDE: a new algorithm for clustering based on multivariate kernel density estimation. [europepmc]
• Machine Learning Advances in Microbiology: A Review of Methods and Applications. [europepmc]
• 3-D breast nodule detection on automated breast ultrasound using faster region-based convolutional neural networks and U-Net. [europepmc]
• Antimicrobial Susceptibility Profiles of Commensal Escherichia coli Isolates from Chickens in Hungarian Poultry Farms Between 2022 and 2023. [europepmc]
• Antimicrobial Susceptibility Profiles of Commensal Enterococcus spp. Isolates from Chickens in Hungarian Poultry Farms Between 2022 and 2023. [europepmc]
• Antimicrobial Susceptibility Profiles of Commensal Staphylococcus spp. Isolates from Chickens in Hungarian Poultry Farms Between 2022 and 2023. [europepmc]
• Antimicrobial Susceptibility Profiles of Commensal Staphylococcus spp. Isolates from Turkeys in Hungarian Poultry Farms Between 2022 and 2023. [europepmc]
• Ultra-high-scale cytometry-based cellular interaction mapping. [europepmc]

Related

• cuSLINK: Single-linkage Agglomerative Clustering on the GPU
• Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
• Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering
• Weakest link pruning of a dendrogram
• A density-sensitive hierarchical clustering method