Clique percolation in random networks

Abstract

The notion of k-clique percolation in random graphs is introduced, where k is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erdos-Renyi graph of N vertices we obtain that the percolation transition of k-cliques takes place when the probability of two vertices being connected by an edge reaches the threshold pc(k)=[(k-1)N]^{-1/(k-1)}. At the transition point the scaling of the giant component with N is highly non-trivial and depends on k. We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks.

4 pages, 3 figures, to be published in Phys. Rev. Lett

References in corpus (11)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Fast algorithm for detecting community structure in networks
• Random graphs with arbitrary degree distributions and their applications
• Defining and identifying communities in networks
• Resilience of the Internet to random breakdowns
• Weighted evolving networks: coupling topology and weights dynamics
• Detecting fuzzy community structures in complex networks with a Potts model
• The topological relationship between the large-scale attributes and local interaction patterns of complex networks
• Distance, dissimilarity index, and network community structure

Cited by in corpus (103)

• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Evolutionary games on graphs
• Critical phenomena in complex networks
• Link communities reveal multiscale complexity in networks
• Quantifying social group evolution
• Networks beyond pairwise interactions: structure and dynamics
• CFinder: Locating cliques and overlapping modules in biological networks
• k-core organization of complex networks
• Robustness and resilience of complex networks
• Phase diagrams for Prisoner's Dilemma game on two-dimensional lattices
• Recent advances in percolation theory and its applications
• Percolation on complex networks: Theory and application
• Robustness of community structure in networks
• Cooperation in noisy case: prisoner's dilemma game on two types of regular random graphs
• Weighted network modules
• A sequential algorithm for fast clique percolation
• Emergence of communities in weighted networks
• A Model for Social Networks
• Evaluating Local Community Methods in Networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Percolation of localized attack on complex networks
• GED: the method for group evolution discovery in social networks
• Statistical physics approaches to the complex Earth system
• Core percolation on complex networks
• Networks of strong ties
• Community structure and ethnic preferences in school friendship networks
• When are networks truly modular?
• Articulation Points in Complex Networks
• k-Core percolation on multiplex networks
• Directed network modules
• Tensor Spectral Clustering for Partitioning Higher-order Network Structures
• Emergence of large cliques in random scale-free network
• Weighted Growing Simplicial Complexes
• The effect of the topology on the spatial ultimatum game
• Percolation transition in networks with degree-degree correlation
• Preferential attachment of communities: the same principle, but a higher level
• Exact bond percolation thresholds in two dimensions
• Topological Percolation on Hyperbolic Simplicial Complexes
• Modularity produces small-world networks with dynamical time-scale separation
• Number of cliques in random scale-free network ensembles
• Communities in Networks
• Does the brain behave like a (complex) network? I. Dynamics
• Multi-parameter models of innovation diffusion on complex networks
• Clique percolation in random graphs
• DEMON: a Local-First Discovery Method for Overlapping Communities
• From Quantum Chemistry to Networks in Biology: A Graph Spectral Approach to Protein Structure Analyses
• The critical point of k-clique percolation in the Erdos-Renyi graph
• Predicting Community Evolution in Social Networks
• Homological percolation transitions in growing simplicial complexes
• Spectral Detection of Simplicial Communities via Hodge Laplacians
• N-body decomposition of bipartite networks
• Asymptotic normality of the size of the giant component in a random hypergraph
• Spectral transitions in networks
• Renormalization flows in complex networks
• Empirical study on clique-degree distribution of networks
• Percolation on networks with weak and heterogeneous dependency
• Structure of n-clique networks embedded in a complex network
• Analysing degeneracies in networks spectra
• Identification of Overlapping Communities via Constrained Egonet Tensor Decomposition
• Clique percolation
• vGraph: A Generative Model for Joint Community Detection and Node Representation Learning
• Communication and correlation among communities
• Percolation in a distorted square lattice
• Parallelizing Maximal Clique Enumeration on GPUs
• Random intersection graphs with communities
• Simplicial cascades are orchestrated by the multidimensional geometry of neuronal complexes
• Centrality properties of directed module members in social networks
• Overlapping modularity at the critical point of k-clique percolation
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• Universality class of epidemic percolation transitions driven by random walks
• Multi-scale Dynamics in a Massive Online Social Network
• Percolation Perspective on Sites Not Visited by a Random Walk in Two Dimensions
• Community Detection Across Multiple Social Networks based on Overlapping Users
• Higher-order temporal network effects through triplet evolution
• Percolation in a simple cubic lattice with distortion
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• The architecture of innovation: Tracking face-to-face interactions with ubicomp technologies
• Phase transitions and noise sensitivity on the Poisson space via stopping sets and decision trees
• A sampling-guided unsupervised learning method to capture percolation in complex networks
• Triangle percolation in mean field random graphs -- with PDE
• Evolving complex networks with conserved clique distributions
• Community detection in hypergraphs through hyperedge percolation
• The Atlas for the Aspiring Network Scientist
• Estimating Network Parameters for Selecting Community Detection Algorithms
• Parallel clustering with CFinder
• Generic criticality of community structure in random graphs
• Thresholds for vanishing of `Isolated' faces in random Čech and Vietoris-Rips complexes
• Graph Pattern Mining and Learning through User-defined Relations (Extended Version)
• Improving community detection via community association strength scores
• Long-time tails in sheared fluids
• Small-world of communities: communication and correlation of the meta-network
• Understanding Information Flow in Cascades Using Network Motifs
• Around Average Behavior: 3-lambda Network Model
• Hybrid evolving clique-networks and their communicability
• Analysis of Social Group Dynamics
• Amino-acid network clique analysis of protein mutation correlation effects: a case study of lysozme
• Variational Embeddings for Community Detection and Node Representation
• Hierarchy of percolation patterns in a kinetic replication model
• Detecting overlapping community structure: Estonian network of payments
• Group Evolution Discovery in Social Networks
• Competing spreading dynamics in simplicial complex
• K-clique percolation in free association networks. The mechanism behind the $7\pm 2$ law ?