DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.85

Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs

Authors: Eunjin Oh and Seunghyeok Oh

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

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-α)}) expected time if a geometric representation is given or in O(m + n^{6(1-α)}) expected time if a geometric representation is not given, where n and m denote the numbers of vertices and edges of G, respectively, and α 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.

Cite as

Eunjin Oh and Seunghyeok Oh. Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 85:1-85:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.ESA.2023.85,
  author =	{Oh, Eunjin and Oh, Seunghyeok},
  title =	{{Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{85:1--85:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.85},
  URN =		{urn:nbn:de:0030-drops-187384},
  doi =		{10.4230/LIPIcs.ESA.2023.85},
  annote =	{Keywords: Maximum cliques, hyperbolic random graphs}
}

Search Results

Documents authored by Oh, Seunghyeok

Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message