Agglomeration in scale-free random graphs

Abstract

In this work we investigate three random graph models capable of generating scale-free graphs. Our main interest relies on formation of cliques, calculating clustering coefficients, the degree distribution anddiameters. The main results we have proven show the existence asymptotically almost surely the existence of a clique whose order goes to infinity as the graphs order goes to infinity, concentration inequalities for the degrees and upper bound for the diameter in one of theses models. We also show that in the model known as Holme-Kims model the clustering coefficients local and global present quite distinct behavior.Whereas the former is bounded away from zero a.a.s, the latter goes to zero as the time goes to infinity.