Narrow scope for resolution-limit-free community detection.

By Vincent A. Traag, P. Dooren, Yurii E. Nesterov. Physical review. E, Statistical, nonlinear, and soft matter physics, 2011

362 citations recorded by the source corpus.

Detecting communities in large networks has drawn much attention over the years. While modularity remains one of the more popular methods of community detection, the so-called resolution limit remains a significant drawback. To overcome this issue, it was recently suggested that instead of comparing the network to a random null model, as is done in modularity, it should be compared to a constant factor. However, it is unclear what is meant exactly by "resolution-limit-free," that is, not suffering from the resolution limit. Furthermore, the question remains what other methods could be classified as resolution-limit-free. In this paper we suggest a rigorous definition and derive some basic properties of resolution-limit-free methods. More importantly, we are able to prove exactly which class of community detection methods are resolution-limit-free. Furthermore, we analyze which methods are not resolution-limit-free, suggesting there is only a limited scope for resolution-limit-free community detection methods. Finally, we provide such a natural formulation, and show it performs superbly.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/cbd8b666ab348ccb2bd3a6e0b3d21a1d53d89179

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

From Louvain to Leiden: guaranteeing well-connected communities (2018, methodology): “In this paper, we show that the Louvain algorithm has a major problem, for both modularity and CPM.”
A new methodology for constructing a publication-level classification system of science (2012, methodology): “Recently, a variant of modularity-based clustering that uses exactly the same quality function as in (4) was proposed by Traag, Van Dooren, and Nesterov (2011).”
Community detection in networks: A user guide (2016, background): “(24) and (25) can be trivially extended to weighted graphs (Traag et al., 2011).”
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks (2008, methodology): “Through the intuition gained from the corresponding dynamics, we reinterpret the Erd¨os-R´enyi Simple Random Walk Normalized Laplacian Combinatorial Degree Degree Uniform Eigencentrality Linearized model[47] Potts model[47] Potts model[48], [ null model (long considered as inferior in the null-model”
A smart local moving algorithm for large-scale modularity-based community detection (2013, methodology): “We emphasize, however, that the SLM algorithm can also be used for optimizing many of the variants of this function that have been proposed in the literature, for instance variants that include a resolution parameter (Reichardt & Bornholdt, 2006) or that have a somewhat modified mathematical structu”
Multi-scale brain networks (2016, neutral): “It should be noted that there exist possible definitions of modularity functions that do not suffer from resolution limits in the first place (Traag et al., 2011).”
Citation-based clustering of publications using CitNetExplorer and VOSviewer (2017, methodology): “The quality function is very similar to the quality function resulting from the so-called constant Potts model proposed by Traag, Van Dooren, and Nesterov (2011).”