Uncovering the overlapping community structure of complex networks in nature and society
Open accessThe DOI matches its Crossref record; 33 of the 34 references it cites were found in a registry or an index.
Abstract
Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of. A key question is how to interpret the global organization of such networks as the coexistence of their structural subunits (communities) associated with more highly interconnected parts. Identifying these a priori unknown building blocks (such as functionally related proteins, industrial sectors and groups of people) is crucial to the understanding of the structural and functional properties of networks. The existing deterministic methods used for large networks find separated communities, whereas most of the actual networks are made of highly overlapping cohesive groups of nodes. Here we introduce an approach to analysing the main statistical features of the interwoven sets of overlapping communities that makes a step towards uncovering the modular structure of complex systems. After defining a set of new characteristic quantities for the statistics of communities, we apply an efficient technique for exploring overlapping communities on a large scale. We find that overlaps are significant, and the distributions we introduce reveal universal features of networks. Our studies of collaboration, word-association and protein interaction graphs show that the web of communities has non-trivial correlations and specific scaling properties.
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.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“complex network theory has demonstrated that many (non-quantum) systems exhibit similarities in their complex features 14 -18 , in the organization of their structure and dynamics 19 -24 , the controllability of their constituents 25 , and their resilience to structural and dynamical perturbations 26 -31 .”
From Complex networks from classical to quantum (2019) · cites this paper as [20]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“This notion of clustering is closely related to clique clustering algorithms in network clustering [53].”
From Topology and data (2009) · cites this paper as [53]
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
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060 · cited 1×
“Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of [1, 2, 3, 4].”
BackgroundEmergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135 · cited 2×
“´ny P. stny. 1A, H-1117 Budapest, Hungary. Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of [1, 2, 3, 4]. A question of interest is how to interpret the global organisation of such networks as the coexistence of…”
BackgroundInfluentialStatistical mechanics of complex networks
Albert, R., & Barabási, A.-L. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.47 · Cited by 20,471 · cited 2×
“Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of [1, 2, 3, 4].”
BackgroundCommunity structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502 · cited 2×
“[16]: it tends to stay together mostly with the words of the community related to “light”, while most of its other communities ( e.g. , those related to “colors”, see Fig.”
BackgroundEveritt, B. J., Landau, S., & Leese, M. (1974) · Cited by 9,363
Social Network Analysis: A Handbook.
Pappi, F. U., & Scott, J. (1993) · Contemporary Sociology · doi:10.2307/2075047 · Cited by 5,969
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 · cited 3×
“[18], at some point “bright”, as a single word, joined a “community” of 890 other words.”
BackgroundFunctional organization of the yeast proteome by systematic analysis of protein complexes
Gavin, A.-C., Bösche, M., Krause, R., Grandi, P., Marzioch, M., Bauer, A., Schultz, J., Rick, J. M., Michon, A.-M., Cruciat, C.-M., et al. (2002) · Nature · doi:10.1038/415141a · Cited by 4,759 · cited 1×
“Another, biological example is that a large fraction of proteins belong to several protein complexes simultaneously [20].”
BackgroundHierarchical Organization of Modularity in Metabolic Networks
Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., & Barabási, A.-L. (2002) · Science · doi:10.1126/science.1073374 · Cited by 4,224 · cited 2×
“In spite of this ambiguity the presence of communities in networks is a signature of the hierarchical nature of complex systems [5, 14].”
BackgroundDefining and identifying communities in networks
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0400054101 · Cited by 2,450 · cited 2×
“[10, 15, 16, 17, 18]).”
Background
Research works printed but not linked: 1
- [21] Everett, M. G. & Borgatti, S. P. Analyzing clique overlap. Connections 21 , 49-61 (1998). -
Cited by
Items 501–600 of 1,010
Synchronization in complex networks with a modular structure
Park, K., Lai, Y., Gupte, S., & Kim, J. (2006) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.2154881 · Cited by 92
West, J., Beck, S., Wang, X., & Teschendorff, A. E. (2013) · Scientific Reports · doi:10.1038/srep01630 · Cited by 89
Mathematical and computational approaches to epidemic modeling: a comprehensive review
Duan, W., Fan, Z., Zhang, P., Guo, G., & Qiu, X. (2015) · Frontiers of Computer Science · doi:10.1007/s11704-014-3369-2 · Cited by 93
“Recently, many researchers who focus on the impact that network topologies have on epidemic dynamics have transferred their attention to epidemic spread in hierarchy and modular networks with community structure [61– 65].”
BackgroundCommunities and Balance in Signed Networks: A Spectral Approach
Anchuri, P., & Magdon‐Ismail, M. (2012) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2012.48 · Cited by 91
“A related problem [10], [11] is that of finding overlapping communities in social networks.”
BackgroundEnumeration of condition-dependent dense modules in protein interaction networks
Georgii, E., Dietmann, S., Uno, T., Pagel, P., & Tsuda, K. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp080 · Cited by 91
“Contact: koji.tsuda@tuebingen.mpg.de Supplementary information: Supplementary data are available at Bioinformatics online.”
Modularity in Biological Networks
Alcalá-Corona, S. A., Sandoval‐Motta, S., Enríquez, J. E., & Lemus, E. H. (2021) · Frontiers in Genetics · doi:10.3389/fgene.2021.701331 · Cited by 105
“Intuitively, the density of connections inside any socalled module (within-connections) must be significantly higher than the density of connections with other modules (betweenconnections) (Thieffry and Romero, 1999; Girvan and Newman, 2002; Clauset et al., 2004; Palla et al., 2005).”
BackgroundOn Effectively Finding Maximal Quasi-cliques in Graphs
Brunato, M., Hoos, H. H., & Battiti, R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-92695-5_4 · Cited by 91
Graph theoretic modeling of large-scale semantic networks
Bales, M. E., & Johnson, S. B. (2005) · Journal of Biomedical Informatics · doi:10.1016/j.jbi.2005.10.007 · Cited by 100
“Palla et al [43] have introduced a set of characteristic quantities to describe the statistics of communities in networks.”
BackgroundBlacklock, K., & Verkhivker, G. M. (2014) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003679 · Cited by 90
Overlapping community detection in complex networks using symmetric binary matrix factorization
Zhang, Z., Wang, Y., & Ahn, Y. (2013) · Physical Review E · doi:10.1103/physreve.87.062803 · Cited by 98
Disease-induced resource constraints can trigger explosive epidemics
Böttcher, L., Woolley-Meza, O., Araújo, N. A. M., Herrmann, H. J., & Helbing, D. (2015) · Scientific Reports · doi:10.1038/srep16571 · Cited by 95
Havemann, F., Heinz, M., Struck, A., & Gläser, J. (2011) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2011/01/p01023 · Cited by 90
“Beginning with the well-known work by Palla, Derenyi, Farkas, and Vicsek in 2005 [1], a number of approaches to the”
Scalable Spectral Clustering for Overlapping Community Detection in Large-Scale Networks
Lierde, H. V., Chow, T. W. S., & Chen, G. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2892096 · Cited by 90
Multimodal mapping of the face connectome
Wang, Y., Metoki, A., Smith, D. V., Medaglia, J. D., Zang, Y., Benear, S. L., Popal, H. S., Lin, Y., & Olson, I. R. (2020) · Nature Human Behaviour · doi:10.1038/s41562-019-0811-3 · Cited by 98
Kensche, P. R., van Noort, V., Dutilh, B. E., & Huynen, M. A. (2008) · Journal of The Royal Society Interface · doi:10.1098/rsif.2007.1047 · Cited by 89
“The modular structure of biological networks is figured as hierarchical and overlapping (e.g. Ravasz et al. 2002; Palla et al. 2005): different modules are related to each other by combination into higher order modules or by”
BackgroundPercolation of interdependent network of networks
Havlin, S., Stanley, E., Bashan, A., Gao, J., & Kenett, D. Y. (2014) · Chaos Solitons & Fractals · doi:10.1016/j.chaos.2014.09.006 · Cited by 96
“Network concepts were also useful in the analysis and understanding of the spread of epidemics [39,40], and the organizational laws of social interactions, such as friendships [41,42] or scientific collaborations [43].”
BackgroundSpectral tripartitioning of networks
Richardson, T., Mucha, P. J., & Porter, M. A. (2009) · Physical Review E · doi:10.1103/physreve.80.036111 · Cited by 90
Dominant Imprint of Rossby Waves in the Climate Network
Wang, Y., Gozolchiani, A., Ashkenazy, Y., Berezin, Y., Guez, O., & Havlin, S. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.138501 · Cited by 93
Visualizing Asymmetric Competition Among More Than 1,000 Products Using Big Search Data
Ringel, D. M., & Skiera, B. (2016) · Marketing Science · doi:10.1287/mksc.2015.0950 · Cited by 88
“This visualization represents a challenge in markets with large numbers of products because groups of mapped objects tend to overlap in the resulting visual representation of the network, making relationships between individual products difficult to decipher (Palla et al. 2005).”
BackgroundHierarchical clustering supported by reciprocal nearest neighbors
Xie, W.-B., Lee, Y.-L., Wang, C., Chen, D., & Zhou, T. (2020) · Information Sciences · doi:10.1016/j.ins.2020.04.016 · Cited by 94
Local dominance unveils clusters in networks
Shi, D., Shang, F., Chen, B., Expert, P., Lü, L., Stanley, E., Lambiotte, R., Evans, T., & Li, R. (2024) · Communications Physics · doi:10.1038/s42005-024-01635-4 · Cited by 96
Complex and Adaptive Dynamical Systems: A Primer
Gros, C. (2015) · Springer eBooks · doi:10.1007/978-3-319-16265-2 · Cited by 89
Community-Engaged Research Perspectives: Then and Now
Barkin, S. L., Schlundt, D., & Smith, P. (2013) · Academic Pediatrics · doi:10.1016/j.acap.2012.12.006 · Cited by 97
Suicide Ideation of Individuals in Online Social Networks
Masuda, N., Kurahashi, I., & Onari, H. (2013) · PLoS ONE · doi:10.1371/journal.pone.0062262 · Cited by 88
“Individuals without triangles are considered to lack membership to social groups even if they have many friends [16]; social groups are often approximated by overlapping triangles [17,18].”
BackgroundClustering and Summarizing Protein-Protein Interaction Networks: A Survey
Bhowmick, S. S., & Seah, B.-S. (2015) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2015.2492559 · Cited by 104
“Local neighborhood density based [91], MIPS, YPD [92], Y2H exp. [29], [97], [103], [107], [108] DPClus [2] Local density and periphery based DIP [96], MIPS IPCA [39] Local density and distance based MIPS RNSC [34] Local search cost based Yeast [93], Fruitfly [94], C. elegans [95], MIPS Pei et al. [54] Subgraph refinem…”
MethodInfluentialSocial-Aware Resource Allocation for Device-to-Device Communications Underlaying Cellular Networks
Zhao, Y., Li, Y., Cao, Y., Jiang, T., & Ge, N. (2015) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2015.2457427 · Cited by 88
Enhance the Performance of Network Computation by a Tunable Weighting Strategy
Li, H., Bu, Z., Wang, Z., Cao, J., & Shi, Y. (2018) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2018.2829906 · Cited by 88
Tail dependence networks of global stock markets
Wen, F., Yang, X., & Zhou, W. (2018) · International Journal of Finance & Economics · doi:10.1002/ijfe.1679 · Cited by 93
Discovering Communities from Social Networks: Methodologies and Applications
Yang, B. X., Liu, D., & Liu, J. (2010) · Springer eBooks · doi:10.1007/978-1-4419-7142-5_16 · Cited by 88
LinkSCAN*: Overlapping community detection using the link-space transformation
Lim, S., Ryu, S., Kwon, S., Jung, K., & Lee, J.-G. (2014) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2014.6816659 · Cited by 88
“In recent years, several clustering methods to uncover the overlapping community structure have been proposed [2], [4], [6], [21], [1], [22], [23].”
BackgroundMethodInfluentialComparative definition of community and corresponding identifying algorithm
Hu, Y., Chen, H., Zhang, P., Li, M., Di, Z., & Fan, Y. (2008) · Physical Review E · doi:10.1103/physreve.78.026121 · Cited by 102
Measuring and Analyzing Search-Redirection Attacks in the Illicit Online Prescription Drug Trade
Leontiadis, N. (2011) · Cited by 119
Atay, Y., Koç, İ., Babaoğlu, İ., & Kodaz, H. (2016) · Applied Soft Computing · doi:10.1016/j.asoc.2016.11.025 · Cited by 90
“For instance, functions of other unknown communities may be estimated inspiring by information, which is that the protein named as “Ycr072c” in the community “ribosome biogenesis/assembly” is important for cell viability [16].”
BackgroundEgo-Splitting Framework: from Non-Overlapping to Overlapping Clusters
Epasto, A., Lattanzi, S., & Leme, R. P. (2017) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3097983.3098054 · Cited by 88
“is is consistent with previous results in social networks [35].”
ResultFuzzy modularity and fuzzy community structure in networks
Liu, J. (2010) · The European Physical Journal B · doi:10.1140/epjb/e2010-00290-3 · Cited by 94
Weighted growing simplicial complexes
Courtney, O. T., & Bianconi, G. (2017) · Physical review. E · doi:10.1103/physreve.95.062301 · Cited by 98
A Markov random walk under constraint for discovering overlapping communities in complex networks
Jin, D., Yang, B., Baquero, C., Liu, D., He, D., & Liu, J. (2011) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2011/05/p05031 · Cited by 89
“Moreover, as we argued, the efficiency of UEOC is competitive with the efficiency of LFM and higher than that of CPM.”
BackgroundMethodInfluentialLED: A fast overlapping communities detection algorithm based on structural clustering
Ma, T., Wang, Y., Tang, M., Cao, J., Tian, Y., Al-Dhelaan, A. M., & Al‐Rodhaan, M. (2016) · Neurocomputing · doi:10.1016/j.neucom.2016.05.020 · Cited by 86
Compression of Flow Can Reveal Overlapping-Module Organization in Networks
Esquivel, A. V., & Rosvall, M. (2011) · Physical Review X · doi:10.1103/physrevx.1.021025 · Cited by 109
“flow-based approach, implemented in fuzzy Infomap, with these approaches, represented here by the OSLOM [13], clique-percolation [32], and link-communities [16] methods.”
MethodCommunity detection in graphs using singular value decomposition
Sarkar, S., & Dong, A. (2011) · Physical Review E · doi:10.1103/physreve.83.046114 · Cited by 95
Node Attribute-enhanced Community Detection in Complex Networks
Jia, C., Li, Y., Carson, M. B., Wang, X., & Yu, J. J. (2017) · Scientific Reports · doi:10.1038/s41598-017-02751-8 · Cited by 99
“τ ‖ ‖ S A I S S S d S S ( ) , / , (3) ij ij j ij ij i j 2 2”
BackgroundMethodInfluentialNavratil, V., de Chassey, B., Combe, C., & Lotteau, V. (2011) · BMC Systems Biology · doi:10.1186/1752-0509-5-13 · Cited by 86
“The CFinder [16] clustering”
Classifying Clustering Schemes
Carlsson, G., & Mémoli, F. (2013) · Foundations of Computational Mathematics · doi:10.1007/s10208-012-9141-9 · Cited by 85
“This notion is closely related to proposals in network clustering [24] and the DBSCAN algorithm [10], and for n > 2 provides a way to tackle the “chaining effect” exhibited by single linkage clustering (i.e., C Δ 2 (δ) ); see Fig.”
MethodInfluentialPartitioning and modularity of graphs with arbitrary degree distribution
Reichardt, J., & Bornholdt, S. (2007) · Physical Review E · doi:10.1103/physreve.76.015102 · Cited by 83
Analyzing Participation of Students in Online Courses Using Social Network Analysis Techniques.
Rabbany, R., Takaffoli, M., & Zai͏̈ane, O. R. (2011) · Educational Data Mining · Cited by 106
Assessing Research Collaboration through Co-authorship Network Analysis.
Fagan, J. M., Eddens, K. S., Dolly, J., Vanderford, N. L., Weiss, H. L., & Levens, J. S. (2018) · PubMed · Cited by 120
Multifractal network generator
Palla, G., Lovász, L., & Vicsek, T. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0912983107 · Cited by 93
Self-citationA Novel Method for Detecting New Overlapping Community in Complex Evolving Networks
Cheng, J., Wu, X., Zhou, M., Gao, S., Huang, Z., & Liu, C. (2018) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2017.2779138 · Cited by 87
“In static networks, the overlapping community detection has been extensively explored since the work [8].”
BackgroundMethodCommunity detection based on modularity and k-plexes
Zhu, J., Chen, B., & Zeng, Y. (2019) · Information Sciences · doi:10.1016/j.ins.2019.10.076 · Cited by 94
“In our perception, a k -plex or several k -plexes can be defined as a community (e.g., the CPM algorithm [26]).”
BackgroundSEAL: Learning Heuristics for Community Detection with Generative Adversarial Networks
Zhang, Y., Xiong, Y., Ye, Y., Liu, T., Wang, W., Zhu, Y., & Yu, P. S. (2020) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3394486.3403154 · Cited by 113
“• Flexibility: Most existing methods make assumptions on structures of communities, e.g., k-clique, k-truss, and k-core [10, 26].”
MethodPredictability of Conversation Partners
Takaguchi, T., Nakamura, M., Sato, N., Yano, K., & Masuda, N. (2011) · Physical Review X · doi:10.1103/physrevx.1.011008 · Cited by 93
“Note that, when the clustering coefficient is large, the individual tends to be inside a community quantified by the abundance of triangles [40].”
BackgroundDistributive immunization of networks against viruses using the ‘honey-pot’ architecture
Goldenberg, J., Shavitt, Y., Shir, E., & Solomon, S. (2005) · Nature Physics · doi:10.1038/nphys177 · Cited by 83
Uncovering the overlapping community structure of complex networks by maximal cliques
Li, J., Wang, X., & Cui, Y. (2014) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2014.08.025 · Cited by 85
Ghosh, A., & Vishveshwara, S. (2008) · Biochemistry · doi:10.1021/bi8007559 · Cited by 83
Generalized Communities in Networks
Newman, M. E. J., & Peixoto, T. P. (2015) · Physical Review Letters · doi:10.1103/physrevlett.115.088701 · Cited by 110
“The method is computationally efficient, allowing for its application to large networks, and provides significantly more insight than the traditional community division into discrete groups, or even recent generalizations to overlapping groups [7, 8].”
MethodShaping communities out of triangles
Prat-Pèrez, A., Domínguez-Sal, D., Brunat, J. M., & Larriba-Pey, J.-L. (2012) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2396761.2398496 · Cited by 92
“Besides, other popular approaches in the literature, such as [1, 19, 28] among others, aim at overlapping communities which are also out of the scope of this paper.”
BackgroundStress‐induced rearrangements of cellular networks: Consequences for protection and drug design
Szalay, M., Kovács, I. A., Korcsmáros, T., Böde, C., & Csermely, P. (2007) · FEBS Letters · doi:10.1016/j.febslet.2007.03.083 · Cited by 90
Graph-based data clustering with overlaps
Fellows, M. R., Guo, J., Komusiewicz, C., Niedermeier, R., & Uhlmann, J. (2010) · Discrete Optimization · doi:10.1016/j.disopt.2010.09.006 · Cited by 82
Selecting the Most Influential Nodes in Social Networks
Estévez, P. A., Vera, P., & Saito, K. (2007) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2007.4371333 · Cited by 82
An edge-centric perspective on the human connectome: link communities in the brain
de Reus, M. A., Saenger, V. M., Kahn, R. S., & van den Heuvel, M. P. (2014) · Philosophical Transactions of the Royal Society B: Biological Sciences · doi:10.1098/rstb.2013.0527 · Cited by 76
On exploiting transient contact patterns for data forwarding in Delay Tolerant Networks
Gao, W., & Cao, G. (2010) · IEEE International Conference on Network Protocols (ICNP) · doi:10.1109/icnp.2010.5762768 · Cited by 81
“k-clique-based method [27] enables the detection of overlapping communities, and modularitybased method [25] works on weighted network contact graph.”
MethodMapping the Evolution of Scientific Fields
Herrera, M., Roberts, D. C. K., & Gulbahce, N. (2010) · PLoS ONE · doi:10.1371/journal.pone.0010355 · Cited by 91
Probabilistic community discovery using hierarchical latent Gaussian mixture model
Zhang, H., Giles, C. L., Foley, H. C., & Yen, J. (2007) · National Conference on Artificial Intelligence · Cited by 87
Peer Influence in the Diffusion of iPhone 3G over a Large Social Network1
de Matos, M. G., Ferreira, P., & Krackhardt, D. M. (2014) · MIS Quarterly · doi:10.25300/misq/2014/38.4.08 · Cited by 107
Dagan, T. (2011) · Trends in Microbiology · doi:10.1016/j.tim.2011.07.001 · Cited by 82
Unified Photo Enhancement by Discovering Aesthetic Communities From Flickr
Hong, R., Zhang, L., & Tao, D. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2016.2514499 · Cited by 80
“chastic block (MMSB) [38]; 2) block-LDA [41]; 3) K-means clustering (KC) [42]; 4) hierarchical clustering (HC) [43]; 5) link clustering (LC) [45]; 6) clique percolation (CP) [48]; 7) low-rank embedding (LRE) [17]; and 8) multi-assignment clustering (MAC) [18].”
Data-Driven Computational Social Science: A Survey
Zhang, J., Wang, W. W., Xia, F., Lin, Y., & Tong, H. (2020) · Big Data Research · doi:10.1016/j.bdr.2020.100145 · Cited by 94
“[97] introduced an approach to analyze the main statistical features of the interwoven sets of overlapping communities based on the Clique Percolation Method (CPM).”
BackgroundMethodParallel $(k)$-Clique Community Detection on Large-Scale Networks
Gregori, E., Lenzini, L., & Mainardi, S. (2012) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2012.229 · Cited by 90
“However, their detection is challenging due to extensive memory requirements and execution time.”
BackgroundBakillah, M., Li, R.-Y., & Liang, S. H. L. (2014) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2014.964247 · Cited by 88
“Papadopoulos et al. (2012) Cohesive subgraph discovery methods are based on the assumption that communities are characterized by well-defined structural properties, such as cliques (Palla et al. 2005) and cores (Batagelj and Zaver š nik 2011).”
MethodLou, H., Li, S., & Zhao, Y. (2013) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2013.03.014 · Cited by 88
Visualizing Fuzzy Overlapping Communities in Networks
Vehlow, C., Reinhardt, T., & Weiskopf, D. (2013) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2013.232 · Cited by 91
“With crisp over-lapping community detection methods [19, 40, 44], each object fully belongs to one or more communities; with fuzzy overlapping community detection methods [4, 34, 53], vertices may belong to different communities to different extent.”
BackgroundMethodInfluentialChaperones as integrators of cellular networks: Changes of cellular integrity in stress and diseases
Palotai, R., Szalay, M., & Csermely, P. (2007) · IUBMB Life · doi:10.1002/iub.8 · Cited by 90
Finding Communities in Dynamic Social Networks
Tantipathananandh, C., & Berger-Wolf, T. Y. (2011) · Proceedings · doi:10.1109/icdm.2011.67 · Cited by 91
“[23] use a very local and restrictive approach of finding overlapping cliques of predefined size in consecutive time steps.”
What Is a Complex Innovation System?
Katz, J. S. (2016) · PLoS ONE · doi:10.1371/journal.pone.0156150 · Cited by 88
“A natural population is one that preserves its clustering, ‘community’ or small world structure [47,48].”
BackgroundOverlapping Community Regularization for Rating Prediction in Social Recommender Systems
Li, H., Wu, D., Tang, W., & Mamoulis, N. (2015) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/2792838.2800171 · Cited by 84
“• CPM is the clique percolation method [20] based on k-clique.”
MethodCommuter networks and community detection: A method for planning sub regional areas
Montis, A. D., Caschili, S., & Chessa, A. (2013) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2013-01716-4 · Cited by 85
“…dealing with related topics (Flake et al., 2002), functional modules such as cycles and pathways in metabolic networks (Guimerà and Amaral, 2005; Palla et al., 2005), to groups of related individuals in social networks (Girvan and Newman, 2002; Lusseau and Newman, 2004), and compartments in…”
BackgroundFinding community structure in spatially constrained complex networks
Chen, Y., Xu, J., & Xu, M. (2015) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2014.999244 · Cited by 82
“The approach has been used in exploring data of e-mail communities, metabolic networks, web communities, literature co-citations, and project cooperation, among others (Flake et al. 2002, Ravasz et al. 2002, Palla et al. 2005, Tyler et al. 2005, Barber et al. 2011).”
MethodHearing the clusters of a graph: A distributed algorithm
Sahai, T., Speranzon, A., & Banaszuk, A. (2011) · Automatica · doi:10.1016/j.automatica.2011.09.019 · Cited by 87
“Several heuristics to partition graphs have been developed over the last few decades [15] including the Kernighan-Lin algorithm [16], Potts method [17], percolation based methods [18], horizontal-vertical decomposition [19] and spectral clustering [3,4].”
MethodSubspace Based Network Community Detection Using Sparse Linear Coding
Mahmood, A., & SMALL, M. P. (2015) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2015.2496345 · Cited by 83
Community structure of complex software systems: Analysis and applications
Šubelj, L., & Bajec, M. (2011) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2011.03.036 · Cited by 87
“Previous work has observed that these networks follow scale-free degree distributions and reveal small-world phenomena, when we here explore another property commonly found in complex networks, i.e. community structure.”
BackgroundOverlapped community detection in complex networks
Pizzuti, C. (2009) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/1569901.1570019 · Cited by 84
“TheClique Percolation Method of Palla et al. [7, 25] implemented in CFinder [1], finds k-clique percolation clusters, i.e. groups of nodes that can be reached via chains of k-cliques and the link in these cliques.”
BackgroundMethodResultInfluentialNetwork approaches for plant phylogenomic synteny analysis
Zhao, T., & Schranz, M. E. (2017) · Current Opinion in Plant Biology · doi:10.1016/j.pbi.2017.03.001 · Cited by 84
An Evolutionary Multiobjective Optimization Based Fuzzy Method for Overlapping Community Detection
Tian, Y., Yang, S., & Zhang, X. (2019) · IEEE Transactions on Fuzzy Systems · doi:10.1109/tfuzz.2019.2945241 · Cited by 81
“…overlapping communities, and a variety of techniques have been adopted to detect overlapping communities from then on, including clique percolation theory [7], local expansion [8], label propagation [9], link community detection [10], fuzzy clustering [11], and evolutionary computation [12].”
BackgroundMethodIdentifying power elites—k-cores in heterogeneous affiliation networks
Larsen, A. G., & Ellersgaard, C. (2017) · Social Networks · doi:10.1016/j.socnet.2017.03.009 · Cited by 87
Overlapping Community Detection Based on Node Importance and Adjacency Information
Wang, P., Huang, Y., Tang, F., Liu, H., & Lü, Y. (2021) · Security and Communication Networks · doi:10.1155/2021/8690662 · Cited by 77
“[15] is the first algorithm that can detect overlapping communities.”
BackgroundRetractedExperience of developing Twitter-based communities of practice in higher education
Lewis, B., & Rush, D. (2013) · Research in Learning Technology · doi:10.3402/rlt.v21i0.18598 · Cited by 77
Controlling nosocomial infection based on structure of hospital social networks
Ueno, T., & Masuda, N. (2008) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2008.07.001 · Cited by 77
“The entire network is composed of relatively dense subnetworks (also called communities or network modules in network literature, e.g. Girvan & Newman 2002; Palla et al. 2005) that are loosely interlinked in a hierarchical manner.”
BackgroundPractical Attacks Against Graph-based Clustering
Chen, Y., Nadji, Y., Kountouras, A., Monrose, F., Perdisci, R., Antonakakis, M., & Vasiloglou, N. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134083 · Cited by 52
“Communities are usually hierarchical [42, 47, 50]; however, finding sub-communities within communities is a known hard problem [15].”
BackgroundSpeeding Up Set Intersections in Graph Algorithms using SIMD Instructions
Han, S., Zou, L., & Yu, J. X. (2018) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3183713.3196924 · Cited by 77
“Note that there are also many clique-based community definitions, such as k-clique community [13, 31] and γ -quasi-k-clique [37].”
BackgroundAttea, B. A., Abbood, A. D., Hasan, A. A., Pizzuti, C., Al-Ani, M. F., Özdemir, S., & Al-Dabbagh, R. D. (2021) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2021.100885 · Cited by 87
Cognitive Computation with Autonomously Active Neural Networks: An Emerging Field
Gros, C. (2009) · Cognitive Computation · doi:10.1007/s12559-008-9000-9 · Cited by 82
Stochastic Competitive Learning in Complex Networks
Silva, T. C., & Zhao, L. (2012) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2011.2181866 · Cited by 82
“For example, it is well known that there is a strong connection between the structure of protein-protein interaction networks and protein functions [35].”
BackgroundSimple probabilistic algorithm for detecting community structure
Ren, W., Yan, G., Liao, X., & Xiao, L. (2009) · Physical Review E · doi:10.1103/physreve.79.036111 · Cited by 79
The organization of scientific knowledge: the structural characteristics of keyword networks
Yi, S., & Choi, J. (2011) · Scientometrics · doi:10.1007/s11192-011-0560-1 · Cited by 93
Estimating the resolution limit of the map equation in community detection
Kawamoto, T., & Rosvall, M. (2015) · Physical Review E · doi:10.1103/physreve.91.012809 · Cited by 87
Overlapping correlation clustering
Bonchi, F., Gionis, A., & Ukkonen, A. (2012) · Knowledge and Information Systems · doi:10.1007/s10115-012-0522-9 · Cited by 92
“The best known approach to detect overlapping communities is the CFinder algorithm based on clique percolation [41].”
MethodCao, X., Wang, X., Jin, D., Cao, Y., & He, D. (2013) · Scientific Reports · doi:10.1038/srep02993 · Cited by 82
“Nucleic acids research 28(1), 289–291 (2000).”
Small World in Motion (SWIM): Modeling Communities in Ad-Hoc Mobile Networking
Kosta, S., Mei, A., & Stefa, J. (2010) · IEEE International Conference on Sensing, Communication, and Networking (SECON) · doi:10.1109/secon.2010.5508278 · Cited by 76
“the number of members of the communities detected by the k-clique algorithm [19] is very close to a power law (see Figure 1(d)).”
BackgroundMethodInfluentialGRAPH THEORY AND COMPLEX NETWORKS
Duan, Z. (2008) · Lixue jinzhan · Cited by 76
Adaptive community detection incorporating topology and content in social networks✰
Qin, M., Jin, D., Lei, K., Gabryś, B., & Musial-Gabrys, K. (2018) · Knowledge-Based Systems · doi:10.1016/j.knosys.2018.07.037 · Cited by 88
Metadata
- Authors
- Palla, G., Derényi, I., Farkas, I., & Vicsek, T.
- Affiliations
- Hungarian Academy of Sciences (HU)
- Eötvös Loránd University (HU)
- Corresponding author
- Vicsek, Tamás
- Venue
- Nature
- Published
- 2005-06
- Volume
- 435
- Issue
- 7043
- Pages
- 814-818
- ISSN
- 0028-0836 (ISSN-L)
- 1476-4687
- OpenAlex
- W2164928285
- Cited by
- 5,373
- References
- 32
- Citations by year
- 2026: 94 · 2025: 165 · 2024: 156 · 2023: 169 · 2022: 222 · 2021: 254 · 2020: 263 · 2019: 322 · 2018: 394 · 2017: 327 · 2016: 323 · 2015: 392 · 2014: 442 · 2013: 351 · 2012: 356
- FWCI
- 86.26
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Nature (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- RePEc: Research Papers in Economics (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Bioinformatics and Genomic Networks
- Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Complex Systems and Time Series Analysis
- Keywords
- overlapping communities, community structure, complex networks, modular structure, community statistics, collaboration networks, word association networks, protein-protein interaction network, scaling behavior, network correlation
- MeSH terms
- Humans, Models, Biological, Protein Binding, Saccharomyces cerevisiae, Community Networks, Nature, Internet
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.