Markov Dynamics as a Zooming Lens for Multiscale Community Detection: Non Clique-Like Communities and the Field-of-View Limit
Open accessThe DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Abstract
In recent years, there has been a surge of interest in community detection algorithms for complex networks. A variety of computational heuristics, some with a long history, have been proposed for the identification of communities or, alternatively, of good graph partitions. In most cases, the algorithms maximize a particular objective function, thereby finding the 'right' split into communities. Although a thorough comparison of algorithms is still lacking, there has been an effort to design benchmarks, i.e., random graph models with known community structure against which algorithms can be evaluated. However, popular community detection methods and benchmarks normally assume an implicit notion of community based on clique-like subgraphs, a form of community structure that is not always characteristic of real networks. Specifically, networks that emerge from geometric constraints can have natural non clique-like substructures with large effective diameters, which can be interpreted as long-range communities. In this work, we show that long-range communities escape detection by popular methods, which are blinded by a restricted 'field-of-view' limit, an intrinsic upper scale on the communities they can detect. The field-of-view limit means that long-range communities tend to be overpartitioned. We show how by adopting a dynamical perspective towards community detection [1], [2], in which the evolution of a Markov process on the graph is used as a zooming lens over the structure of the network at all scales, one can detect both clique- or non clique-like communities without imposing an upper scale to the detection. Consequently, the performance of algorithms on inherently low-diameter, clique-like benchmarks may not always be indicative of equally good results in real networks with local, sparser connectivity. We illustrate our ideas with constructive examples and through the analysis of real-world networks from imaging, protein structures and the power grid, where a multiscale structure of non clique-like communities is revealed.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Finding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931 · cited 2×
“This structural notion has led to several heuristics including, among others, modularity [7,8] and multiscale-Potts models [9–11] which have been coupled with different optimization algorithms (e.”
MethodA Global Geometric Framework for Nonlinear Dimensionality Reduction
Tenenbaum, J. B., Silva, V. D., & Langford, J. C. (2000) · Science · doi:10.1126/science.290.5500.2319 · Cited by 13,585
Modularity and community structure in networks
Newman, M. E. J. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0601602103 · Cited by 12,256
Complex brain networks: graph theoretical analysis of structural and functional systems
Bullmore, E., & Sporns, O. (2009) · Nature Reviews Neuroscience · doi:10.1038/nrn2575 · Cited by 11,820 · cited 2×
“This realization also has implications for current efforts to construct networks from data where, in contrast to correlation matrices, locally sparser networks are favored as a means to reveal the underlying systemic connections of the data [6].”
BackgroundFortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · cited 2×
“[3]).”
BackgroundMaps of random walks on complex networks reveal community structure
Rosvall, M., & Bergstrom, C. T. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0706851105 · Cited by 4,583
Statistical physics of social dynamics
Castellano, C., Fortunato, S., & Loreto, V. (2009) · Reviews of Modern Physics · doi:10.1103/revmodphys.81.591 · Cited by 4,119
Resolution limit in community detection
Fortunato, S., & Barthélemy, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0605965104 · Cited by 3,024 · cited 2×
“The field-of-view appears on the opposite scale of the well-known resolution limit [18], which indicates a lower limit size below which modularity cannot detect communities.”
BackgroundStatistical mechanics of community detection
Reichardt, J., & Bornholdt, S. (2006) · Physical Review E · doi:10.1103/physreve.74.016110 · Cited by 2,048
Stochastic blockmodels and community structure in networks
Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.83.016107 · Cited by 2,025
Cited by
Contributions and challenges for network models in cognitive neuroscience
Sporns, O. (2014) · Nature Neuroscience · doi:10.1038/nn.3690 · Cited by 759
Random walks and diffusion on networks
Masuda, N., Porter, M. A., & Lambiotte, R. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.07.007 · Cited by 657
Betzel, R. F., & Bassett, D. S. (2017) · NeuroImage · doi:10.1016/j.neuroimage.2016.11.006 · Cited by 587
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
Lambiotte, R., Delvenne, J.-C., & Barahona, M. (2014) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2015.2391998 · Cited by 398
Self-citationTopological Strata of Weighted Complex Networks
Petri, G., Scolamiero, M., Donato, I., & Vaccarino, F. (2013) · PLoS ONE · doi:10.1371/journal.pone.0066506 · Cited by 214
Metadata
- Authors
- Schaub, M. T., Delvenne, J.-C., Yaliraki, S. N., & Barahona, M.
- Venue
- PLoS ONE
- Publisher
- Public Library of Science (PLoS)
- Published
- 2012-02-27
- Volume
- 7
- Issue
- 2
- Pages
- e32210
- ISSN
- 1932-6203 (ISSN-L)
- OpenAlex
- W1978825280
- Cited by
- 149
- References
- 11
- FWCI
- 9.97
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Markov Dynamics as a Zooming Lens for Multiscale Community Detection: Non Clique-Like Communities and the Field-of-View Limit. https://app.cochat.ai/papers/10.1371/journal.pone.0032210
- The paper
- Schaub, M. T., Delvenne, J.-C., Yaliraki, S. N., & Barahona, M. (2012). Markov Dynamics as a Zooming Lens for Multiscale Community Detection: Non Clique-Like Communities and the Field-of-View Limit. PLoS ONE. https://doi.org/10.1371/journal.pone.0032210
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.