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

DOI10.1007/S10955-006-9184-XMaRDI QIDQ2641391zbMATH OpenOpenAlexFDO

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

Publication date 20 August 2007

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

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

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)

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).

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

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1866312 (Why is no real title available?)
• Collective dynamics of `small-world' networks
• Community structure in social and biological networks
• Emergence of Scaling in Random Networks
• Paths in graphs
• Statistical mechanics of complex networks

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)