  In this paper, we study the maximum clique problem on hyperbolic random
graphs. A hyperbolic random graph is a mathematical model for analyzing
scale-free networks since it effectively explains the power-law degree
distribution of scale-free networks. We propose a simple algorithm for finding
a maximum clique in hyperbolic random graph. We first analyze the running time
of our algorithm theoretically. We can compute a maximum clique on a hyperbolic
random graph $G$ in $O(m + n^{4.5(1-\alpha)})$ expected time if a geometric
representation is given or in $O(m + n^{6(1-\alpha)})$ expected time if a
geometric representation is not given, where $n$ and $m$ denote the numbers of
vertices and edges of $G$, respectively, and $\alpha$ denotes a parameter
controlling the power-law exponent of the degree distribution of $G$. Also, we
implemented and evaluated our algorithm empirically. Our algorithm outperforms
the previous algorithm [BFK18] practically and theoretically. Beyond the
hyperbolic random graphs, we have experiment on real-world networks. For most
of instances, we get large cliques close to the optimum solutions efficiently.
