The critical point of k-clique percolation in the Erdős-Rényi graph

DOI10.1007/S10955-006-9184-XzbMATH Open1118.82024arXivcond-mat/0610298OpenAlexW2096504267MaRDI QIDQ2641391FDOQ2641391

Authors: Gergely Palla, I. Derényi, T. Vicsek 

Publication date: 20 August 2007

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Abstract: Motivated by the success of a k-clique percolation method for the identification of overlapping communities in large real networks, here we study the k-clique percolation problem in the Erdos-Renyi graph. When the probability p of two nodes being connected is above a certain threshold p_c(k), the complete subgraphs of size k (the k-cliques) are organized into a giant cluster. By making some assumptions that are expected to be valid below the threshold, we determine the average size of the k-clique percolation clusters, using a generating function formalism. From the divergence of this average size we then derive an analytic expression for the critical linking probability p_c(k).

Full work available at URL: https://arxiv.org/abs/cond-mat/0610298

Recommendations

• Critical percolation on certain nonunimodular graphs
• scientific article; zbMATH DE number 4183464
• On the random graph structure near the critical point
• Critical percolation on the kagome hypergraph
• The sharp \(K_4\)-percolation threshold on the Erdős-Rényi random graph
• A note about critical percolation on finite graphs
• Critical percolation on random regular graphs
• Critical percolation on random regular graphs
• On the Behavior of a Random Graph Near a Critical Point
• Overlapping modularity at the critical point of \(k\)-clique percolation

zbMATH Keywords

networkrandom graphpercolationcommunity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Critical phenomena in equilibrium statistical mechanics (82B27) Percolation (82B43)

Cites Work

• Statistical mechanics of complex networks
• Emergence of Scaling in Random Networks
• Community structure in social and biological networks
• Title not available (Why is that?)
• Collective dynamics of `small-world' networks
• Paths in graphs
• Title not available (Why is that?)

Cited In (8)

• Clique percolation
• Thresholds for vanishing of `isolated' faces in random Čech and Vietoris-Rips complexes
• Catastrophic event phenomena in communication networks: a survey
• Random intersection graphs with communities
• InfoSearch: a social search engine
• Overlapping modularity at the critical point of \(k\)-clique percolation
• Triangle percolation in mean field random graphs-with PDE
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs

This page was built for publication: The critical point of \(k\)-clique percolation in the Erdős-Rényi graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2641391)