2008/05/31 by Jussi M. Kumpula, Mikko Kivelä, Mikko Kivela +3 · 1 citation
Mathematics · Physics and Astronomy · Psychology · #Algorithm #Clique #Clique percolation method #Combinatorics #Community structure #Complex Network Analysis Techniques #Complex network #Computer science #Mathematics #Mental Health Research Topics #Opinion Dynamics and Social Influence #Percolation (cognitive psychology) #Representation (politics) #physics.soc-ph
paper · pdf · doi:10.1103/physreve.78.026109
Accepted to Phys. Rev. E, 8 pages, 4 figures
arxiv created 2008/07/30 · openalex publication_date 2008/08/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.