HCS clustering algorithm
The Highly Connected Subgraphs (HCS) clustering algorithm (also known as the HCS algorithm, and other names such as Highly Connected Clusters/Components/Kernels) is an algorithm based on graph connectivity for cluster analysis.
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The Highly Connected Subgraphs (HCS) clustering algorithm (also known as the HCS algorithm, and other names such as Highly Connected Clusters/Components/Kernels) is an algorithm based on graph connectivity for cluster analysis. It works by representing the similarity data in a similarity graph, and then finding all the highly connected subgraphs.
It does not make any prior assumptions on the number of the clusters. This algorithm was published by Erez Hartuv and Ron Shamir in 20001. The HCS algorithm gives a clustering solution, which is inherently meaningful in the application domain, since each solution cluster must have diameter 2 while a union of two solution clusters will have diameter 3.
Proof: Let n=|G|. If G has a vertex x with degree = n/2. There is a famous theorem in graph theory that says that if every vertex has degree >= n/2, then the diameter of G (the longest path between any two nodes) = n/2.
Therefore, the number of edges in a highly connected graph must be at least (n × n/2)/2, where we sum the degrees of each vertex and divide by 2. (b) By definition, each iteration removes a minimum cut with <= n/2 edges. Theorems 1 and 2a provide a strong indication of a final cluster's homogeneity.
Doing better approaches the case where all vertices of a cluster are connected, which is both too stringent and also NP-hard. Theorem 2b indicates separation since any two final clusters C1 and C2 would not have been separated unless there were at most O(C1+C2) edges between them (contrast with the quadratic edges within clusters).
Text derived from https://en.wikipedia.org/w/index.php?oldid=1374858274 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “HCS clustering algorithm” publication date (×1) · confidence 0.95 revision URL