Large cliques in a power-law random graph
2010 (English)In: Journal of Applied Probability, ISSN 0021-9002, E-ISSN 1475-6072, Vol. 47, no 4, 1124-1135 p.Article in journal (Refereed) Published
In this paper we study the size of the largest clique omega(G(n, alpha)) in a random graph G(n, alpha) on n vertices which has power-law degree distribution with exponent alpha. We show that, for 'flat' degree sequences with alpha > 2, with high probability, the largest clique in G(n, alpha) is of a constant size, while, for the heavy tail distribution, when 0 < alpha < 2, omega(G (n, alpha)) grows as a power of n. Moreover, we show that a natural simple algorithm with high probability finds in G(n, alpha) a large clique of size (1 - o(1))omega(G(n, alpha)) in polynomial time.
Place, publisher, year, edition, pages
2010. Vol. 47, no 4, 1124-1135 p.
Power-law random graph, clique, greedy algorithm
IdentifiersURN: urn:nbn:se:uu:diva-148611ISI: 000286958100018OAI: oai:DiVA.org:uu-148611DiVA: diva2:402476