Hierarchical Community Detection in Hierarchical Stochastic Block Models

When

25/10/2024    
11:00 am-12:00 pm
Sayeh Khaniha
Inria

Where

Amphi 6
19 Place Marguerite Perey, Palaiseau

Event Type

In this session of our reading group, I will discuss community detection in hierarchical clustering of networks, based on the paper “When Does Bottom-up Beat Top-down in Hierarchical Community Detection?” by Maximilien Dreveton et al. Hierarchical clustering involves constructing a tree of communities, with lower levels revealing finer-grained structures. Two main approaches address this problem: divisive (top-down) algorithms, which recursively split nodes, and agglomerative (bottom-up) algorithms, which start by identifying the smallest communities and then merge them using a linkage method. This talk will focus on establishing theoretical guarantees for the exact recovery of the hierarchical tree under a Hierarchical Stochastic Block Model (HSBM) using a bottom-up algorithm. The findings show that bottom-up methods can achieve the information-theoretic threshold for exact recovery at intermediate hierarchy levels, offering less restrictive conditions than top-down algorithms and expanding the feasible region for accurate community detection.

Privacy Overview

This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.