Cliques in Hyperbolic Random Graphs
Algorithmica, (2017)Abstract
Most complex real world networks display scale-free features. This characteristic motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by hyprg and has shown theoretically and empirically to fulfill all typical properties of real world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs \(G\) and present new results on the expected number of \(k\)-cliques \(E(K_k)\) and the size of the largest clique \(ømega(G)\). We observe that there is a phase transition at power-law exponent \(= 3\). More precisely, for \(beta in (2,3)\) we prove \(E(K_k)=n^k (3-\beta)/2 \Theta(k)^-k\) and \(ømega(G)=\Theta(n^(3-\beta)/2)\), while for \(\beta\geq3\) we prove \(E(K_k)=n \Theta(k)^-k\) and \(ømega(G)=\Theta(łog(n)/ n)\). Furthermore, we show that for \(3\), cliques in hyperbolic random graphs can be computed in time \(O(n)\). If the underlying geometry is known, cliques can be found with worst-case runtime \(O(m n^2.5)\) for all values of \(\beta\).