Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.16
URN: urn:nbn:de:0030-drops-63670
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6367/
Bläsius, Thomas ; Friedrich, Tobias ; Krohmer, Anton ; Laue, Sören
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane
| pdf-format: |
|
Abstract
Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of Omega(n^2). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.
BibTeX - Entry
@InProceedings{blsius_et_al:LIPIcs:2016:6367,
author = {Thomas Bl{\"a}sius and Tobias Friedrich and Anton Krohmer and S{\"o}ren Laue},
title = {{Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {16:1--16:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-015-6},
ISSN = {1868-8969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6367},
URN = {urn:nbn:de:0030-drops-63670},
doi = {10.4230/LIPIcs.ESA.2016.16},
annote = {Keywords: hyperbolic random graphs, embedding, power-law graphs, hyperbolic plane}
}
| Keywords: | hyperbolic random graphs, embedding, power-law graphs, hyperbolic plane | |
| Seminar: | 24th Annual European Symposium on Algorithms (ESA 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 18.08.2016 |
