Sequential algorithm for fast clique percolation
Physical Review EPublished 15 August 2008Open access
Jussi M. Kumpula, Mikko Kivelä, Kimmo Kaski, Jari Saramäki
Citations225
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A sequential clique percolation algorithm (SCP) is presented to do fast community detection in weighted and unweighted networks, for cliques of a chosen size and can simultaneously produce a dendrogram representation of hierarchical community structure.
Abstract
In complex network research clique percolation, introduced by Palla, Derényi, and Vicsek [Nature (London) 435, 814 (2005)], is a deterministic community detection method which allows for overlapping communities and is purely based on local topological properties of a network. Here we present a sequential clique percolation algorithm (SCP) to do fast community detection in weighted and unweighted networks, for cliques of a chosen size. This method is based on sequentially inserting the constituent links to the network and simultaneously keeping track of the emerging community structure. Unlike existing algorithms, the SCP method allows for detecting k -clique communities at multiple weight thresholds in a single run, and can simultaneously produce a dendrogram representation of hierarchical community structure. In sparse weighted networks, the SCP algorithm can also be used for implementing the weighted clique percolation method recently introduced by Farkas [New J. Phys. 9, 180 (2007)]. The computational time of the SCP algorithm scales linearly with the number of k -cliques in the network. As an example, the method is applied to a product association network, revealing its nested community structure.
Keywords
PsychologyPhysics and Astronomy
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
Proceedings of the National Academy of SciencesCommunity structure in social and biological networks
15,656 Citations2002Michelle Girvan, M. E. J. Newman
This article proposes a method for detecting communities, built around the idea of using centrality indices to find community boundaries, and tests it on computer-generated and real-world graphs whose community structure is already known and finds that the method detects this known structure with high sensitivity and reliability.
Physical Review EFinding and evaluating community structure in networks
13,892 Citations2004Michelle G. Newman, Michelle Girvan
It is demonstrated that the algorithms proposed are highly effective at discovering community structure in both computer-generated and real-world network data, and can be used to shed light on the sometimes dauntingly complex structure of networked systems.
NatureUncovering the overlapping community structure of complex networks in nature and society
5,435 Citations2005Gergely Palla, Imre Derényi +2 more
After defining a set of new characteristic quantities for the statistics of communities, this work applies an efficient technique for exploring overlapping communities on a large scale and finds that overlaps are significant, and the distributions introduced reveal universal features of networks.
NatureFunctional cartography of complex metabolic networks
4,013 Citations2005Roger Guimerà, Luı́s A. Nunes Amaral
A methodology is proposed that can find functional modules in complex networks, and classify nodes into universal roles according to their pattern of intra- and inter-module connections, which yields a ‘cartographic representation’ of complex networks.
Proceedings of the National Academy of SciencesDefining and identifying communities in networks
2,453 Citations2004Filippo Radicchi, Claudio Castellano +3 more
This article proposes a local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability and applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods.
Princeton University Press eBooksThe Structure and Dynamics of Networks
2,292 Citations2011Mark Newman, Albert-Ĺaszló Barabási +1 more
NatureHierarchical structure and the prediction of missing links in networks
2,198 Citations2008Aaron Clauset, Cristopher Moore +1 more
This work presents a general technique for inferring hierarchical structure from network data and shows that the existence of hierarchy can simultaneously explain and quantitatively reproduce many commonly observed topological properties of networks.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsScientific collaboration networks. I. Network construction and fundamental results
2,057 Citations2001M. E. J. Newman
Using computer databases of scientific papers in physics, biomedical research, and computer science, a network of collaboration between scientists in each of these disciplines is constructed, and a number of measures of centrality and connectedness in the same networks are studied.
The European Physical Journal BDetecting community structure in networks
2,022 Citations2004M. E. J. Newman
A number of more recent algorithms that appear to work well with real-world network data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage differences in resistor networks are described.
Proceedings of the National Academy of SciencesStructure and tie strengths in mobile communication networks
1,958 Citations2007Jukka‐Pekka Onnela, Jari Saramäki +6 more
It is found that, when it comes to information diffusion, weak and strong ties are both simultaneously ineffective, and this coupling significantly slows the diffusion process, resulting in dynamic trapping of information in communities.
NatureQuantifying social group evolution
1,657 Citations2007Gergely Palla, Albert-Ĺaszló Barabási +1 more
The focus is on networks capturing the collaboration between scientists and the calls between mobile phone users, and it is found that large groups persist for longer if they are capable of dynamically altering their membership, suggesting that an ability to change the group composition results in better adaptability.
Physical Review EIntensity and coherence of motifs in weighted complex networks
1,115 Citations2005Jukka-Pekka Onnela, Jari Saramäki +2 more
This paper applies motif scores and clustering coefficient to financial and metabolic networks and finds that inclusion of weights may considerably modify the conclusions obtained from the study of unweighted characteristics.
BioinformaticsCFinder: locating cliques and overlapping modules in biological networks
941 Citations2006Balázs Adamcsek, Gergely Palla +3 more
It is shown that in gene (protein) association networks CFinder can be used to predict the function(s) of a single protein and to discover novel modules, and CFinder is also very efficient for locating the cliques of large sparse graphs.
Proceedings of the National Academy of SciencesAn information-theoretic framework for resolving community structure in complex networks
822 Citations2007Martin Rosvall, Carl T. Bergstrom
An information-theoretic foundation for the concept of modularity in networks is developed and the modules of which the network is composed are identified by finding an optimal compression of its topology, capitalizing on regularities in its structure.
Scale-Free Networks
753 Citations2007Guido Caldarelli
Proceedings of the Royal Society B Biological SciencesIdentifying the role that animals play in their social networks
723 Citations2004David Lusseau, M. E. J. Newman
The network is found to be similar to human social networks in some respects but different in some others, such as the level of assortative mixing by degree within the population, which elucidates some of the means by which the network forms and evolves.
Physical Review LettersClique Percolation in Random Networks
554 Citations2005Imre Derényi, Gergely Palla +1 more
Why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks is discussed.
Proceedings of the National Academy of SciencesExtracting the hierarchical organization of complex systems
552 Citations2007Marta Sales‐Pardo, Roger Guimerà +2 more
An unsupervised method for extracting the hierarchical organization of complex biological, social, and technological networks is introduced and validated and an ensemble of hierarchically nested random graphs is defined, which is used to validate the method.
BioinformaticsSubnetwork hierarchies of biochemical pathways
366 Citations2003Petter Holme, Mikael Huss +1 more
A method to decompose biochemical networks into subnetworks based on the global geometry of the network is presented and is applied to 43 organisms from the WIT database.
Physical Review LettersEmergence of Communities in Weighted Networks
222 Citations2007Jussi M. Kumpula, Jukka‐Pekka Onnela +3 more
A simple network model where the weights are generated dynamically and they shape the developing topology by tuning a model parameter governing the importance of weights, which undergo a gradual structural transition from a module-free topology to one with communities.
BMC BioinformaticsCluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastasis
180 Citations2006Páll Jónsson, Tamara Cavanna +2 more
The protein network generation and subsequent network analysis used here, were shown to be useful for highlighting key proteins involved in metastasis, and can be extended to other species, thereby suggesting possible pathways around proteins of interest.
The European Physical Journal BCommunity analysis in social networks
172 Citations2004A. Arenas, L. Danon +3 more
The analysis reveals the community structure and provides a useful visualising technique, and it is found that the networks’ community structure is topologically self-similar using the Horton-Strahler index.
Lecture notes in computer scienceStructural Inference of Hierarchies in Networks
142 Citations2008Aaron Clauset, Cristopher Moore +1 more
This work gives a precise definition of hierarchical structure, gives a generic model for generating arbitrary hierarchical structure in a random graph, and describes a statistically principled way to learn the set of hierarchical features that most plausibly explain a particular real-world network.