A sequential algorithm for fast clique percolation

Abstract

In complex network research clique percolation, introduced by Palla et al., 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 et al. 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.

Accepted to Phys. Rev. E, 8 pages, 4 figures

References in corpus (18)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Functional cartography of complex metabolic networks
• Defining and identifying communities in networks
• Hierarchical structure and the prediction of missing links in networks
• Structure and tie strengths in mobile communication networks
• Quantifying social group evolution
• Intensity and coherence of motifs in weighted complex networks
• CFinder: Locating cliques and overlapping modules in biological networks
• An information-theoretic framework for resolving community structure in complex networks
• Clique percolation in random networks
• Extracting the hierarchical organization of complex systems
• Subnetwork hierarchies of biochemical pathways
• Weighted network modules
• Emergence of communities in weighted networks
• Community analysis in social networks
• Structural Inference of Hierarchies in Networks

Cited by in corpus (23)

• Community detection in graphs
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Detecting highly overlapping community structure by greedy clique expansion
• Multiresolution community detection for megascale networks by information-based replica correlations
• Local resolution-limit-free Potts model for community detection
• Clique Graphs and Overlapping Communities
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Communities and beyond: mesoscopic analysis of a large social network with complementary methods
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Finding overlapping communities in multiplex networks
• Global disorder transition in the community structure of large-q Potts systems
• Clique percolation method: memory efficient almost exact communities
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• Comparison and Benchmark of Graph Clustering Algorithms
• Bayesian Overlapping Community Detection in Dynamic Networks
• The Atlas for the Aspiring Network Scientist
• Clubmark: a Parallel Isolation Framework for Benchmarking and Profiling Clustering Algorithms on NUMA Architectures
• Using Model-based Overlapping Seed Expansion to detect highly overlapping community structure
• ScienceWISE: Topic Modeling over Scientific Literature Networks
• CIIA:A New Algorithm for Community Detection
• Detección de comunidades en redes: Algoritmos y aplicaciones