7 papers
Recovering Small Communities in the Planted Partition Model
Martijn Gösgens, Maximilien Dreveton
We study community recovery in the planted partition model in regimes where the number and sizes of communities may vary arbitrarily with the number of vertices. In such highly unb…
Robust estimation of a Markov chain transition matrix from multiple sample paths
Lasse Leskelä, Maximilien Dreveton
Markov chains are fundamental models for stochastic dynamics, with applications in a wide range of areas such as population dynamics, queueing systems, reinforcement learning, and…
When Does Bottom-up Beat Top-down in Hierarchical Community Detection?
Maximilien Dreveton, Daichi Kuroda, Matthias Grossglauser +1
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…
Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics
Maximilien Dreveton, Matthias Grossglauser, Daichi Kuroda +1
Hierarchical clustering seeks to uncover nested structures in data by constructing a tree of clusters, where deeper levels reveal finer-grained relationships. Traditional methods,…
Optimal Graph Clustering without Edge Density Signals
Maximilien Dreveton, Elaine Siyu Liu, Matthias Grossglauser +1
This paper establishes the theoretical limits of graph clustering under the Popularity-Adjusted Block Model (PABM), addressing limitations of existing models. In contrast to the St…
Reducing Sensor Requirements by Relaxing the Network Metric Dimension
Paula Mürmann, Robin Jaccard, Maximilien Dreveton +2
Source localization in graphs involves identifying the origin of a phenomenon or event, such as an epidemic outbreak or a misinformation source, by leveraging structural graph prop…