When Does Bottom-up Beat Top-down in Hierarchical Community Detection?

• URL: http://arxiv.org/abs/2306.00833v2
• Date: Wed, 24 Jul 2024 13:13:20 GMT
• Title: When Does Bottom-up Beat Top-down in Hierarchical Community Detection?
• Authors: Maximilien Dreveton, Daichi Kuroda, Matthias Grossglauser, Patrick Thiran,
• Abstract summary: Hierarchical clustering of networks consists in finding a tree of communities, such that lower levels of the hierarchy reveal finer-grained community structures. Agglomerative ($textitbottom-up$) algorithms first identify the smallest community structure and then repeatedly merge the communities using a $textitlinkage$ method. We establish theoretical guarantees for the recovery of the hierarchical tree and community structure of a Hierarchical Block Model by a bottom-up algorithm.
• Score: 8.097200145973389
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hierarchical clustering of networks consists in finding a tree of communities, such that lower levels of the hierarchy reveal finer-grained community structures. There are two main classes of algorithms tackling this problem. Divisive ($\textit{top-down}$) algorithms recursively partition the nodes into two communities, until a stopping rule indicates that no further split is needed. In contrast, agglomerative ($\textit{bottom-up}$) algorithms first identify the smallest community structure and then repeatedly merge the communities using a $\textit{linkage}$ method. In this article, we establish theoretical guarantees for the recovery of the hierarchical tree and community structure of a Hierarchical Stochastic Block Model by a bottom-up algorithm. We also establish that this bottom-up algorithm attains the information-theoretic threshold for exact recovery at intermediate levels of the hierarchy. Notably, these recovery conditions are less restrictive compared to those existing for top-down algorithms. This shows that bottom-up algorithms extend the feasible region for achieving exact recovery at intermediate levels. Numerical experiments on both synthetic and real data sets confirm the superiority of bottom-up algorithms over top-down algorithms. We also observe that top-down algorithms can produce dendrograms with inversions. These findings contribute to a better understanding of hierarchical clustering techniques and their applications in network analysis.

Related papers

• Hierarchical Clustering via Local Search [0.0]
  We introduce a local search algorithm for hierarchical clustering. We show that any locally optimal tree guarantees a revenue of at least $fracn-23sum_i jw(i,j)$ where is $n$ the number of objects and $w: [n] times [n] mathbbR+$ is the associated similarity function.
  arXiv  Detail & Related papers  (2024-05-24T23:46:24Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
  arXiv  Detail & Related papers  (2023-05-24T11:05:12Z)
• Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity [0.0]
  We propose a nearest neighbor based clustering algorithm that results in a naturally defined hierarchy of clusters. In contrast to the agglomerative and divisive hierarchical clustering algorithms, our approach is not dependent on the iterative working of the algorithm.
  arXiv  Detail & Related papers  (2022-03-15T16:03:42Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• Hierarchical clustering by aggregating representatives in sub-minimum-spanning-trees [5.877624540482919]
  We propose a novel hierarchical clustering algorithm, in which, while building the clustering dendrogram, we can effectively detect the representative point. Under our analysis, the proposed algorithm has O(nlogn) time-complexity and O(logn) space-complexity, indicating that it has the scalability in handling massive data.
  arXiv  Detail & Related papers  (2021-11-11T07:36:55Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  We introduce a new approach based on A* search for clustering. We overcome the prohibitively large search space by combining A* with a novel emphtrellis data structure. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks.
  arXiv  Detail & Related papers  (2021-04-14T18:15:27Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods [77.34726150561087]
  We study how local structural network properties can be used as proxies to improve the efficiency of hierarchical community detection. We also check the performance impact of network prunings as an ancillary tactic to make hierarchical community detection more efficient.
  arXiv  Detail & Related papers  (2020-09-15T00:16:12Z)
• Data Structures & Algorithms for Exact Inference in Hierarchical Clustering [41.24805506595378]
  We present novel dynamic-programming algorithms for emphexact inference in hierarchical clustering based on a novel trellis data structure. Our algorithms scale in time and space proportional to the powerset of $N$ elements which is super-exponentially more efficient than explicitly considering each of the (2N-3)!! possible hierarchies.
  arXiv  Detail & Related papers  (2020-02-26T17:43:53Z)
• Scalable Hierarchical Clustering with Tree Grafting [66.68869706310208]
  Grinch is a new algorithm for large-scale, non-greedy hierarchical clustering with general linkage functions. Grinch is motivated by a new notion of separability for clustering with linkage functions.
  arXiv  Detail & Related papers  (2019-12-31T20:56:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.