Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
An Optimal Algorithm for Tiling the Plane with a Translated Polyomino Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Generating Random Hyperbolic Graphs in Subquadratic Time

Authors : Moritz von Looz, Henning Meyerhenke, Roman Prutkin

Published in: Algorithms and Computation

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Complex networks have become increasingly popular for modeling various real-world phenomena. Realistic generative network models are important in this context as they simplify complex network research regarding data sharing, reproducibility, and scalability studies. Random hyperbolic graphs are a very promising family of geometric graphs with unit-disk neighborhood in the hyperbolic plane. Previous work provided empirical and theoretical evidence that this generative graph model creates networks with many realistic features.
In this work we provide the first generation algorithm for random hyperbolic graphs with subquadratic running time. We prove a time complexity of \(O((n^{3/2}+m) \log n)\) with high probability for the generation process. This running time is confirmed by experimental data with our implementation. The acceleration stems primarily from the reduction of pairwise distance computations through a polar quadtree, which we adapt to hyperbolic space for this purpose and which can be of independent interest. In practice we improve the running time of a previous implementation (which allows more general neighborhoods than the unit disk) by at least two orders of magnitude this way. Networks with billions of edges can now be generated in a few minutes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Approximation Algorithms in the Successive Hitting Set Model
next chapter Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing
Footnotes
1
We consider the name “hyperbolic unit-disk graphs” as more precise, but we use “random hyperbolic graphs” to be consistent with the literature. More general neighborhoods are possible [15] but not considered here since most theoretical works [7, 8, 12] are for unit-disk neighborhoods.
 
Literature
1.
Aiello, W., Chung, F., Lu, L.: A random graph model for massive graphs. In: Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 171–180. ACM (2000)
2.
3.
4.
Anderson, J.W.: Hyperbolic Geometry. Springer Undergraduate Mathematics Series, 2nd edn. Springer, Berlin (2005)MATH
5.
Bader, D.A., Berry, J., Kahan, S., Murphy, R., Riedy, E.J., Willcock, J.: Graph 500 benchmark 1 (“search”), version 1.1. Technical report, Graph 500 (2010)
6.
Batagelj, V., Brandes, U.: Efficient generation of large random networks. Phys. Rev. E 71(3), 036113 (2005)CrossRef
7.
Bode, M., Fountoulakis, N., Müller, T.: On the giant component of random hyperbolic graphs. In: The Seventh European Conference on Combinatorics, Graph Theory and Applications. CRM Series, vol. 16, pp. 425–429. Scuola Normale Superiore (2013)
8.
9.
Chakrabarti, D., Faloutsos, C.: Graph mining: laws, generators, and algorithms. ACM Comput. Surv. (CSUR) 38(1), 2 (2006)CrossRef
10.
Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: a recursive model for graph mining. In Proceedings of the 4th SIAM International Conference on Data Mining (SDM), Orlando, FL. SIAM, April 2004
11.
Dorogovtsev, S.N., Mendes, J.F.F.: Evolution of Networks: from Biological Nets to the Internet and WWW. Oxford University Press, Oxford (2003)CrossRefMATH
12.
Gugelmann, L., Panagiotou, K., Peter, U.: Random hyperbolic graphs: degree sequence and clustering. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 573–585. Springer, Heidelberg (2012) CrossRef
13.
Kiwi, M., Mitsche, D.: A bound for the diameter of random hyperbolic graphs. In: 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp. 26–39. SIAM, January 2015
14.
Kolda, T.G., Pinar, A., Todd, P., Seshadhri, C.: A scalable generative graph model with community structure. SIAM J. Sci. Comput. 36(5), C424–C452 (2014)MathSciNetCrossRefMATH
15.
Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., Boguñá, M.: Hyperbolic geometry of complex networks. Phys. Rev. E 82(3), 036106 (2010)MathSciNetCrossRef
16.
Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)CrossRef
17.
Miller, J.C., Hagberg, A.: Efficient generation of networks with given expected degrees. In: Frieze, A., Horn, P., Prałat, P. (eds.) WAW 2011. LNCS, vol. 6732, pp. 115–126. Springer, Heidelberg (2011) CrossRef
18.
19.
Samet, H.: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann Publishers Inc., San Francisco (2005) MATH
20.
Seshadhri, C., Kolda, T.G., Pinar, A.: Community structure and scale-free collections of Erdős-Rényi graphs. Phys. Rev. E 85(5), 056109 (2012)CrossRef
21.
Seshadhri, C., Pinar, A., Kolda, T.G.: The similarity between stochastic Kronecker and Chung-Lu graph models. In: Proceedings of the 2012 SIAM International Conference on Data Mining (SDM), pp. 1071–1082 (2012)
22.
Staudt, C.L., Sazonovs, A., Meyerhenke, H.: NetworKit: an interactive tool suite for high-performance network analysis (2014). arXiv preprint arXiv:​1403.​3005
23.
von Looz, M., Meyerhenke, H.: Querying probabilistic neighborhoods in spatial data sets efficiently, September 2015. ArXiv preprint arXiv:​1509.​01990
24.
von Looz, M., Meyerhenke, H., Prutkin, R.: Generating random hyperbolic graphs in subquadratic time, September 2015. ArXiv preprint arXiv:​1501.​03545
Metadata
Title
Generating Random Hyperbolic Graphs in Subquadratic Time
Authors
Moritz von Looz
Henning Meyerhenke
Roman Prutkin
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Algorithms and Computation

Print ISBN: 978-3-662-48970-3

Electronic ISBN: 978-3-662-48971-0

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-662-48971-0_40

Premium Partner

    Image Credits