cs.SIMar 21, 2023

Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering

Authors: Łukasz Brzozowski, Grzegorz Siudem, Marek Gagolewski

Organizations: Warsaw University of Technology, Faculty of Mathematics and Information Science, ul. Koszykowa 75, 00-662 Warsaw, Poland · Warsaw University of Technology, Faculty of Physics, ul. Koszykowa 75, 00-662 Warsaw, Poland · Deakin University, Data to Intelligence Research Centre, School of IT, Geelong, VIC 3220, Australia

Abstract

Community detection is a significant challenge in analysing real graphs, including social, citation, biological, and many other networks. This article proposes three new, general, hierarchical frameworks to deal with this task. The introduced approach supports various linkage-based clustering algorithms, vertex proximity matrices, and graph representation learning models. We compare 364 module combinations on Stochastic Block Model graphs and real-life datasets. We observe that our best pipelines (Wasserman-Faust and the mutual information-based PPMI proximity, as well as the deep learning-based DNGR representations) perform competitively with the state-of-the-art Leiden and Louvain algorithms. At the same time, unlike the latter, they remain hierarchical. Thus, they output a series of nested partitions of all possible cardinalities which are compatible with each other. This feature is crucial when the number of correct partitions is unknown in advance, and we show that it is obtained at near-zero practical cost in terms of partition quality. On graphs composed of many small communities, our pipelines are more accurate than the reference solutions. Nevertheless, the downside of our approach is its time complexity, which confines the framework to networks of some 10000 vertices on personal machines.

Explore similar work

CardsList
  1. Alcmean's: Unsupervised community detection using local Laplacian, automatic detection of the number of centers

    Jun 8, 2026Shahin Momenzadeh, Rojiar Pir MohammadianiCluster Number EstimationClustering

  2. Diffusion-Induced Spatial Attention Overlapping Community Detection

    Sep 22, 2026Kosti Koistinen, Vesa Kuikka, Joni Herttuainen +3Graph Attention NetworksGraph Clustering

  3. ECHO: Encoding Communities via High-order Operators

    Feb 25, 2026Emilio FerraraGraph ClusteringSocial Network Analysis