Clique percolation

DOI10.1002/RSA.20270MaRDI QIDQ3055777zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Oliver Riordan

Publication date 9 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0804.0867

zbMATH Keywords

random graphbranching processcliquepercolation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: Derenyi, Palla and Vicsek introduced the following dependent percolation model, in the context of finding communities in networks. Starting with a random graph $G$ generated by some rule, form an auxiliary graph $G^{\prime }$ whose vertices are the $k$-cliques of $G$, in which two vertices are joined if the corresponding cliques share $k-1$ vertices. They considered in particular the case where $G=G(n,p)$, and found heuristically the threshold for a giant component to appear in $G^{\prime }$. Here we give a rigorous proof of this result, as well as many extensions. The model turns out to be very interesting due to the essential global dependence present in $G^{\prime }$.

Recommendations

• The critical point of \(k\)-clique percolation in the Erdős-Rényi graph
• Percolation in general graphs
• Percolation on dense graph sequences
• The Giant Component in a Random Subgraph of a Given Graph
• scientific article; zbMATH DE number 1444472

Cites work

• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• Bisecting sparse random graphs
• Component behavior near the critical point of the random graph process
• Largest random component of a k-cube
• Random subgraphs of finite graphs. II: The lace expansion and the triangle condition
• Random subgraphs of finite graphs. III: The phase transition for the n-cube
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Sharp thresholds of graph properties, and the k-sat problem
• The Evolution of Random Graphs
• The Evolution of Random Subgraphs of the Cube
• The critical point of \(k\)-clique percolation in the Erdős-Rényi graph
• The phase transition in inhomogeneous random graphs

Cited in

(14)

• Locomotive assignment graph model for freight traffic on linear Section of railway. The problem of finding a maximal independent schedule coverage
• Asymptotic normality of the size of the giant component in a random hypergraph
• Phase transition in random intersection graphs with communities
• Percolation on complex networks: theory and application
• A threshold for the maker-breaker clique game
• Thresholds for vanishing of `isolated' faces in random Čech and Vietoris-Rips complexes
• Square percolation and the threshold for quadratic divergence in random right‐angled Coxeter groups
• A threshold for relative hyperbolicity in random right-angled Coxeter groups
• Parameterized Clique on Scale-Free Networks
• Inside the critical window for cohomology of random \(k\)-complexes
• Random geometric complexes
• Overlapping modularity at the critical point of \(k\)-clique percolation
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• The average-case complexity of counting cliques in Erdős-Rényi hypergraphs

This page was built for publication: Clique percolation

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