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 901–1,000 of 1,010
Data offloading in social mobile networks through VIP delegation
Barbera, M. V., Viana, A. C., de Amorim, M. D., & Stefa, J. (2014) · Ad Hoc Networks · doi:10.1016/j.adhoc.2014.01.012 · Cited by 48
“After applying the k-clique algorithm [18] to determine the communities and with respect to the campus-like scenarios, we have the following parameters: the Dartmouth dataset has 24 communities of 41 members in average, the SWIM-500 trace has 16 communities with 32 members in average, the D-SWIM-1500 trace has 39 comm…”
MethodOverlapping Community Detection Based on Structural Centrality in Complex Networks
Wang, X., Liu, G., & Li, J. (2017) · IEEE Access · doi:10.1109/access.2017.2769484 · Cited by 48
A community discovery algorithm based on boundary nodes and label propagation
Gui, Q., Deng, R., Xue, P., & Cheng, X. (2017) · Pattern Recognition Letters · doi:10.1016/j.patrec.2017.12.018 · Cited by 48
“[22] The algorithm extends the traditional community model that allows nodes belonging to several communities, and this topic quickly became a research hotspot for community discovery.”
BackgroundRobust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks
Fan, N., & Pardalos, P. M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17458-2_15 · Cited by 48
“Despite of these difficulties, several methods for community detection have been developed and employed with application in different areas successfully, such as minimum-cut method [11], hierarchical clustering, Girvan-Newman algorithm [9], modularity maximization [12], and clique percolation method [ 13 ].”
MethodPerspective: network-guided pattern formation of neural dynamics
Hütt, M. ‐., Kaiser, M., & Hilgetag, C. C. (2014) · Philosophical Transactions of the Royal Society B Biological Sciences · doi:10.1098/rstb.2013.0522 · Cited by 60
“There exists a wide range of different algorithms to detect clusters of a network, for example, (Hilgetag et al., 2000; Girvan & Newman, 2002; Palla et al., 2005).”
Overlapping Community Change-Point Detection in an Evolving Network
Cheng, J., Chen, M., Zhou, M., Gao, S., Liu, C., & Liu, C. (2018) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2018.2880780 · Cited by 48
“In these networks, overlapping communities [9], [10] can reveal the hidden or implicit relationships among a group of individuals, and usually represent different functional modules of the underlying system.”
BackgroundMethodModularity maximization as a flexible and generic framework for brain network exploratory analysis
Esfahlani, F. Z., Jo, Y., Puxeddu, M. G., Merritt, H., Tanner, J., Greenwell, S. A., Patel, R., Faskowitz, J., & Betzel, R. F. (2021) · NeuroImage · doi:10.1016/j.neuroimage.2021.118607 · Cited by 57
Overlapping Graph Clustering in Attributed Networks via Generalized Cluster Potential Game
Li, H., Feng, Y., Xia, C., & Cao, J. (2023) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3597436 · Cited by 58
“For node-based methods, Palla et al. [8] proposed the Clique Percolation Method ( CPM ), which uses the definition k -clique as the indicator of network clusters.”
MethodBhattacharyya, M., Ghosh, A., Hansia, P., & Vishveshwara, S. (2009) · Proteins Structure Function and Bioinformatics · doi:10.1002/prot.22573 · Cited by 48
SMART: A Social- and Mobile-Aware Routing Strategy for Disruption-Tolerant Networks
Zhu, K., Li, W., & Fu, X. (2014) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2014.2298494 · Cited by 47
“We evaluate the performance of SMART using different community partitioning algorithms, including the m-partition algorithm, the k-clique percolation algorithm [31] (which considers the adjacent k-clique as communities), and the Girvan–Newman algorithm [28] (which continues removing edges with the highest betweenness…”
MethodDetecting Overlapping Community Structures in Networks
Fang, W. H., Qian, W., Wang, C., & Zhou, A. (2009) · World Wide Web · doi:10.1007/s11280-009-0060-x · Cited by 47
“[23] think a community can be interpreted as a union of smaller fullyconnected subgraphs that share vertices.”
BackgroundHierarchical community detection with applications to real-world network analysis
Yang, B. X., Jin, D., Liu, J., & Liu, D. (2012) · Data & Knowledge Engineering · doi:10.1016/j.datak.2012.09.002 · Cited by 49
Reihanian, A., Feizi‐Derakhshi, M., & Aghdasi, H. S. (2017) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2017.03.007 · Cited by 52
“Apart from optimization-based methods, heuristic methods such as GN algorithm (Girvan and Newman, 2002) and Clique Percolation Method (CPM) (Palla et al., 2005) design a graph clustering algorithm based on intuitive assumptions (Zhao et al.”
MethodCommunity Hiding by Link Perturbation in Social Networks
Chen, X., Jiang, Z., Li, H., Ma, J., & Yu, P. S. (2021) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2021.3054115 · Cited by 51
Extracting Communities from Complex Networks by the k-Dense Method
Saito, K., Yamada, T., & Kazama, K. (2008) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1093/ietfec/e91-a.11.3304 · Cited by 47
“[2] is defined as a union of all the k-cliques that can be reached from each other thorough a series of adjacent k-cliques.”
BackgroundMethodInfluentialA Social Identity Approach to Identify Familiar Strangers in a Social Network
Agarwal, N., Liu, H., Murthy, S., Sen, A., & Wang, X. (2009) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v3i1.13946 · Cited by 53
“Authors in (Rosen-Zvi et al. 2004)(McCallum et al. 2005) use LDA and its variations to mine relationships between people based on the content.”
BackgroundProteomics Signature Profiling (PSP): A Novel Contextualization Approach for Cancer Proteomics
Goh, W. W. B., Lee, Y. H., Ramdzan, Z. M., Sergot, M. J., Chung, M. C. M., & Wong, L. (2012) · Journal of Proteome Research · doi:10.1021/pr200698c · Cited by 46
General clique percolation in random networks
Fan, J., & Chen, X. (2014) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/107/28005 · Cited by 46
Zhang, X.-F., Dai, D., Ou-Yang, L., & Yan, H. (2014) · BMC Bioinformatics · doi:10.1186/1471-2105-15-186 · Cited by 51
“We resort to test how well the set of multi-group proteins predicted by GMFTP matches with those of the other methods which also handle overlaps (CFinder, ClusterONE, Linkcomm, MINE and SR-MCL) and the two gold standards (CYC2008 and SGD).”
A new clustering method and its application in social networks
Zhao, P., & Zhang, C. (2011) · Pattern Recognition Letters · doi:10.1016/j.patrec.2011.06.008 · Cited by 47
“The overlapping clustering is a concept that has recently received increased attention in (Palla et al., 2005; Pereira-Leal et al., 2004; Futschik and Carlisle, 2005), etc.”
BackgroundProtein Complex Prediction in Large Ontology Attributed Protein-Protein Interaction Networks
Zhang, Y., Lin, H., Yang, Z., Wang, J., Li, Y., & Xu, B. (2013) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2013.86 · Cited by 46
An efficient community detection method based on rank centrality
Jiang, Y., Jia, C., & Yu, J. J. (2012) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2012.12.013 · Cited by 48
Identification of hybrid node and link communities in complex networks
He, D., Jin, D., Chen, Z., & Zhang, W. (2015) · Scientific Reports · doi:10.1038/srep08638 · Cited by 47
Stetz, G., & Verkhivker, G. M. (2015) · PLoS ONE · doi:10.1371/journal.pone.0143752 · Cited by 46
“Computation of the network parameters was performed using the Clique Percolation Method as implemented in the CFinder program [168].”
MethodInfluentialBetweenness centrality in Delay Tolerant Networks: A survey
Magaia, N., Francisco, A. P., Pereira, P. R., & Correia, M. P. (2015) · Ad Hoc Networks · doi:10.1016/j.adhoc.2015.05.002 · Cited by 51
Influence Propagation Model for Clique-Based Community Detection in Social Networks
Alduaiji, N., Datta, A., & Li, J. (2018) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2018.2831694 · Cited by 54
“The clique percolation method (CPM) [11], one of the well-known”
BackgroundMethodA social communication model based on simplicial complexes
Wang, D., Zhao, Y., Leng, H., & SMALL, M. P. (2020) · Physics Letters A · doi:10.1016/j.physleta.2020.126895 · Cited by 46
Community detection in complex networks using network embedding and gravitational search algorithm
Kumar, S., Panda, B. S., & Aggarwal, D. (2020) · Journal of Intelligent Information Systems · doi:10.1007/s10844-020-00625-6 · Cited by 49
“The node-centric Clique Percolation Method (CPM) rely on pre-defined substructures like finding cliques and k -cores within the network, which extracts all the maximal cliques in the network, to determine communities (Palla et al. 2005).”
MethodSpectral and network methods in the analysis of correlation matrices of stock returns
Heimo, T., Saramäki, J., Onnela, J.-P. “., & Kaski, K. K. (2007) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2007.04.124 · Cited by 46
Identification of Hierarchical and Overlapping Functional Modules in PPI Networks
Wang, J., Ren, J., Li, M., & Wu, F. (2012) · IEEE Transactions on NanoBioscience · doi:10.1109/tnb.2012.2210907 · Cited by 46
Link prediction in a user–object network based on time-weighted resource allocation
Liu, J., & Deng, G. (2009) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2009.05.021 · Cited by 46
Park, Y., & Bader, J. S. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts211 · Cited by 45
Vafaii, H., Mandino, F., Desrosiers-Grégoire, G., O’Connor, D. A., Markicevic, M., Shen, X., Ge, X., Hermán, P., Hyder, F., Papademetris, X., et al. (2024) · Nature Communications · doi:10.1038/s41467-023-44363-z · Cited by 50
Modeling the clustering in citation networks
Ren, F., Shen, H., & Cheng, X. (2012) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2012.02.001 · Cited by 45
“The clusters are gained by clique percolation method [25] with k = 4.”
BackgroundMethodResultInfluentialTrapping in scale-free networks with hierarchical organization of modularity
Zhang, Z., Lin, Y., Gao, S., Zhou, S., Guan, J., & Li, M. (2009) · Physical Review E · doi:10.1103/physreve.80.051120 · Cited by 45
Control range: a controllability-based index for node significance in directed networks
Wang, B., Gao, L., & Gao, Y. (2012) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2012/04/p04011 · Cited by 54
“For instance, some modules are almost consistent with the original definition of these words, such as { ‘Path’, We have also performed experiments using the algorithms Infomap [12], CPM [11] and modularity optimization method [31] on this network.”
MethodMulti-scale community detection using stability optimisation
Martelot, E. L., & Hankin, C. (2013) · International Journal of Web Based Communities · doi:10.1504/ijwbc.2013.054907 · Cited by 46
Link Clustering with Extended Link Similarity and EQ Evaluation Division
Huang, L., Wang, G., Wang, Y., Blanzieri, E., & Su, C. (2013) · PLoS ONE · doi:10.1371/journal.pone.0066005 · Cited by 45
“Hence, traditional methods are inadequate in identifying appropriate communities when overlaps are significant [5].”
BackgroundMethodInfluentialCommunity detection in complex networks using extended compact genetic algorithm
Li, J., & Song, Y. (2012) · Soft Computing · doi:10.1007/s00500-012-0942-1 · Cited by 50
“Additionally, clique percolation method (CPM) is the most popular technique to find overlapping communities (Palla et al. 2005; Fortunato 2010).”
MethodTriangles to Capture Social Cohesion
Friggeri, A., Chelius, G., & Eric Fleury, B. (2011) · International Conference on Social Computing · doi:10.1109/passat/socialcom.2011.169 · Cited by 45
“” Naturally, other techniques such as the clique percolation method [5] which do not rely on modularity were introduced – clique percolation goes even further as the method does not evaluate the quality of communities.”
MethodMining maximal cliques from a large graph using MapReduce: Tackling highly uneven subproblem sizes
Svendsen, M. S., Mukherjee, A. P., & Tirthapura, S. (2014) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2014.08.011 · Cited by 45
“MCE is a fundamental problem in graph analysis, and has been used widely, for instance, in clustering and community detection in social and biological networks [35], in the study of the co-expression of genes under stress [37], in integrating different types of genome mapping data [19], and other applications in bio-i…”
BackgroundDetecting Communities in Large Networks by Iterative Local Expansion
Chen, J., Zai͏̈ane, O. R., & Goebel, R. G. (2009) · International Conference on Computational Aspects of Social Networks (CASoN) · doi:10.1109/cason.2009.29 · Cited by 46
“Based on these observations, fuzzy methods [9], [34], [35], [36] have been proposed for overlapping structure.”
MethodBackbone Discovery in Social Networks
Du, N., Wu, B., & Wang, B. (2007) · IEEE/WIC/ACM International Conference on Web Intelligence · doi:10.1109/wi.2007.36 · Cited by 45
“Similar to [9], we assume that the message transmission and processing delay has an asymptotic upper bound.”
Discovering communities in complex networks by edge label propagation
Liu, W., Jiang, X., Pellegrini, M. A., & Wang, X. (2016) · Scientific Reports · doi:10.1038/srep22470 · Cited by 50
NCMine: Core-peripheral based functional module detection using near-clique mining
Tadaka, S., & Kinoshita, K. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btw488 · Cited by 45
Stetz, G., & Verkhivker, G. M. (2016) · Journal of Chemical Information and Modeling · doi:10.1021/acs.jcim.5b00755 · Cited by 46
Modeling customer preferences using multidimensional network analysis in engineering design
Wang, M., Chen, W., Huang, Y. M., Contractor, N., & Fu, Y. (2016) · Design Science · doi:10.1017/dsj.2016.11 · Cited by 46
Transient Community Detection and Its Application to Data Forwarding in Delay Tolerant Networks
Zhang, X., & Cao, G. (2017) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2017.2708090 · Cited by 45
“Moreover, Clique Percolation Method (CPM) or called K-clique [18] has been proposed to detect communities in both weighted and unweighted network.”
BackgroundMethodRevealing the role of node similarity and community merging in community detection
Zhang, J., Ding, X., & Yang, J. (2018) · Knowledge-Based Systems · doi:10.1016/j.knosys.2018.12.009 · Cited by 45
Evolutionary Divide-and-Conquer Algorithm for Virus Spreading Control Over Networks
Zhao, T.-F., Chen, W., Kwong, S., Gu, T., Yuan, H., Zhang, J., & Zhang, J. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.2975530 · Cited by 45
“The test algorithms include: the clique percolation method (CPM) [45], the expectation–maximization (EM) algorithm [46], the Girvan–Newman (GN) algorithm [47], the Louvain method (Louvain) [34], the Lancichinetti– Fortunato method (LFM) [48], the label propagation algorithm (LPA) [49], and the…”
MethodCommunity detection in weighted networks: Algorithms and applications
Lu, Z., Wen, Y., & Cao, G. (2013) · IEEE International Conference on Pervasive Computing and Communications · doi:10.1109/percom.2013.6526730 · Cited by 45
“Among these detection algorithms, CFinder [11] and RAK [12] are the most popular and efficient ones.”
BackgroundMethodInfluential-core architecture and -core percolation on complex networks
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2006) · Physica D Nonlinear Phenomena · doi:10.1016/j.physd.2006.09.027 · Cited by 46
Community detection in social networks
Fani, H., & Bagheri, E. (2017) · Encyclopedia with Semantic Computing and Robotic Intelligence · doi:10.1142/s2425038416300019 · Cited by 52
Identifying spreading influence nodes for social networks
Ou, Y., Guo, Q., & Liu, J.-G. (2022) · Frontiers of Engineering Management · doi:10.1007/s42524-022-0190-8 · Cited by 48
“However, the community structure of a network may change when applying different community detection algorithms (Palla et al., 2005; Newman, 2006; Pan et al., 2010; Tang et al., 2016), leading to this strategy being unstable.”
MethodStochastic block model and exploratory analysis in signed networks
Jiang, J. Q. (2015) · Physical Review E · doi:10.1103/physreve.91.062805 · Cited by 57
Percolation Computation in Complex Networks
Reid, F., McDaid, A. F., & Hurley, N. (2012) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2012.54 · Cited by 44
“in supplementary material [1], follows the method of Everett and Borgatti, finding all maximal cliques, by a custom method, and generating the overlap matrix between these cliques.”
MethodImmunization Strategies Based on the Overlapping Nodes in Networks with Community Structure
Chakraborty, D., Singh, A. K., & Cherifi, H. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-42345-6_6 · Cited by 44
“Our analysis of ground truth data shows us that the size of communities within a network follow a power-law property confirming with the existing literature [19].”
BackgroundMethodInfluentialAn Analysis of Overlapping Community Detection Algorithms in Social Networks
Devi, J. C., & Poovammal, E. (2016) · Procedia Computer Science · doi:10.1016/j.procs.2016.06.082 · Cited by 44
“Various community detection approaches have been proposed namely graph-based approach 4 , link-based approach 5 , agent and dynamic based approach 25,26 , fuzzy-based approach 20–22 and modularity scoring based approach 6–19,23,24 .”
BackgroundA survey on game theoretic models for community detection in social networks
Jonnalagadda, A., & Kuppusamy, L. (2016) · Social Network Analysis and Mining · doi:10.1007/s13278-016-0386-1 · Cited by 45
“The real-world networks exhibit significant irregularities in terms of degree of nodes and the distribution of edges, bringing out a high level of organization of the network (Girvan and Newman 2002; Palla et al. 2005; Fortunato 2010).”
BackgroundDifferent Approaches to Community Detection
Rosvall, M., Delvenne, J., Schaub, M. T., & Lambiotte, R. (2019) · Wiley eBooks · doi:10.1002/9781119483298.ch4 · Cited by 60
Zhang, Z., Pu, P., Han, D., & Tang, M. (2018) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2018.04.036 · Cited by 44
López‐Cortés, A., Paz‐y‐Miño, C., Cabrera‐Andrade, A., Barigye, S. J., Munteanu, C. R., González‐Díaz, H., Pazos, A., Pérez‐Castillo, Y., & Tejera, E. (2018) · Scientific Reports · doi:10.1038/s41598-018-35149-1 · Cited by 46
Improved Algorithms for Maximal Clique Search in Uncertain Networks
Li, R.-H., Dai, Q., Wang, G., Ming, Z., Qin, L., & Yu, J. X. (2019) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2019.00108 · Cited by 44
“Enumerating all maximal cliques from a network has numerous applications, including finding overlapping communities from social networks [11], detecting social hierarchy [12], and identifying protein complexes in protein-protein interaction (PPI) network [13].”
BackgroundA review on community structures detection in time evolving social networks
Alotaibi, N., & Rhouma, D. (2021) · Journal of King Saud University - Computer and Information Sciences · doi:10.1016/j.jksuci.2021.08.016 · Cited by 44
Niu, Y., Kong, D., Liu, L., Wen, R., & Xiao, J. (2022) · Expert Systems with Applications · doi:10.1016/j.eswa.2022.119213 · Cited by 44
Modeling with Node Degree Preservation Can Accurately Find Communities
Jin, D., Chen, Z., He, D., & Zhang, W. (2015) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v29i1.9201 · Cited by 44
“These methods can be grouped into that for finding disjoint communities (Girvan and Newman 2002; Blondel et al. 2008; Rosvall and Bergstrom 2008) and those for finding overlapping communities (Palla et al. 2005; Lancichinetti, Fortunato and Kertesz 2009; Ahn, Bagrow and Lehmann 2010).”
MethodParallel Overlapping Community Detection with SLPA
Kuzmin, K., Shah, S. Y., & Szymanski, B. K. (2013) · International Conference on Social Computing · doi:10.1109/socialcom.2013.37 · Cited by 44
“The clique percolation technique [2] finds communities in a fully connected network by finding adjacent cliques in the graph.”
BackgroundTopic discovery and future trend forecasting for texts
Hurtado, J., Agarwal, A., & Xingquan Zhu, A. (2016) · Journal Of Big Data · doi:10.1186/s40537-016-0039-2 · Cited by 44
“An example of the discovered topic community using CPM is show in Fig.”
MethodInfluentialModeling the effects of social impact on epidemic spreading in complex networks
Ni, S., Weng, W., & Zhang, H. (2011) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2011.07.042 · Cited by 43
Kininmonth, S., van Oppen, M. J. H., & Possingham, H. P. (2010) · Ecological Modelling · doi:10.1016/j.ecolmodel.2010.08.042 · Cited by 49
“If each coral reef can be given probabilities of potentially belongng to multiple genetic communities then there is the case for verlapping communities (Palla et al., 2005; Lancichinetti et al., 009).”
BackgroundLIMITED RESOLUTION AND MULTIRESOLUTION METHODS IN COMPLEX NETWORK COMMUNITY DETECTION
Kumpula, J. M., Saramäki, J., Kaski, K. K., & Kertész, J. (2007) · Fluctuation and Noise Letters · doi:10.1142/s0219477507003854 · Cited by 43
Kim, H. J., Chae, B. K., & Park, S. B. (2017) · URBAN DESIGN International · doi:10.1057/s41289-017-0050-z · Cited by 45
Parameters Variation-Based Synchronization on Derivative Coupled Lur’e Networks
Tang, Z., Park, J. H., Wang, Y., & Feng, J. (2018) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2018.2879985 · Cited by 43
“oscillatory, and chaos phenomena, which are crucial to the final behaviors of the whole complex networks [7]–[10].”
BackgroundAstl, L., & Verkhivker, G. M. (2019) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.9b00119 · Cited by 44
Multiscale Local Community Detection in Social Networks
Luo, W., Zhang, D., Li, N., & Lu, N. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2938173 · Cited by 51
“Ingenious methods such as random walk [18], label propagation [19], and other typical methods [20], [21], [22] have also been proposed to detect communities.”
MethodOverlapping community detection on complex networks with Graph Convolutional Networks
Yuan, S., Zeng, H., Zuo, Z., & Wang, C. (2022) · Computer Communications · doi:10.1016/j.comcom.2022.12.008 · Cited by 43
Defining and identifying cograph communities in complex networks
Jia, S., Gao, L., Gao, Y., Nastos, J., Wang, Y., Zhang, X., & Wang, H. (2015) · New Journal of Physics · doi:10.1088/1367-2630/17/1/013044 · Cited by 47
Random matrix analysis of localization properties of gene coexpression network
Jalan, S., Solymosi, N., Vattay, G., & Li, B. (2010) · Physical Review E · doi:10.1103/physreve.81.046118 · Cited by 46
Clique percolation in random graphs
Li, M., Deng, Y., & Wang, B.-H. (2015) · Physical Review E · doi:10.1103/physreve.92.042116 · Cited by 43
OpenEnsembles: A Python Resource for Ensemble Clustering
Ronan, T., Anastasio, S., Qi, Z., Tavares, P. H. S. V., Sloutsky, R., & Naegle, K. M. (2018) · Journal of Machine Learning Research · Cited by 42
Liu, K., Huang, J., Sun, H., Wan, M., Qi, Y., & He, L. (2015) · Knowledge-Based Systems · doi:10.1016/j.knosys.2015.08.015 · Cited by 42
Label propagation algorithm based on local cycles for community detection
Zhang, X., Fei, S., Song, C., Tian, X., & Ao, Y.-Y. (2014) · International Journal of Modern Physics B · doi:10.1142/s0217979215500290 · Cited by 42
Ji, J., Song, X., Liu, C., & Zhang, X. (2013) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2013.04.001 · Cited by 42
Identification of hub subnetwork based on topological features of genes in breast cancer
Zhuang, D., JIANG, L., He, Q., Zhou, P., & Yue, T. (2014) · International Journal of Molecular Medicine · doi:10.3892/ijmm.2014.2057 · Cited by 42
“This issue has been resolved to some extent using clustering methods which have previously been shown to be useful in identifying protein/gene interactions that take place within the same cellular process (33).”
Visualizing community detection in opportunistic networks
Yoneki, E., Hui, P., & Crowcroft, J. (2007) · ACM Workshop on Challenged Networks (CHANTS) · doi:10.1145/1287791.1287810 · Cited by 42
Jiang, Z., Dong, X., & Zhang, Z. (2016) · Scientific Reports · doi:10.1038/srep19149 · Cited by 46
Automatic Induction of Synsets from a Graph of Synonyms
Ustalov, D., Panchenko, A., & Biemann, C. (2017) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/p17-1145 · Cited by 51
“Clique Percolation Method (CPM) (Palla et al., 2005) is a fuzzy clustering algorithm for”
MethodInfluentialDiscovering Fuzzy Structural Patterns for Graph Analytics
He, T., & Chan, K. C. C. (2018) · IEEE Transactions on Fuzzy Systems · doi:10.1109/tfuzz.2018.2791951 · Cited by 42
“For example, in [8], an algorithm is proposed to detect graph clusters based on the clique percolation method.”
MethodHaas, S., & Fischer, M. (2018) · ACM Symposium on Applied Computing · doi:10.1145/3167132.3167239 · Cited by 42
“CPM is based on the clique size k 15 such that the smallest attack consists out of 15 similar alerts to filter false positive alerts.”
MethodEnsemble-based overlapping community detection using disjoint community structures
Chakraborty, T., Ghosh, S., & Park, N. (2018) · Knowledge-Based Systems · doi:10.1016/j.knosys.2018.08.033 · Cited by 42
Identifying ‘firebreaks’ to fragment dispersal networks of a marine parasite
Samsing, F., Johnsen, I. A., Treml, E. A., & Dempster, T. (2019) · International Journal for Parasitology · doi:10.1016/j.ijpara.2018.11.005 · Cited by 43
Gadiyaram, V., Vishveshwara, S., & Vishveshwara, S. (2019) · Journal of Chemical Information and Modeling · doi:10.1021/acs.jcim.9b00002 · Cited by 47
Effective number of accessed nodes in complex networks
Viana, M. P., Batista, J. L. B., & Costa, L. D. F. (2012) · Physical Review E · doi:10.1103/physreve.85.036105 · Cited by 53
“We also considered probabilities obtained from real-world networks, namely circuits [32], power grids [33], German highways [34], protein interactions [35], e-mails [36], and co-authorships in network science [37].”
Gao, L., Hu, Y., & Di, Z. (2008) · Physical Review E · doi:10.1103/physreve.78.046109 · Cited by 42
Prediction of protein–protein interactions between Ralstonia solanacearum and Arabidopsis thaliana
Li, Z., He, F., Zhang, Z., & Peng, Y. (2011) · Amino Acids · doi:10.1007/s00726-011-0978-z · Cited by 45
“Members of a cluster are usually involved in similar biological processes, and protein complexes can be identified through the clustering of a network (Palla et al. 2005; Jonsson et al. 2006).”
BackgroundWu, B., Ye, Q., Yang, S., & Wang, B. (2009) · doi:10.1145/1651274.1651277 · Cited by 41
“The last two columns in Table 1 represents the time costing of CPM and FLIBer.”
BackgroundMethodInfluentialVisual Event Summarization on Social Media using Topic Modelling and Graph-based Ranking Algorithms
Schinas, M., Papadopoulos, S., Kompatsiaris, I. Y., & Mitkas, P. A. (2015) · International Conference on Multimedia Retrieval · doi:10.1145/2671188.2749407 · Cited by 41
“To handle this high degree of visual redundancy we use the Clique Percolation Method, presented in [17], to find sets of messages that are visual duplicates.”
MethodSocievole, A., Rango, F. D., & Caputo, A. (2014) · IFIP Wireless Days · doi:10.1109/wd.2014.7020819 · Cited by 41
“• k-CLIQUE or Clique Percolation Method (CPM) [26] is an approach finding overlapping communities where a community is defined as the union of all k-cliques (complete subgraphs with k nodes) that can reach each other through a series of adjacent k-cliques, where two k-cliques are said to be adjacent is they share k−1…”
MethodOverlapping community detection using a community optimized graph swarm
Rees, B. S., & Gallagher, K. B. (2012) · Social Network Analysis and Mining · doi:10.1007/s13278-012-0050-3 · Cited by 41
“Palla et al. (2005) extended the theory of cliques as communities by introducing the definition that a community, specifically a k-clique community, is a union of all k cliques that can be reached via adjacent k cliques.”
BackgroundMethodInfluentialDetecting communities in networks by merging cliques
Yan, B., & Gregory, S. (2009) · IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS) · doi:10.1109/icicisys.2009.5358036 · Cited by 40
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.