A clustering algorithm based on graph connectivity

By Erez Hartuv, Ron Shamir. Information Processing Letters, 2000

545 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/c4f70586901303d76523c49b7cc5b7dde1ac0246

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Signal Processing

Citations in the corpus

A Comprehensive Survey of Clustering Algorithms (2015, background): “For more detailed information about this kind of clustering algorithms, you can refer to [1,20,46–49].”
Graphlet-based measures are suitable for biological network comparison (2013, background): “…of the whole network at once, thus artificially decreasing its density D ow nloaded from https://academ ic.oup.com /bioinform atics/article-abstract/29/4/483/199955 by guest on 16 Septem ber 2019 Highly Connected Subgraphs algorithm (Hartuv and Shamir, 2000) to find dense subregions of HS network.”
Functional topology in a network of protein interactions (2004, methodology): “A highly connected subgraph is itself a graph, in which the minimum number of edges whose removal disconnects the graph is greater than n/2, where n is the number of nodes in the subgraph (Hartuv and Shamir, 2000).”
Mining coherent dense subgraphs across massive biological networks for functional discovery (2005, methodology): “MODES is developed based on HCS (Mining Highly Connected Subgraphs) (Hartuv and Shamir, 2000), with two new features: (1) MODES is more efficient in identifying dense subgraphs; and more importantly, (2) MODES can discover overlapping subgraphs.”
CLICK and EXPANDER: a system for clustering and visualizing gene expression data (2003, methodology): “The algorithm builds on the HCS algorithm of Hartuv and Shamir (2000).”
Uncovering Biological Network Function via Graphlet Degree Signatures (2008, background): “Similarly, highly connected subgraphs are used to identify clusters in networks (Hartuv and Shamir, 2000), deﬁning the relationship between the PPI network size and the number and complexity of the identiﬁed clusters, and identifying known protein complexes from these clusters (Prˇzulj et al.,…”
Protein complex prediction via cost-based clustering (2004, methodology): “We have developed and applied the Restricted Neigh-bourhood Search Clustering algorithm (RNSC), which partitions the network’s node set into clusters based on a cost function that is assigned to each partitioning.”
Cluster analysis for gene expression data: a survey (2004, methodology): “For other methods, proximity is mapped only to either 0 or 1 on the basis of some threshold, and edges only exist between objects i and j, where P 1⁄2i; j equals 1 [7], [26].”
Exploiting sequence-based features for predicting enhancer–promoter interactions (2017, methodology): “We further implemented the Highly Connected Subgraphs clustering algorithm [6] to group motifs in each component into clusters.”
Identification of cell types from single-cell transcriptomes using a novel clustering method (2015, methodology): “For example, the highly connected subgraph (HCS) clustering method (Hartuv and Shamir, 2000) defines a cluster as a HCS with a connectivity (the minimum number of edges to be removed to disconnect a graph) above half the number of nodes.”
Network-based prediction of protein function (2007, methodology): “Przulj et al (2004) used the highly connected subgraphs (HCS) algorithm (Hartuv and Shamir, 2000) to determine complexes in PPI data.”
Survey of clustering algorithms (2005, background): “Several recent advances on -means and other squared-error based clustering algorithms with their applications can be found in [125], [155], [222], [223], [264], and [277].”
Querying k-truss community in large and dynamic graphs (2014, background): “This property ensures the high connectivity of a community, which has been proposed as a criterion of a good community in [13].”
Experiments on Graph Clustering Algorithms (2003, methodology): “A purely graph-theoretic approach using this connection more or less directly is the recursive minimum cut approach presented in [6].”
Reconstruction and estimation in the planted partition model (2012, background): “A third group ofmethods work by optimizing some sort of cost function, for example by finding a minimum cut [16,33] or by maximizing the Girvan–Newman modularity [1,27].”