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 101–200 of 1,010
Querying k-truss community in large and dynamic graphs
Huang, X., Cheng, H., Qin, L., Tian, W., & Yu, J. X. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2610495 · Cited by 488
“There are two major cat-1321 egories: non-overlapping community detection [15, 17] and over-lapping community detection [16, 1, 25].”
BackgroundGlobal topological features of cancer proteins in the human interactome
Jonsson, P. F., & Bates, P. A. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl390 · Cited by 496
Complex discovery from weighted PPI networks
Liu, G., Wong, L., & Chua, H. N. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp311 · Cited by 470
Understanding brain networks and brain organization
Pessoa, L. (2014) · Physics of Life Reviews · doi:10.1016/j.plrev.2014.03.005 · Cited by 464
“Although prevalent, in general, this approach is inadequate given that in many complex systems, elements naturally belong to multiple communities [140,141].”
BackgroundTractable Models for Information Diffusion in Social Networks
Kimura, M., & Saito, K. (2006) · Lecture Notes in Computer Science · doi:10.1007/11871637_27 · Cited by 444
“Recently, considerable attention has been devoted to investigating social networks [9,5,4,7,11,6], since the progress of the Internet, the World Wide Web, and blogs has enabled us to collect real large-scale social networks.”
BackgroundCommunity detection in networks with positive and negative links
Traag, V. A., & Bruggeman, J. (2009) · Physical Review E · doi:10.1103/physreve.80.036115 · Cited by 434
“[6] Palla, G, I Derényi, I Farkas, and T Vicsek (2005) Uncovering the overlapping community structure of complex networks in nature and society.”
BackgroundPrediction of Information Diffusion Probabilities for Independent Cascade Model
Saito, K., Nakano, R., & Kimura, M. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-85567-5_9 · Cited by 436
“Recently, attention has been devoted to investigating complex networks such as social, computer and biochemical networks [3,18,15,13,16].”
BackgroundCommunity discovery using nonnegative matrix factorization
Wang, F., Li, T., Wang, X., Zhu, S., & Ding, C. (2011) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0181-y · Cited by 446
Structure and dynamics of core/periphery networks
Csermely, P., London, A., Wu, L.-Y., & Uzzi, B. (2013) · Journal of Complex Networks · doi:10.1093/comnet/cnt016 · Cited by 367
“However, many of these dense subgraphs that characterize local network topology were later used for the definition of network modules (or in other words: network communities) [28,29,42,45], and usually lacked the discrimination of the network periphery, i.”
BackgroundComparing Community Structure to Characteristics in Online Collegiate Social Networks
Red, V., Kelsic, E. D., Mucha, P. J., & Porter, M. A. (2011) · SIAM Review · doi:10.1137/080734315 · Cited by 331
“One of the presently dominant approaches in community detection involves the optimization of a quality function known as modularity, which counts the total edge weight of all intra-community connections compared to that which might be expected at random (under some null model) [27,71,73,74,76], though there are also n…”
BackgroundCausal thinking and complex system approaches in epidemiology
Galea, S., Riddle, M., & Kaplan, G. A. (2010) · International Journal of Epidemiology · doi:10.1093/ije/dyp296 · Cited by 426
Fuzzy communities and the concept of bridgeness in complex networks
Nepusz, T., Petróczi, A., Négyessy, L., & Bazsó, F. (2008) · Physical Review E · doi:10.1103/physreve.77.016107 · Cited by 421
Hierarchical Block Structures and High-Resolution Model Selection in Large Networks
Peixoto, T. P. (2014) · Physical Review X · doi:10.1103/physrevx.4.011047 · Cited by 248
“This type of approach should, in principle, also be applicable to other model classes, such as those based on overlapping [9, 83–85], or link communities [25, 86].”
BackgroundMethodControlling edge dynamics in complex networks
Nepusz, T., & Vicsek, T. (2012) · Nature Physics · doi:10.1038/nphys2327 · Cited by 430
Self-citationGraph theory and networks in Biology
Mason, O., & Verwoerd, M. (2007) · IET Systems Biology · doi:10.1049/iet-syb:20060038 · Cited by 398
“Using the observation that many communities are comprised of cliques (completely connected subgraphs), which are themselves densely interconnected, an approach to module identification that addresses this issue was presented in [179].”
BackgroundPercolation on complex networks: Theory and application
Li, M., Liu, R.-R., Lü, L., Hu, M.-B., Xu, S., & Zhang, Y.-C. (2021) · Physics Reports · doi:10.1016/j.physrep.2020.12.003 · Cited by 365
Modular networks and cumulative impact of lateral transfer in prokaryote genome evolution
Dagan, T., Artzy-Randrup, Y., & Martin, W. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0800679105 · Cited by 409
Overlapping community detection using Bayesian non-negative matrix factorization
Psorakis, I., Roberts, S., Ebden, M., & Sheldon, B. (2011) · Physical Review E · doi:10.1103/physreve.83.066114 · Cited by 399
Memory in network flows and its effects on spreading dynamics and community detection
Rosvall, M., Esquivel, A. V., Lancichinetti, A., West, J. D., & Lambiotte, R. (2014) · Nature Communications · doi:10.1038/ncomms5630 · Cited by 395
Community detection in social networks
Bedi, P., & Sharma, C. (2016) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1178 · Cited by 346
Zotenko, E., Mestre, J., O'Leary, D. P., & Przytycka, T. M. (2008) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000140 · Cited by 401
“We note that approaches similar to ours have been previously used by Palla et al [38] and Chesler et al. [39].”
MethodUniversality in network dynamics
Barzel, B., & Barabási, A.-L. (2013) · Nature Physics · doi:10.1038/nphys2741 · Cited by 396
Population connectivity: recent advances and new perspectives
Kool, J. T., Moilanen, A., & Treml, E. A. (2013) · Landscape Ecology · doi:10.1007/s10980-012-9819-z · Cited by 374
“Network community structure can be evaluated through various clustering methods (Clauset et al. 2004; Palla et al. 2005), characterizing associations between individuals or groups.”
BackgroundMethodEfficient and principled method for detecting communities in networks
Ball, B., Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.84.036103 · Cited by 386
“Early efforts at community detection, going back to the 1970s, assumed nonoverlapping or disjoint communities [1, 4, 5], but as many researchers have argued in the last few years, it is common in practical situations for communities to overlap [6].”
BackgroundCore-Periphery Structure in NetworksPreprint
Puck, M., Mason, R., Porter, A., Fowler, J. H., & Mucha, P. J. (2013) · Cited by 395
Discovering social circles in ego networks
Mcauley, J., & Leskovec, J. (2014) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2556612 · Cited by 366
Community Mining from Signed Social Networks
Yang, B., Cheung, W., & Liu, J. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.1061 · Cited by 383
“They can generally be divided into three main categories: 1) graph theoretic methods such as random walk methods and physics-based methods [10], [11], [12], the spectral methods [13], [14], [15], [16], and the Kernighan-Lin algorithm [17], 2) hierarchical methods such as agglomerative methods based…”
BackgroundMethodQuantitative function for community detection
Li, Z., Zhang, S., Wang, R.-S., Zhang, X.-S., & Chen, L. (2008) · Physical Review E · doi:10.1103/physreve.77.036109 · Cited by 382
Gallos, L. K., Makse, H. A., & Sigman, M. (2012) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1106612109 · Cited by 398
“[19] Palla G, Derenyi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society.”
BackgroundInfluentialExtending the definition of modularity to directed graphs with overlapping communities
Nicosia, V, Mangioni, G., Carchiolo, V, & Malgeri, M. (2009) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2009/03/p03024 · Cited by 346
“It is not so hard to accept the given definition of communities as a reasonable one: communities in real–life are groups of strongly connected nodes, as happens for example with people in a tennis club, authors in a co–authorship network or colleagues working in the same office [22] [18].”
BackgroundGlia Accumulate Evidence that Actions Are Futile and Suppress Unsuccessful Behavior
Mu, Y., Bennett, D. V., Rubinov, M., Narayan, S., Yang, C.-T., Tanimoto, M., Mensh, B. D., Looger, L. L., & Ahrens, M. B. (2019) · Cell · doi:10.1016/j.cell.2019.05.050 · Cited by 374
“…the correlation coefficient between all components, thresholding the correlation matrix, and clustering the thresholded correlation matrix using the clique percolation method (Palla et al., 2005), an algorithm that can flexibly assign each component to more than one cluster or to no clusters.”
A tutorial in connectome analysis: Topological and spatial features of brain networks
Kaiser, M. (2011) · NeuroImage · doi:10.1016/j.neuroimage.2011.05.025 · Cited by 371
Distributed community detection in delay tolerant networks
Hui, P., Yoneki, E., Chan, S. Y., & Crowcroft, J. (2007) · Proceedings of 2nd ACM/IEEE international workshop on Mobility in the evolving internet architecture · doi:10.1145/1366919.1366929 · Cited by 370
“Besides the methods mentioned in the two reviews papers, we also introduce the k -CLIQUE community detection method by Palla et al. [23] and the weighted community analysis methods by Newman [13], which are used to compare with our distributed algorithms in this paper.”
MethodA classification for community discovery methods in complex networks
Coscia, M., Giannotti, F., & Pedreschi, D. (2011) · Statistical Analysis and Data Mining: The ASA Data Science Journal · doi:10.1002/sam.10133 · Cited by 353
“Communities may correspond to groups of pages of the World Wide Web dealing with related topics [1], to functional modules such as cycles and pathways in metabolic networks [2, 3], to groups of related individuals in social networks [4] and so on.”
BackgroundMethodInfluentialCombining link and content for community detection: a discriminative approach
Yang, T., Jin, R., Chi, Y., & Zhu, S. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557120 · Cited by 364
A Directed Protein Interaction Network for Investigating Intracellular Signal Transduction
Vinayagam, A., Stelzl, U., Foulle, R., Plassmann, S., Zenkner, M., Timm, J., Assmus, H. E., Andrade-Navarro, M. A., & Wanker, E. E. (2011) · Science Signaling · doi:10.1126/scisignal.2001699 · Cited by 352
“the program Cfinder, which uses the clique percolation method (62).”
MethodCamacho, D., Panizo-LLedot, Á., Bello-Orgaz, G., Gonzalez-Pardo, A., & Cambria, E. (2020) · Information Fusion · doi:10.1016/j.inffus.2020.05.009 · Cited by 329
Community Detection and Mining in Social Media
Tang, L., & Liu, H. (2010) · Synthesis lectures on data mining and knowledge discovery · doi:10.2200/s00298ed1v01y201009dmk003 · Cited by 352
“The clique percolation method (CPM) is such a scheme to find overlapping communities in networks (Palla et al., 2005).”
BackgroundMethodHow to calculate the fractal dimension of a complex network: the box covering algorithm
Song, C., Gallos, L. K., Havlin, S., & Makse, H. A. (2007) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2007/03/p03006 · Cited by 345
A survey of community search over big graphs
Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., & Lin, X. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00556-x · Cited by 339
Computational approaches for detecting protein complexes from protein interaction networks: a survey
Li, X., Wu, M., Kwoh, C.-K., & Ng, S.-K. (2010) · BMC Genomics · doi:10.1186/1471-2164-11-s1-s3 · Cited by 349
“CFinder detects the k-clique percolation clusters as functional modules using a Clique Percolation Method [44].”
MethodExtending the definition of modularity of directed graphs with overlapping communitiesPreprint
Nicosia, V., Mangioni, G., Carchiolo, V., & Malgeri, M. (2009) · Cited by 348
Interchange of entire communities: microbial community coalescence
Rillig, M. C., Antonovics, J., Caruso, T., Lehmann, A., Powell, J. R., Veresoglou, S. D., & Verbruggen, E. (2015) · Trends in Ecology & Evolution · doi:10.1016/j.tree.2015.06.004 · Cited by 328
Kovács, I. A., Palotai, R., Szalay, M. S., & Csermely, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012528 · Cited by 338
The Why, How, and When of Representations for Complex Systems
Torres, L., Blevins, A. S., Bassett, D., & Eliassi-Rad, T. (2021) · SIAM Review · doi:10.1137/20m1355896 · Cited by 297
Metrics for Community Analysis: A Survey
Chakraborty, T., Dalmia, A., Mukherjee, A., & Ganguly, N. (2018) · ACM Computing Surveys · doi:10.1145/3091106 · Cited by 296
“Although initial attempt for overlapping community detection was done by [Palla et al. 2005], [Zhang et al. 2007] introduced the original notion of overlapping community structure.”
BackgroundResultStructural Folds: Generative Disruption in Overlapping Groups
Vedres, B., & Stark, D. (2010) · American Journal of Sociology · doi:10.1086/649497 · Cited by 320
“We use the clique percolation method (CPM) developed by physicists to uncover the overlapping community structure of complex networks (Palla et al. 2005), a method recently demonstrated as a suitable tool to analyze the evolution of cohesive groups (Palla, Barabási, and Vicsek 2007).”
BackgroundMethodCooperation in the noisy case: Prisoner’s dilemma game on two types of regular random graphs
Vukov, J., Szabó, G., & Szolnoki, A. (2006) · Physical Review E · doi:10.1103/physreve.73.067103 · Cited by 338
Evolutionary Network Analysis: A Survey
Aggarwal, C., & Subbian, K. (2014) · ACM Computing Surveys · doi:10.1145/2601412 · Cited by 313
“The work in Papadimitriou et al. [2010] proposes five similarity schemes for measuring the similarities between the different graph snapshots.”
BackgroundSmall-World Propensity and Weighted Brain Networks
Muldoon, S. F., Bridgeford, E. W., & Bassett, D. S. (2016) · Scientific Reports · doi:10.1038/srep22057 · Cited by 304
Local search of communities in large graphs
Cui, W., Xiao, Y., Wang, H., & Wang, W. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2612179 · Cited by 299
“The real social networks usually have overlapping communities [19], i.”
BackgroundFundamental structures of dynamic social networks
Sekara, V., Stopczynski, A., & Lehmann, S. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1602803113 · Cited by 313
“Human social communities are inherently overlapping (5, 6, 8, 17), with each and every individual participating in multiple communities.”
BackgroundAn Algorithm to Find Overlapping Community Structure in Networks
Gregory, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74976-9_12 · Cited by 302
“The first phase of their algorithm finds densely connected “community cores”, similarly to the method of [15].”
BackgroundMethodDetecting highly overlapping community structure by greedy clique expansion
Lee, C., Reid, F., McDaid, A. F., & Hurley, N. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1002.1827 · Cited by 271
“Similarly, in complex networks of interactions between proteins, it has been claimed that many proteins belong to multiple communities, each of which in turn corresponds to some biological function [8, 9].”
BackgroundMethodInfluentialSystems biology and the future of medicine
Loscalzo, J., & Barabasi, A. (2011) · WIREs Systems Biology and Medicine · doi:10.1002/wsbm.144 · Cited by 287
Community-Affiliation Graph Model for Overlapping Network Community Detection
Yang, J., & Leskovec, J. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.139 · Cited by 293
“To deal with this community detection algorithms based on identifying overlapping cliques [23], articulation points, as well as hierarchical clustering of”
BackgroundMethodResultInfluentialThe Brain as a Complex System: Using Network Science as a Tool for Understanding the Brain
Telesford, Q. K., Simpson, S. L., Burdette, J. H., Hayasaka, S., & Laurienti, P. J. (2011) · Brain Connectivity · doi:10.1089/brain.2011.0055 · Cited by 285
“The most popular method for finding overlapping communities was developed by (Palla et al., 2005), which uses a popular technique called the Clique Percolation Method.”
Börner, K., Sanyal, S., & Vespignani, A. (2007) · Annual Review of Information Science and Technology · doi:10.1002/aris.2007.1440410119 · Cited by 279
Kaiser, T., Herzog, P., Voderholzer, U., & Brakemeier, E. (2021) · Depression and Anxiety · doi:10.1002/da.23136 · Cited by 296
“We used the Clique Percolation Method for weighted networks (CPMw; Farkas et al., 2007; Palla et al., 2005) to identify communities of depressive and anxiety symptoms based on the estimated models.”
MethodTowards real-time community detection in large networks
Leung, I. X. Y., Hui, P., Liò, P., & Crowcroft, J. (2009) · Physical Review E · doi:10.1103/physreve.79.066107 · Cited by 289
“Another important question which was also briefly addressed in [19] is the problem of overlapping communities [17], i.”
BackgroundDynamics-Driven Allostery in Protein Kinases
Kornev, A. P., & Taylor, S. S. (2015) · Trends in Biochemical Sciences · doi:10.1016/j.tibs.2015.09.002 · Cited by 284
“They performed community analysis of these data based on the Clique Percolation Method [93] and detected a varying number (from 8 to 30) of semi-rigid bodies that consisted of four to eight residues.”
MethodTowards Linear Time Overlapping Community Detection in Social Networks
Xie, J., & Szymanski, B. K. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-30220-6_3 · Cited by 280
Xu, J., Li, C.-X., Li, Y.-S., Lv, J.-Y., Ma, Y., Shao, T.-T., Xu, L.-D., Wang, Y.-Y., Du, L., Zhang, Y.-P., et al. (2011) · Nucleic Acids Research · doi:10.1093/nar/gkq832 · Cited by 279
“Cliques are all of complete subgraphs that are not parts of larger complete subgraphs (39).”
BackgroundMethodDefining and Evaluating Network Communities Based on Ground-Truth
Yang, J., & Leskovec, J. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.138 · Cited by 254
Triadic closure as a basic generating mechanism of communities in complex networks
Bianconi, G., Darst, R. K., Iacovacci, J., & Fortunato, S. (2014) · Physical Review E · doi:10.1103/physreve.90.042806 · Cited by 268
Characterizing the Community Structure of Complex Networks
Lancichinetti, A., Kivelä, M., Saramäki, J., & Fortunato, S. (2010) · PLoS ONE · doi:10.1371/journal.pone.0011976 · Cited by 267
Dense Subgraph Extraction with Application to Community Detection
Chen, J., & Saad, Y. (2012) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.271 · Cited by 268
“In addition to partitioning-based and density-based approaches, also seen are techniques that build hierarchical structures [10], [11], [12], [13], that exploit stochastic block models [14], [15], [16], and that extract chains of adjacent cliques [17], [18].”
BackgroundAnalysis of community structure in networks of correlated data
Gómez, S., Jensen, P., & Arenas, A. (2009) · Physical Review E · doi:10.1103/physreve.80.016114 · Cited by 260
Patania, A., Petri, G., & Vaccarino, F. (2017) · EPJ Data Science · doi:10.1140/epjds/s13688-017-0114-8 · Cited by 252
Fast unfolding of community hierarchies in large networks
Blondel, V. D., Guillaume, J., Lambiotte, R., & Lefebvre, E. (2008) · Cited by 274
Hierarchy Measure for Complex Networks
Mones, E., Vicsek, L., & Vicsek, T. (2012) · PLoS ONE · doi:10.1371/journal.pone.0033799 · Cited by 259
“Secondly, uncovering a nested hierarchy is analogous to community detection, for which there are known methods [13,14].”
Self-citationClustering attributed graphs: Models, measures and methods
BOTHOREL, C., CRUZ, J. D., MAGNANI, M., & MICENKOVÁ, B. (2015) · Network Science · doi:10.1017/nws.2015.9 · Cited by 249
Co-citation and cluster analyses of extant literature on social networks
Shiau, W.-L., Dwivedi, Y. K., & Yang, H. S. (2017) · International Journal of Information Management · doi:10.1016/j.ijinfomgt.2017.04.007 · Cited by 250
“Palla et al. (2005) defined an innovative set of characteristic quantities to uncover the overlapping community structure of complex networks in nature and society and adopted effective techniques to explore large-scale overlapping communities.”
BackgroundFarkas, I., Ábel, D., Palla, G., & Vicsek, T. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/180 · Cited by 251
Self-citationA socio-aware overlay for publish/subscribe communication in delay tolerant networks
Yoneki, E., Hui, P., Chan, S., & Crowcroft, J. (2007) · Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems · doi:10.1145/1298126.1298166 · Cited by 255
“k-CLIQUE is based on[31] in which ak-clique community is defined as a union of all k-cliques (complete sub-graphs of sizek) that can be reached from each other through a series of adjacentk-cliques, where twok-cliques are said to be adjacent if they sharek − 1 nodes.”
BackgroundApplications, Architectures, and Protocol Design Issues for Mobile Social Networks: A Survey
Kayastha, N., Niyato, D., Wang, P., & Hossain, E. (2011) · Proceedings of the IEEE · doi:10.1109/jproc.2011.2169033 · Cited by 253
Overlapping Community Detection Using Neighborhood-Inflated Seed Expansion
Whang, J. J., Gleich, D. F., & Dhillon, I. S. (2016) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2518687 · Cited by 250
Community detection in networks: Structural communities versus ground truth
Hric, D., Darst, R. K., & Fortunato, S. (2014) · Physical Review E · doi:10.1103/physreve.90.062805 · Cited by 238
Popa, O., Hazkani-Covo, E., Landan, G., Martin, W., & Dagan, T. (2011) · Genome Research · doi:10.1101/gr.115592.110 · Cited by 240
“1; Palla et al. 2005, 2007; Leicht and Newman 2008; Foster et al. 2010).”
Multiresolution community detection for megascale networks by information-based replica correlations
Ronhovde, P., & Nussinov, Z. (2009) · Physical Review E · doi:10.1103/physreve.80.016109 · Cited by 245
Modifying the DPClus algorithm for identifying protein complexes based on new topological structures
Li, M., Chen, J.-E., Wang, J.-X., Hu, B., & Chen, G. (2008) · BMC Bioinformatics · doi:10.1186/1471-2105-9-398 · Cited by 246
“CFinder [22] is a tool of detecting overlapping clusters based on the Clique Percolation Method (CPM) [26].”
MethodWhy We Twitter: An Analysis of a Microblogging Community
Java, A., Song, X., Finin, T., & Tseng, B. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-00528-2_7 · Cited by 233
“Prompted by this intuition, we applied the Clique Percolation Method (CPM) [33,34] to find overlapping communities in networks.”
MethodCommunity detection in large-scale social networks
Du, N., Wu, B., Pei, X., Wang, B., & Xu, L. (2007) · Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis · doi:10.1145/1348549.1348552 · Cited by 231
“However, as mentioned in [16], most actual networks are made of highly overlapping cohesive subgroups of nodes simply because individuals often belong to numerous different kinds of relationships simultaneously.”
BackgroundCycles and clustering in bipartite networks
Lind, P. G., González, M. C., & Herrmann, H. J. (2005) · Physical Review E · doi:10.1103/physreve.72.056127 · Cited by 237
Detecting complex network modularity by dynamical clustering
Boccaletti, S., Ivanchenko, M., Latora, V., Pluchino, A., & Rapisarda, A. (2007) · Physical Review E · doi:10.1103/physreve.75.045102 · Cited by 232
Sequential algorithm for fast clique percolation
Kumpula, J. M., Kivelä, M., Kaski, K., & Saramäki, J. (2008) · Physical Review E · doi:10.1103/physreve.78.026109 · Cited by 230
SPICi: a fast clustering algorithm for large biological networks
Jiang, P., & Singh, M. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq078 · Cited by 237
Community detection in large‐scale networks: a survey and empirical evaluation
Harenberg, S., Bello, G., Gjeltema, L., Ranshous, S., Harlalka, J., Seay, R., Padmanabhan, K., & Samatova, N. (2014) · WIREs Computational Statistics · doi:10.1002/wics.1319 · Cited by 227
Approximate closest community search in networks
Huang, X., Lakshmanan, L. V. S., Yu, J. X., & Cheng, H. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2856318.2856323 · Cited by 220
“Generally, community detection falls into two major categories: non-overlapping [20, 22, 34] and overlapping community detection [21, 1, 31, 33].”
BackgroundStatistical physics approaches to the complex Earth system
Fan, J., Meng, J., Ludescher, J., Chen, X., Ashkenazy, Y., Kurths, J., Havlin, S., & Schellnhuber, H. J. (2021) · Physics Reports · doi:10.1016/j.physrep.2020.09.005 · Cited by 172
“A single node of the network may belong to more than one community, and most of the actual networks are made of highly overlapping communities of nodes [84].”
The effect of size heterogeneity on community identification in complex networks
Danon, L., Díaz-Guilera, A., & Arenas, A. (2006) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2006/11/p11010 · Cited by 234
Liu, C., Liu, J., & Jiang, Z. (2014) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2014.2305974 · Cited by 230
“[23] introduced the concept of clique percolation to the prob-”
BackgroundComputational network biology: Data, models, and applications
Liu, C., Ma, Y., Zhao, J., Nussinov, R., Zhang, Y.-C., Cheng, F., & Zhang, Z.-K. (2020) · Physics Reports · doi:10.1016/j.physrep.2019.12.004 · Cited by 227
Disrupted modular brain dynamics reflect cognitive dysfunction in Alzheimer's disease
de Haan, W., van der Flier, W. M., Koene, T., Smits, L. L., Scheltens, P., & Stam, C. J. (2012) · NeuroImage · doi:10.1016/j.neuroimage.2011.11.055 · Cited by 222
“Finally, the use of other modularity metrics might also result in different or additional findings, like hierarchical modularity or overlapping modules (Alexander-Bloch et al., 2010; Lancichinetti and Fortunato, 2009; Palla et al., 2005).”
Fortunato, S., & Castellano, C. (2012) · Computational Complexity · doi:10.1007/978-1-4614-1800-9_33 · Cited by 215
Network analysis of protein dynamics
Böde, C., Kovács, I. A., Szalay, M. S., Palotai, R., Korcsmáros, T., & Csermely, P. (2007) · FEBS Letters · doi:10.1016/j.febslet.2007.05.021 · Cited by 223
“A more refined analysis of the hierarchical and overlapping structure [5,6] of protein structure network modules still holds a lot of surprises in the identification of key protein”
BackgroundOnline search of overlapping communities
Cui, W., Xiao, Y., Wang, H., Lu, Y., & Wang, W. (2013) · Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2463676.2463722 · Cited by 222
Robust network community detection using balanced propagation
Šubelj, L., & Bajec, M. (2011) · The European Physical Journal B · doi:10.1140/epjb/e2011-10979-2 · Cited by 202
Behavioral dynamics of tax evasion – A survey
Pickhardt, M., & Prinz, A. (2014) · Journal of Economic Psychology · doi:10.1016/j.joep.2013.08.006 · Cited by 167
POLYPHONET: An advanced social network extraction system from the Web
Matsuo, Y., Mori, J., Hamasaki, M., Nishimura, T., Takeda, H., Hasida, K., & Ishizuka, M. (2007) · Journal of Web Semantics · doi:10.1016/j.websem.2007.09.002 · Cited by 223
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.