Large Communities in a Scale-free Network – 2017

by Rodrigo Ribeiro3 de August de 202011 de August de 2020

with C. Alves (U. Leipzig) and R. Sanchis (UFMG) – Journal of Statistical Physics

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-\varepsilon)(1-p)/(2-p)$ and $\varepsilon$ is any number such that $0<\varepsilon<1$ , and $0<p<1$ is a parameter of the model.