Large Communities in a scale-free network

Abstract

We prove the existence of a large complete subgraph w.h.p. in a preferential attachment random graph process with an edge-step. That is, we prove that the random graph $G_t$ produced by the so-called GLP model at time $t$ contains a complete subgraph of order $t^{\alpha }$, where $\alpha =(1-\epsilon )\frac{1-p}{2-p}$, $\epsilon$ is any number such that $0<\epsilon <1$, and $0<p<1$ is a parameter of the model.

14 pages. Updated version

Cited by in corpus (1)

• Diameter of P.A. random graphs with edge-step functions