Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs
- Title
- Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs
- Authors
- 오승혁
- Date Issued
- 2023
- Publisher
- 포항공과대학교
- 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 in $O(m + n^{4.5(1-\alpha)})$ expected time if the geometric representation of the hyperbolic random graph is given or in $O(m + n^{6(1-\alpha)})$ expected time if the geometric representation is not given. 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.
- URI
- http://postech.dcollection.net/common/orgView/200000690252
https://oasis.postech.ac.kr/handle/2014.oak/118454
- Article Type
- Thesis
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.