Large cliques in a power-law random graph
Authors:
- Svante Janson,
- Tomasz Łuczak,
- Ilkka Norros
Abstract
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. © 2010 Applied Probability Trust.
- Record ID
- UAM2ccf3f6ce9b446238bd928af303aeb9e
- Author
- Journal series
- Journal of Applied Probability, ISSN 0021-9002
- Issue year
- 2010
- Vol
- 47
- No
- 4
- Pages
- 1124-1135
- ASJC Classification
- ; ;
- DOI
- DOI:10.1239/jap/1294170524 Opening in a new tab
- URL
- https://www.cambridge.org/core/journals/journal-of-applied-probability/article/large-cliques-in-a-powerlaw-random-graph/F1CE6D1654D53B7CE7C4665D5BD04D4A#article Opening in a new tab
- Language
- (en) English
- Score (nominal)
- 0
- Score source
- journalList
- Publication indicators
- = 20; = 18; = 45; : 2010 = 0.934; : 2010 (2 years) = 0.768 - 2010 (5 years) =0.866
- Citation count
- 45
Share
- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM2ccf3f6ce9b446238bd928af303aeb9e/
- URN
urn:amu-prod:UAM2ccf3f6ce9b446238bd928af303aeb9e
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.