Large Cliques in a Power-Law Random Graph

By Svante Janson, Tomasz Łuczak, Ilkka Norros. Journal of Applied Probability, 2009

52 citations recorded by the source corpus.

In this paper we study the size of the largest clique ω(G(n, α)) in a random graph G(n, α) on n vertices which has power-law degree distribution with exponent α. We show that, for ‘flat’ degree sequences with α > 2, with high probability, the largest clique in G(n, α) is of a constant size, while, for the heavy tail distribution, when 0 < α < 2, ω(G(n, α)) grows as a power of n. Moreover, we show that a natural simple algorithm with high probability finds in G(n, α) a large clique of size (1 − o(1))ω(G(n, α)) in polynomial time.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/a8b59f7fc8a12e87df09b865911941f648a641f7