BEC.2: A fast and relevant Multi-Scale Graph Clustering algorithm in nPnB framework
Bruno Gaume · HAL (Le Centre pour la Communication Scientifique Directe) · 2025
In a recent paper, a unified theoretical framework nP nB is defined for the evaluation of graph clusterings with respect to the following two properties: P DC : Each community is Densely Connected; P WC : Communities are Weakly Connected to each other. In this theoretical framework a clustering of a graph is interpreted as a constrained binary classifier of node pairs intended to find the edges of the graph. The authors propose BEC in this framework, a graph clustering method which they show returns outperforming results than state-of-the-art methods, i.e. better satisfying the two properties P DC and P W C . However, this method is relatively slow and difficult to work on terrain graphs having more than a million nodes, the computation time is then counted in hours. This makes it difficult to apply BEC to graphs resulting from biological data where the number of nodes is very often greater than one million. To solve this problem we propose BEC.2 in the nP nB framework, a new graph clustering method. We compare on different classical benchmarks the computation times and the quality of clusterings returned by BEC.2, and Louvain (one of the faster and most popular clustering method optimizing M odularity) as time base line, and BEC as quality base line. We show that BEC.2 remains slower than Louvain but 100 time faster than BEC with computation time now counted in seconds and returning better or equivalent results.