The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
On Modularity Clustering
Open accessAbstract
Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, particularly in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomerative approach.
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
(1979) · Cited by 43,841
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
Jain, A. K., Murty, M. N., & Flynn, P. J. (1999) · ACM Computing Surveys · doi:10.1145/331499.331504 · Cited by 13,199
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
Finding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390
Fast algorithm for detecting community structure in networks
Newman, M. E. J. (2004) · Physical Review E · doi:10.1103/physreve.69.066133 · Cited by 5,406
An Information Flow Model for Conflict and Fission in Small Groups
Zachary, W. W. (1977) · Journal of Anthropological Research · doi:10.1086/jar.33.4.3629752 · Cited by 4,704
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
Comparing community structure identification
Danon, L., Díaz-Guilera, A., Duch, J., & Arenas, A. (2005) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2005/09/p09008 · Cited by 2,872
Newman, M. E. J. (2004) · Physical Review E · doi:10.1103/physreve.70.056131 · Cited by 2,476
Cited by
Semi-supervised classification with graph convolutional networks
Kipf, T. N., & Welling, M. (2016) · arXiv · doi:10.48550/arxiv.1609.02907 · Cited by 24,853
From Louvain to Leiden: guaranteeing well-connected communities
Traag, V. A., Waltman, L., & van Eck, N. J. (2019) · Scientific Reports · doi:10.1038/s41598-019-41695-z · Cited by 5,635
Community detection in networks: a user guide
Fortunato, S., & Hric, D. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.09.002 · Cited by 2,086
Dynamic reconfiguration of human brain networks during learning
Bassett, D. S., Wymbs, N. F., Porter, M. A., Mucha, P. J., Carlson, J. M., & Grafton, S. T. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1018985108 · Cited by 1,705
A smart local moving algorithm for large-scale modularity-based community detection
Waltman, L., & van Eck, N. J. (2013) · The European Physical Journal B · doi:10.1140/epjb/e2013-40829-0 · Cited by 1,088
Performance of modularity maximization in practical contexts
Good, B. H., de Montjoye, Y.-A., & Clauset, A. (2010) · Physical Review E · doi:10.1103/physreve.81.046106 · Cited by 937
Controllability of structural brain networks
Gu, S., Pasqualetti, F., Cieslak, M., Telesford, Q. K., Yu, A. B., Kahn, A. E., Medaglia, J. D., Vettel, J. M., Miller, M. B., Grafton, S. T., et al. (2015) · Nature Communications · doi:10.1038/ncomms9414 · Cited by 912
“Maximization of Q 0 yields a hard partition of a network into communities such that the total edge weight inside of communities is as large as possible (relative to the null model and subject to the limitations of the employed computational heuristics, as optimizing Q 0 is NP-hard 61–63 ).”
Social structure of Facebook networks
Traud, A. L., Mucha, P. J., & Porter, M. A. (2012) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2011.12.021 · Cited by 707
NetCoMi: network construction and comparison for microbiome data in R
Peschel, S., Müller, C. L., von Mutius, E., Boulesteix, A.-L., & Depner, M. (2021) · Briefings in Bioinformatics · doi:10.1093/bib/bbaa290 · Cited by 604
Clustering and community detection in directed networks: A survey
Malliaros, F. D., & Vazirgiannis, M. (2013) · Physics Reports · doi:10.1016/j.physrep.2013.08.002 · Cited by 591
Spectral clustering and the high-dimensional stochastic blockmodel
Rohe, K., Chatterjee, S., & Yu, B. (2011) · The Annals of Statistics · doi:10.1214/11-aos887 · Cited by 535
The community-search problem and how to plan a successful cocktail party
Sozio, M., & Gionis, A. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835923 · Cited by 490
Stability of graph communities across time scales
Delvenne, J.-C., Yaliraki, S. N., & Barahona, M. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0903215107 · Cited by 475
Quantifying the local adaptive landscape of a nascent bacterial community
Ascensao, J. A., Wetmore, K. M., Good, B. H., Arkin, A. P., & Hallatschek, O. (2023) · Nature Communications · doi:10.1038/s41467-022-35677-5 · Cited by 447
Robust detection of dynamic community structure in networks
Bassett, D. S., Porter, M. A., Wymbs, N. F., Grafton, S. T., Carlson, J. M., & Mucha, P. J. (2013) · Chaos: An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.4790830 · Cited by 425
Emotion semantics show both cultural variation and universal structure
Jackson, J. C., Watts, J., Henry, T. R., List, J.-M., Forkel, R., Mucha, P. J., Greenhill, S. J., Gray, R. D., & Lindquist, K. A. (2019) · Science · doi:10.1126/science.aaw8160 · Cited by 425
Depner, M., Taft, D. H., Kirjavainen, P. V., Kalanetra, K. M., Karvonen, A. M., Peschel, S., Schmausser-Hechfellner, E., Roduit, C., Frei, R., Lauener, R., et al. (2020) · Nature Medicine · doi:10.1038/s41591-020-1095-x · Cited by 368
Social Network Analysis and Mining for Business Applications
Bonchi, F., Castillo, C., Gionis, A., & Jaimes, A. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1961189.1961194 · Cited by 359
Geographic Constraints on Social Network Groups
Onnela, J.-P., Arbesman, S., González, M. C., Barabási, A.-L., & Christakis, N. A. (2011) · PLoS ONE · doi:10.1371/journal.pone.0016939 · Cited by 349
Modularity-maximizing graph communities via mathematical programming
Agarwal, G., & Kempe, D. (2008) · The European Physical Journal B · doi:10.1140/epjb/e2008-00425-1 · Cited by 338
Detecting communities and their evolutions in dynamic social networks—a Bayesian approach
Yang, T., Chi, Y., Zhu, S., Gong, Y., & Jin, R. (2011) · Machine Learning · doi:10.1007/s10994-010-5214-7 · Cited by 318
Community Detection via Maximization of Modularity and Its Variants
Chen, M., Kuzmin, K., & Szymanski, B. K. (2014) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2014.2307458 · Cited by 301
Local search of communities in large graphs
Cui, W., Xiao, Y., Wang, H., & Wang, W. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2612179 · Cited by 299
Nikolaidis, A., Paksarian, D., Alexander, L., Derosa, J., Dunn, J., Nielson, D. M., Droney, I., Kang, M., Douka, I., Bromet, E., et al. (2021) · Scientific Reports · doi:10.1038/s41598-021-87270-3 · Cited by 275
Analysis of community structure in networks of correlated data
Gómez, S., Jensen, P., & Arenas, A. (2009) · Physical Review E · doi:10.1103/physreve.80.016114 · Cited by 260
Modularity clustering is force-directed layout
Noack, A. (2009) · Physical Review E · doi:10.1103/physreve.79.026102 · Cited by 258
Ma, S., Shungin, D., Mallick, H., Schirmer, M., Nguyen, L. H., Kolde, R., Franzosa, E., Vlamakis, H., Xavier, R., & Huttenhower, C. (2022) · Genome biology · doi:10.1186/s13059-022-02753-4 · Cited by 164
Flamino, J., Galeazzi, A., Feldman, S., Macy, M. W., Cross, B., Zhou, Z., Serafino, M., Bovet, A., Makse, H. A., & Szymanski, B. K. (2023) · Nature Human Behaviour · doi:10.1038/s41562-023-01550-8 · Cited by 113
Social media behavior is associated with vaccine hesitancy
Rathje, S., He, J. K., Roozenbeek, J., Van Bavel, J. J., & van der Linden, S. (2022) · PNAS Nexus · doi:10.1093/pnasnexus/pgac207 · Cited by 100
Metacell-2: a divide-and-conquer metacell algorithm for scalable scRNA-seq analysis
Ben-Kiki, O., Bercovich, A., Lifshitz, A., & Tanay, A. (2022) · Genome Biology · doi:10.1186/s13059-022-02667-1 · Cited by 98
Zierer, J., Pallister, T., Tsai, P.-C., Krumsiek, J., Bell, J. T., Lauc, G., Spector, T. D., Menni, C., & Kastenmüller, G. (2016) · Scientific Reports · doi:10.1038/srep37646 · Cited by 63
Metadata
- Authors
- Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., & Wagner, D.
- Venue
- IEEE Transactions on Knowledge and Data Engineering
- Published
- 2008-02
- Volume
- 20
- Issue
- 2
- Pages
- 172-188
- ISSN
- 1041-4347 (ISSN-L)
- OpenAlex
- W2109726592
- Cited by
- 1,242
- References
- 27
- FWCI
- 38.23
- Type
- journal article
- Language
- en
- Open access
- green
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
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.