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 201–300 of 1,010
Bianconi, G. (2021) · doi:10.1017/9781108770996 · Cited by 223
Emergence of Communities in Weighted Networks
Kumpula, J. M., Onnela, J.-P., Saramäki, J., Kaski, K., & Kertész, J. (2007) · Physical Review Letters · doi:10.1103/physrevlett.99.228701 · Cited by 222
Overlapping stochastic block models with application to the French political blogosphere
Latouche, P., Birmelé, E., & Ambroise, C. (2011) · The Annals of Applied Statistics · doi:10.1214/10-aoas382 · Cited by 260
A game-theoretic framework to identify overlapping communities in social networks
Chen, W., Liu, Z., Sun, X., & Wang, Y. (2010) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0186-6 · Cited by 215
“[21]).”
BackgroundMethodInfluentialAcademic social networks: Modeling, analysis, mining and applications
Kong, X., Shi, Y., Yu, S., Liu, J., & Xia, F. (2019) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2019.01.029 · Cited by 200
Toivonen, R., Onnela, J.-P., Saramäki, J., Hyvönen, J., & Kaski, K. (2006) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2006.03.050 · Cited by 218
Assessing the relevance of node features for network structure
Bianconi, G., Pin, P., & Marsili, M. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0811511106 · Cited by 221
“Community∗ detection, for example, aims at uncovering a hidden classification of nodes, and a variety of methods have been proposed relying on (i) structural properties of the network [betweenness centrality (13), modularity (14), spectral decomposition (15), cliques (16), and hierarchical structure (17)], (ii) statis…”
BackgroundAn overview of social network analysis
Oliveira, M., & Gama, J. (2012) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1048 · Cited by 188
Clustering coefficient and community structure of bipartite networks
Zhang, P., Wang, J., Li, X., Li, M., Di, Z., & Fan, Y. (2008) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2008.09.006 · Cited by 201
Identifying the community structure of the international-trade multi-network
Barigozzi, M., Fagiolo, G., & Mangioni, G. (2011) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2011.02.004 · Cited by 210
“For instance, one may consider to apply algorithms allowing for overlapping communities [28,29].”
BackgroundIdentification of core-periphery structure in networks
Zhang, X., Martin, T., & Newman, M. E. J. (2015) · Physical Review E · doi:10.1103/physreve.91.032803 · Cited by 206
Social contact networks for the spread of pandemic influenza in children and teenagers
Glass, L. M., & Glass, R. J. (2008) · BMC Public Health · doi:10.1186/1471-2458-8-61 · Cited by 204
“Because people belong to multiple groups, the social contact network exhibits the overlapping quality of a structured community [ 15 ] with both clustering within a group (cliques) and the "small-world characteristic" of needing only a small number of contacts along links to reach any particular individual within the…”
BackgroundEffect of correlations on network controllability
Pósfai, M., Liu, Y.-Y., Slotine, J.-J., & Barabási, A.-L. (2013) · Scientific Reports · doi:10.1038/srep01067 · Cited by 203
Behavioral Operations and Supply Chain Management–A Review and Literature Mapping
Fahimnia, B., Pournader, M., Siemsen, E., Bendoly, E., & Wang, C. (2019) · Decision Sciences · doi:10.1111/deci.12369 · Cited by 201
A Survey of Sentiment Analysis from Social Media Data
Chakraborty, K., Bhattacharyya, S., & Bag, R. (2020) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2019.2956957 · Cited by 194
“Out of the algorithms that were implemented on large networks, study in [37] showed methods to explore extremely overlapping, nested and linked association of nodes in binary networks.”
MethodGeneral optimization technique for high-quality community detection in complex networks
Sobolevsky, S., Campari, R., Belyi, A., & Ratti, C. (2014) · Physical Review E · doi:10.1103/physreve.90.012811 · Cited by 206
“As pointed in [6], such a relation is frequently observed in real world networks.”
BackgroundHierarchical functional modularity in the resting‐state human brain
Ferrarini, L., Veer, I. M., Baerends, E., van Tol, M., Renken, R. J., van der Wee, N. J. A., Veltman, D. J., Aleman, A., Zitman, F. G., Penninx, B. W. J. H., et al. (2009) · Human Brain Mapping · doi:10.1002/hbm.20663 · Cited by 200
“We also tested the method proposed by Palla et al. [2005], since their solution aims at identifying nonoverlapping communities.”
MethodInfluentialGED: the method for group evolution discovery in social networks
Bródka, P., Saganowski, S., & Kazienko, P. (2013) · Social Network Analysis and Mining · doi:10.1007/s13278-012-0058-8 · Cited by 171
“Palla et al. (2007) have used clique percolation method (CPM) (Palla et al. 2005; Dere´nyi et al. 2005), which allows groups to overlap.”
MethodInfluentialRanking stability and super-stable nodes in complex networks
Ghoshal, G., & Barabási, A.-L. (2011) · Nature Communications · doi:10.1038/ncomms1396 · Cited by 205
Šubelj, L., & Bajec, M. (2011) · Physical Review E · doi:10.1103/physreve.83.036103 · Cited by 193
Wang, J., Li, M., Chen, J., & Pan, Y. (2011) · IEEE/ACM Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2010.75 · Cited by 196
Evaluating local community methods in networks
Bagrow, J. P. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/05/p05001 · Cited by 198
“Other methods (for example, [23, 25, 32]) concern themselves with local community structure, but either require global knowledge to first determine this structure, or are defined locally but do not provide a definitive partition necessary for evaluation [24, 25, 26, 27, 28, 29, 30, 31].”
MethodCoFIM: A community-based framework for influence maximization on large-scale networks
Shang, J., Zhou, S., Li, X., Liu, L., & Wu, H. (2017) · Knowledge-Based Systems · doi:10.1016/j.knosys.2016.09.029 · Cited by 196
Human-centric Computing and Information Sciences
(2013) · Human-centric Computing and Information Sciences · doi:10.1007/13673.2192-1962 · Cited by 198
A Unified Semi-Supervised Community Detection Framework Using Latent Space Graph Regularization
Yang, L., Cao, X., Jin, D., Wang, X., & Meng, D. (2015) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2014.2377154 · Cited by 197
“In the past few years, a large number of community detection algorithms have been proposed and some of them have achieved good performance in many fields [7], [8], [24]–[27].”
BackgroundMethodLocal resolution-limit-free Potts model for community detection
Ronhovde, P., & Nussinov, Z. (2010) · Physical Review E · doi:10.1103/physreve.81.046114 · Cited by 197
Community detection based on modularity and an improved genetic algorithm
Shang, R., Bai, J., Jiao, L., & Jin, C. (2013) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2012.11.003 · Cited by 197
“Palla, Dereny and Farkas proposed a group penetration algorithm, which is the first algorithm that can detect overlapping communities [9].”
BackgroundOverlapping communities in dynamic networks: their detection and mobile applications
Nguyen, N. P., Dinh, T. N., Tokala, S., & Thai, M. T. (2011) · Proceedings of the 17th annual international conference on Mobile computing and networking · doi:10.1145/2030613.2030624 · Cited by 192
Shaffer, S. M., Emert, B. L., Reyes Hueros, R. A., Cote, C., Harmange, G., Schaff, D. L., Sizemore, A. E., Gupte, R., Torre, E., Singh, A., et al. (2020) · Cell · doi:10.1016/j.cell.2020.07.003 · Cited by 194
“We performed k-clique community detection (Derényi et al., 2005; Jonsson et al., 2006; Palla et al., 2005) with k=4 on binarized networks created by thresholding the original weighted network at decreasing values (Giusti et al.”
The mRNA related ceRNA–ceRNA landscape and significance across 20 major cancer types
Xu, J., Li, Y., Lu, J., Pan, T., Ding, N., Wang, Z., Shao, T., Zhang, J., Wang, L., & Li, X. (2015) · Nucleic Acids Research · doi:10.1093/nar/gkv853 · Cited by 192
“All modules in the ceRNA networks are identified using CFinder (41).”
MethodCore-Periphery Structure in Networks (Revisited)
Rombach, P., Porter, M. A., Fowler, J. H., & Mucha, P. J. (2017) · SIAM Review · doi:10.1137/17m1130046 · Cited by 228
“Myriad methods have been developed to detect network communities [29, 30, 36, 61, 69], and several of these methods allow communities to overlap with each other [1, 2, 64].”
BackgroundCIM: Community-Based Influence Maximization in Social Networks
Chen, Y.-C., Zhu, W.-Y., Peng, W.-C., Lee, W.-C., & Lee, S.-Y. (2014) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/2532549 · Cited by 180
“The time complexity of most community detection algorithms [Bortner and Han 2010; Danon et al. 2005; Ester et al. 1996; Feng et al. 2007; Girvan and Newman 2002; Huang et al. 2010; Lancichinetti et al. 2009; Ng et al. 2001; Newman 2004; Palla et al. 2005; Ruan and Zhang 2007; Wan et al. 2008; White and Smyth 2005; Xu…”
BackgroundIdentifying network communities with a high resolution
Ruan, J., & Zhang, W. (2008) · Physical Review E · doi:10.1103/physreve.77.016104 · Cited by 187
“Such characteristics include heterogenous community sizes [33], hierarchical structures [34], overlapping communities [35], and fuzzy communities [36].”
Background20 years of network community detection
Fortunato, S., & Newman, M. E. J. (2022) · Nature Physics · doi:10.1038/s41567-022-01716-7 · Cited by 184
Computing communities in large networks using random walks (long version)Preprint
Pons, P., & Latapy, M. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.physics/0512106 · Cited by 229
Community Detection in Complex Networks: Multi–objective Enhanced Firefly Algorithm
Amiri, B., Hossain, L., Crawford, J. W., & Wigand, R. T. (2013) · Knowledge-Based Systems · doi:10.1016/j.knosys.2013.01.004 · Cited by 189
Limited resolution in complex network community detection with Potts model approach
Kumpula, J. M., Saramäki, J., Kaski, K., & Kertész, J. (2007) · The European Physical Journal B · doi:10.1140/epjb/e2007-00088-4 · Cited by 189
Overlapping community detection using seed set expansion
Whang, J. J., Gleich, D. F., & Dhillon, I. S. (2013) · Proceedings of the 22nd ACM international conference on Information & Knowledge Management · doi:10.1145/2505515.2505535 · Cited by 188
A comparative study of social network models: Network evolution models and nodal attribute models
Toivonen, R., Kovanen, L., Kivelä, M., Onnela, J.-P., Saramäki, J., & Kaski, K. (2009) · Social Networks · doi:10.1016/j.socnet.2009.06.004 · Cited by 184
“We also identify communities using the k-cliquepercolation method developed by Palla et al. (2005). The method defines a k-cluster as a subgraph within which all nodes can be reached by ‘rolling’ a k-clique such that all except one of its nodes are fixed (see Fig.”
MethodEpidemic spreading on higher-order networks
Wang, W., Nie, Y., Li, W., Lin, T., Shang, M.-S., Su, S., Tang, Y., Zhang, Y.-C., & Sun, G.-Q. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.01.003 · Cited by 176
Overlapping community detection via bounded nonnegative matrix tri-factorization
Zhang, Y., & Yeung, D.-Y. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339629 · Cited by 178
“The first method for this problem, called the clique percolation method (CPM), was proposed in [16].”
MethodGoogling Investor Sentiment around the World
Gao, Z., Ren, H., & Zhang, B. (2020) · Journal of Financial and Quantitative Analysis · doi:10.1017/s0022109019000061 · Cited by 178
Clique graphs and overlapping communities
Evans, T. (2010) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2010/12/p12037 · Cited by 202
Fuzzy overlapping communities in networks
Gregory, S. (2011) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2011/02/p02017 · Cited by 209
“Numerous community detection algorithms have been d eveloped, using a variety of techniques: removal of high-betweenness edges [1], modularity o ptimization [2, 3], detection of dense subgraphs [4], statistical inference [5], and many more.”
InfluentialExploring local community structures in large networks
Luo, F., Wang, J. Z., & Promislow, E. (2008) · Web Intelligence and Agent Systems: An International Journal · doi:10.3233/wia-2008-0147 · Cited by 175
“Further study of the identified communities reveals that digital media items are much easier to form compact local communities than book items do.”
Havlin, S., Kenett, D. Y., Ben-Jacob, E., Bunde, A., Cohen, R., Hermann, H., Kantelhardt, J. W., Kertész, J., Kirkpatrick, S., Kurths, J., et al. (2012) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2012-01695-x · Cited by 187
A Fast Algorithm to Find Overlapping Communities in Networks
Gregory, S. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-87479-9_45 · Cited by 174
“We compare its performance and execution time with both CONGA and CFinder [20], another state-of-the art algorithm for finding overlapping communities.”
BackgroundMethodInfluentialStructure and Overlaps of Ground-Truth Communities in Networks
Yang, J., & Leskovec, J. (2014) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/2594454 · Cited by 189
Mobility Models, Traces and Impact of Mobility on Opportunistic Routing Algorithms: A Survey
Batabyal, S., & Bhaumik, P. (2015) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2015.2419819 · Cited by 180
“K-Clique [99], and Fiedler [100] are two centralized community detection algorithms.”
Design Study of LineSets, a Novel Set Visualization Technique
Alper, B., Riche, N., Ramos, G., & Czerwinski, M. (2011) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2011.186 · Cited by 177
“To limit the visual clutter and increase the readability of complex set representations, we propose the use of geometrically continuous lines, called LineSets (Figure 1).”
MethodTracking community evolution in social networks: A survey
Dakiche, N., Benbouzid-Si Tayeb, F., Slimani, Y., & Benatchba, K. (2019) · Information Processing & Management · doi:10.1016/j.ipm.2018.03.005 · Cited by 175
Chen, B., Fan, W., Liu, J., & Wu, F.-X. (2014) · Briefings in Bioinformatics · doi:10.1093/bib/bbt039 · Cited by 179
“Although it is difficult to tell their identical structures, various attempts have been made based on topological structures, such as cliques [12, 15–17], dense sub-graphs [18–24], core-attachment structures [25–29] and star-like structures [30], to identify protein complexes from PPI networks.”
BackgroundWorldwide spreading of economic crisis
Garas, A., Argyrakis, P., Rozenblat, C., Tomassini, M., & Havlin, S. (2010) · New Journal of Physics · doi:10.1088/1367-2630/12/11/113043 · Cited by 178
Community Detection and Stochastic Block Models
Abbe, E. A. (2018) · Foundations and Trends® in Communications and Information Theory · doi:10.1561/0100000067 · Cited by 685
Comparative evaluation of community detection algorithms: a topological approach
Orman, G. K., Labatut, V., & Cherifi, H. (2012) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2012/08/p08001 · Cited by 192
“They can therefore be considered as complementary, and we recommend applying both of them in order to perform a complete and accurate assessment.”
BackgroundMethodConsistency of Network Modules in Resting-State fMRI Connectome Data
Moussa, M. N., Steen, M. R., Laurienti, P. J., & Hayasaka, S. (2012) · PLoS ONE · doi:10.1371/journal.pone.0044428 · Cited by 160
Jonsson, P. F., Cavanna, T., Zicha, D., & Bates, P. A. (2006) · BMC Bioinformatics · doi:10.1186/1471-2105-7-2 · Cited by 178
“The resulting 10,628 interactions were then analysed using CFinder [27], which locates maximal complete subgraphs ( k - cliques) in the networks and then identifies 'communities' by carrying out standard component analysis of the clique-clique overlap.”
BackgroundMethodInfluentialWang, M., Wang, C., Yu, J. X., & Zhang, J. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2794367.2794370 · Cited by 175
“Based on the original approach [20], the Sequential Clique Percolation (SCP) [14] algorithm sequentially generates cliques to form connected communities.”
MethodKao, R. R., Green, D. M., Johnson, J., & Kiss, I. Z. (2007) · Journal of The Royal Society Interface · doi:10.1098/rsif.2007.1129 · Cited by 166
“the existence of more closely linked nodes in subgroups of the population (e.g. Girvan & Newman 2002; Palla et al. 2005).”
BackgroundSurvey on Social Community Detection
Plantié, M., & Crampes, M. (2013) · Computer Communications and Networks · doi:10.1007/978-1-4471-4555-4_4 · Cited by 169
“• cohesive subgraph discovery [53], • vertex clustering [56], • community quality optimization [48, 11], • divisive [48] • and model-based methods [23].”
BackgroundMethodInfluentialAhmadlou, M., & Adeli, H. (2011) · NeuroImage · doi:10.1016/j.neuroimage.2011.04.070 · Cited by 171
“Analysis of communities among sub-parts of a system is increasingly used for social networks (Girvan and Newman, 2002; Palla et al., 2005; Mann et al., 2008; Chen and Redner, 2010), ecological networks (Tschirhart, 2002; Pusch et al.”
Dynamic patterns of information flow in complex networks
Harush, U., & Barzel, B. (2017) · Nature Communications · doi:10.1038/s41467-017-01916-3 · Cited by 172
“To observe this we show that, on average, the contribution of the A ij link to the propagation of information follows (Supplementary Note 1) where ξ = ω − 1 and ω is taken from (8).”
BackgroundInfluentialInferring social network structure in ecological systems from spatio-temporal data streams
Psorakis, I., Roberts, S. J., Rezek, I., & Sheldon, B. C. (2012) · Journal of The Royal Society Interface · doi:10.1098/rsif.2012.0223 · Cited by 171
“in their 2005 paper [14] have shown that network communities can be seen as aggregations of adjacent cliques.”
BackgroundEffect of correlations on network controllability
Liu, Y., Pósfai, M., Slotine, J.-J. E., & Barabási, A.-Ĺ. (2012) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 171
Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences
Kovanen, L., Kaski, K., Kertész, J., & Saramäki, J. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1307941110 · Cited by 169
“We use clique percolation (36) to create a dichotomy for local edge density: Event ei = ðvi;0; vi;1; ti; δiÞ is a “dense event” if the edge ðvi; vjÞ of the aggregate network is inside a four-clique community, and otherwise ei is a “sparse event.”
MethodUsing Social Network Measures in Wildlife Disease Ecology, Epidemiology, and Management
Silk, M. J., Croft, D. P., Delahay, R. J., Hodgson, D. J., Boots, M., Weber, N. L., & McDonald, R. A. (2016) · BioScience · doi:10.1093/biosci/biw175 · Cited by 183
Centralities in simplicial complexes. Applications to protein interaction networks
Estrada, E., & Ross, G. J. (2017) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2017.11.003 · Cited by 191
“One of its main drawbacks is its focus on binary relations only (Evans, 2010; Palla et al., 2005).”
BackgroundSemantic integration to identify overlapping functional modules in protein interaction networks
Cho, Y.-R., Hwang, W., Ramanathan, M., & Zhang, A. (2007) · BMC Bioinformatics · doi:10.1186/1471-2105-8-265 · Cited by 166
“Next, we compared the performance of the flow-based modularization algorithm to three competing state-ofthe-art methods: the CFinder algorithm [22] as a densitybased method, the betweenness-cut algorithm [32,33] as a hierarchical approach, and the STM algorithm [34].”
BackgroundMethodIndex-Based Densest Clique Percolation Community Search in Networks
Yuan, L., Qin, L., Zhang, W., Chang, L., & Yang, J. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2783933 · Cited by 164
Complex network analysis of free-energy landscapes
Gfeller, D., De Los Rios, P., Caflisch, A., & Rao, F. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0608099104 · Cited by 165
Detecting criminal organizations in mobile phone networks
Ferrara, E., De Meo, P., Catanese, S., & Fiumara, G. (2014) · Expert Systems with Applications · doi:10.1016/j.eswa.2014.03.024 · Cited by 164
“Strategies to work around both limitations exist, and recently some approaches have been proposed to discover overlapping communities [41, 42], in order to allow nodes to belong to different communities.”
BackgroundLi, H.-J., Bu, Z., Li, A., Liu, Z., & Shi, Y. (2016) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2563425 · Cited by 164
“Palla et al. proposed a clique percolation technique [29] which is mainly used to find overlapping communities in networks.”
MethodHow to design multi-target drugs: target search options in cellular networks
Korcsmáros, T., Szalay, M. S., Böde, C., Kovács, I. A., & Csermely, P. (2007) · Expert Opinion on Drug Discovery · doi:10.1517/17460441.2.6.799 · Cited by 155
“• overlaps of network communities [31] , which have a key role in the regulation of complex systems [29] , may be efficient guides to restrict the initial target pool in search of target sets for multi-target drugs • differential analysis of relevant cellular networks, (such as signaling networks, gene-regulatory netw…”
BackgroundA Maximal Clique Based Multiobjective Evolutionary Algorithm for Overlapping Community Detection
Wen, X., Chen, W.-N., Lin, Y., Gu, T., Zhang, H., Li, Y., Yin, Y., & Zhang, J. (2016) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2016.2605501 · Cited by 162
Community structure in Congressional cosponsorship networks
Zhang, Y., Friend, A. J., Traud, A. L., Porter, M. A., Fowler, J. H., & Mucha, P. J. (2008) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2007.11.004 · Cited by 159
Recent advances in clustering methods for protein interaction networks
Wang, J., Li, M., Deng, Y., & Pan, Y. (2010) · BMC Genomics · doi:10.1186/1471-2164-11-s3-s10 · Cited by 160
“In 2005, Palla et al.[ 69 ] investigated the overlapping structures in complex networks and proposed a Clique Percolation Method (CPM).”
BackgroundHigh quality, scalable and parallel community detection for large real graphs
Prat-Pèrez, A., Domínguez-Sal, D., & Larriba-Pey, J.-L. (2014) · International World Wide Web Conference (WWW) · doi:10.1145/2566486.2568010 · Cited by 180
“In such work, they measure the time spent by several state of the art algorithms, such as clique percolation [16] or link clustering [1], and found that they did not scale to networks with more than hundreds of thousands of edges.”
BackgroundCommunity extraction for social networks
Zhao, Y., Levina, E., & Zhu, J. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1006642108 · Cited by 171
Wang, J., Peng, X., Li, M., & Pan, Y. (2013) · PROTEOMICS · doi:10.1002/pmic.201200277 · Cited by 161
“Clique percolation method (CPM) [29] is a powerful algorithm to find protein complex.”
MethodInfluentialCommunities, knowledge creation, and information diffusion
Lambiotte, R., & Panzarasa, P. (2009) · Journal of Informetrics · doi:10.1016/j.joi.2009.03.007 · Cited by 183
Spectral Entropies as Information-Theoretic Tools for Complex Network Comparison
De Domenico, M., & Biamonte, J. (2016) · Physical Review X · doi:10.1103/physrevx.6.041062 · Cited by 160
Palla, G., Farkas, I. J., Pollner, P., Derényi, I., & Vicsek, T. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/186 · Cited by 190
Self-citationLocal modularity measure for network clusterizations
Muff, S., Rao, F., & Caflisch, A. (2005) · Physical Review E · doi:10.1103/physreve.72.056107 · Cited by 162
Azad, A., Pavlopoulos, G. A., Ouzounis, C., Kyrpides, N. C., & Buluç, A. (2018) · Nucleic Acids Research · doi:10.1093/nar/gkx1313 · Cited by 181
“These algorithms include SPICi (11), MCUPGMA (48), SPC (49), MCODE (13), DPClus (16613608), RNSC (50) and CFinder (51).”
MethodDetection of Overlapping Communities in Dynamical Social Networks
Cazabet, R., Amblard, F., & Hanachi, C. (2010) · doi:10.1109/socialcom.2010.51 · Cited by 174
Overlapping Communities Explain Core–Periphery Organization of Networks
Yang, J., & Leskovec, J. (2014) · Proceedings of the IEEE · doi:10.1109/jproc.2014.2364018 · Cited by 159
Plan, Activity, and Intent Recognition
Sukthankar, G., Geib, C., Bui, H., Pynadath, D. V., & Goldman, R. P. (2014) · Elsevier eBooks · doi:10.1016/c2012-0-01169-6 · Cited by 182
Phylomemetic Patterns in Science Evolution—The Rise and Fall of Scientific Fields
Chavalarias, D., & Cointet, J. (2013) · PLoS ONE · doi:10.1371/journal.pone.0054847 · Cited by 183
“We chose a very simple and comprehensible methods to define our clusters: in line with [23] we define scientific fields as directed cliques of terms in G.”
MethodClustering in complex networks. I. General formalism
Serrano, M. Á., & Boguñá, M. (2006) · Physical Review E · doi:10.1103/physreve.74.056114 · Cited by 181
Topic oriented community detection through social objects and link analysis in social networks
Zhao, Z., Feng, S., Wang, Q., Huang, J. Z., Williams, G. J., & Fan, J. (2011) · Knowledge-Based Systems · doi:10.1016/j.knosys.2011.07.017 · Cited by 173
“The heuristic methods often design a graph clustering algorithm based on intuitive assumptions (e.g.,MFCalgorithm[9],HITSalgorithm[10],GNalgortihm[11],WH algorithm [12], CPM algorithm [13], FEC algorithm [14]).”
MethodSynchronization processes in complex networks
Arenas, A., Díaz-Guilera, A., & Pérez-Vicente, C. J. (2006) · Physica D: Nonlinear Phenomena · doi:10.1016/j.physd.2006.09.029 · Cited by 159
CommunityGAN: Community Detection with Generative Adversarial Nets
Jia, Y., Zhang, Q., Zhang, W., & Wang, X. (2019) · International World Wide Web Conference (WWW) · doi:10.1145/3308558.3313564 · Cited by 189
“3) On the whole, the performance of 4 graph representation learning methods (node2vec, LINE, Graph-GAN, ComE) falls with the increase of overlapping density among communities, while 3 traditional overlapping community detection methods (MMSB, CPM, AGM) keep relatively steady.”
BackgroundInfluentialMahoney, J. M., Taroni, J., Martyanov, V., Wood, T. A., Greene, C. S., Pioli, P. A., Hinchcliff, M. E., & Whitfield, M. L. (2015) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1004005 · Cited by 153
“We detected communities in the information graph using a variant of clique percolation [17], a network community detection procedure that, in this case, explicitly identifies communities of triangles (S1 Text).”
MethodDiscovering Overlapping Groups in Social Media
Wang, X., Tang, L., Gao, H., & Liu, H. (2010) · Proceedings · doi:10.1109/icdm.2010.48 · Cited by 178
From pull-down data to protein interaction networks and complexes with biological relevance
Zhang, B., Park, B.-H., Karpinets, T., & Samatova, N. F. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn036 · Cited by 153
Wei, K., Liang, X., & Xu, K. (2013) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2013.042313.00103 · Cited by 169
Understanding emotion with brain networks
Pessoa, L. (2017) · Current Opinion in Behavioral Sciences · doi:10.1016/j.cobeha.2017.09.005 · Cited by 167
Community detection with the Label Propagation Algorithm: A survey
Garza, S. E., & Schaeffer, S. E. (2019) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2019.122058 · Cited by 176
The Differential Role of Central and Bridge Symptoms in Deactivating Psychopathological Networks
Castro, D., Ferreira, F., Castro, I., Rodrigues, A. R., Correia, M., Ribeiro, J., & Ferreira, T. B. (2019) · Frontiers in Psychology · doi:10.3389/fpsyg.2019.02448 · Cited by 159
“Blanken et al. (2018) have assumed an alternative perspective in exploring the usefulness of the Clique Percolation Method (CPM; Palla et al., 2005; Adamcsek et al., 2006) to detect overlapping modules in psychopathological networks.”
BackgroundLuo, X., Liu, Z., Jin, L., Zhou, Y., & Zhou, M. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.3041360 · Cited by 155
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.