Document Open Access Logo

Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane

Authors Thomas Bläsius, Tobias Friedrich, Anton Krohmer, Sören Laue

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.16.pdf
  • Filesize: 3.25 MB
  • 18 pages

Document Identifiers

Author Details

Thomas Bläsius
Tobias Friedrich
Anton Krohmer
Sören Laue

Cite As Get BibTex

Thomas Bläsius, Tobias Friedrich, Anton Krohmer, and Sören Laue. Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.16

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.

Subject Classification

Keywords
  • hyperbolic random graphs
  • embedding
  • power-law graphs
  • hyperbolic plane

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. William Aiello, Fan Chung, and Linyuan Lu. A random graph model for massive graphs. In 32nd Symp. Theory of Computing (STOC), pages 171-180, 2000. Google Scholar
  2. William Aiello, Fan Chung, and Linyuan Lu. A random graph model for power law graphs. Experimental Mathematics, 10(1):53-66, 2001. Google Scholar
  3. Rodrigo Aldecoa, Chiara Orsini, and Dmitri Krioukov. Hyperbolic graph generator. Computer Physics Communications, 196:492-496, 2015. URL: http://dx.doi.org/10.1016/j.cpc.2015.05.028.
  4. Dena Marie Asta and Cosma Rohilla Shalizi. Geometric network comparisons. In 31st Conference on Uncertainty in Artificial Intelligence (UAI), pages 102-110, 2015. Google Scholar
  5. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286:509-512, 1999. Google Scholar
  6. Michel Bode, Nikolaos Fountoulakis, and Tobias Müller. On the giant component of random hyperbolic graphs. In 7th European Conf. Combinatorics, Graph Theory and Applications, pages 425-429, 2013. Google Scholar
  7. Michel Bode, Nikolaos Fountoulakis, and Tobias Müller. The probability that the hyperbolic random graph is connected. https://www.math.uu.nl/~Muell001/Papers/BFM.pdf, 2014.
  8. Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping. Nature Communications, 1:62, 2010. Google Scholar
  9. Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. arXiv preprint arXiv:1511.00576, 2015. Google Scholar
  10. F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6(2):125-145, 2002. Google Scholar
  11. Aaron Clauset, Cosma Rohilla Shalizi, and M. E. J. Newman. Power-law distributions in empirical data. SIAM Review, 51(4):661-703, 2009. Google Scholar
  12. James R. Clough and Tim S. Evans. Embedding graphs in lorentzian spacetime. arXiv 1602.03103, 2016. Google Scholar
  13. Trevor F. Cox and M.A.A. Cox. Multidimensional Scaling, Second Edition. Chapman and Hall/CRC, 2 edition, 2000. Google Scholar
  14. Tobias Friedrich and Anton Krohmer. Cliques in hyperbolic random graphs. In 34th IEEE Conf. Computer Communications (INFOCOM), pages 1544-1552, 2015. Google Scholar
  15. Tobias Friedrich and Anton Krohmer. On the diameter of hyperbolic random graphs. In 42nd Intl. Coll. Automata, Languages and Programming (ICALP), pages 614-625, 2015. Google Scholar
  16. Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random hyperbolic graphs: degree sequence and clustering. In 39th Intl. Coll. Automata, Languages and Programming (ICALP), pages 573-585, 2012. Google Scholar
  17. Stephen G. Kobourov. Handbook of Graph Drawing and Visualization, chapter Force-Directed Drawing Algorithms, pages 383-408. Chapman and Hall/CRC, 2013. Google Scholar
  18. Stephen G. Kobourov and Kevin Wampler. Non-eeuclidean spring embedders. IEEE Transactions on Visualization and Computer Graphics, 11(6):757-767, 2005. Google Scholar
  19. Christoph Koch and Johannes Lengler. Bootstrap percolation on geometric inhomogeneous random graphs. In 43rd Intl. Coll. Automata, Languages and Programming (ICALP), 2016. Google Scholar
  20. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 82:036106, 2010. Google Scholar
  21. John Lamping, Ramana Rao, and Peter Pirolli. A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. In 13th ACM CHI, pages 401-408, 1995. URL: http://dx.doi.org/10.1145/223904.223956.
  22. Jonh Lamping and Ramana Rao. The hyperbolic browser: A focus+context technique for visualizing large hierarchies. Journal of Visual Languages & Computing, 7(1):33-55, 1996. Google Scholar
  23. David Liben-Nowell and Jon M. Kleinberg. The link-prediction problem for social networks. J. Am. Soc. Inf. Sci., 58(7):1019-1031, 2007. URL: http://dx.doi.org/10.1002/asi.20591.
  24. Tamara Munzner. Exploring large graphs in 3d hyperbolic space. IEEE Computer Graphics and Applications, 18(4):18-23, 1998. URL: http://dx.doi.org/10.1109/38.689657.
  25. M. E. J. Newman. Clustering and preferential attachment in growing networks. Phys. Rev. E, 64:025102, 2001. Google Scholar
  26. Ilkka Norros and Hannu Reittu. On a conditionally Poissonian graph process. Advances in Applied Probability, 38(1):59-75, 2006. Google Scholar
  27. Fragkiskos Papadopoulos, Rodrigo Aldecoa, and Dmitri Krioukov. Network geometry inference using common neighbors. Phys. Rev. E, 92:022807, Aug 2015. URL: http://dx.doi.org/10.1103/PhysRevE.92.022807.
  28. Fragkiskos Papadopoulos, Maksim Kitsak, M Ángeles Serrano, Marián Boguñá, and Dmitri Krioukov. Popularity versus similarity in growing networks. Nature, 489(7417):537-540, 2012. Google Scholar
  29. Fragkiskos Papadopoulos, Constantinos Psomas, and Dmitri V. Krioukov. Network mapping by replaying hyperbolic growth. IEEE/ACM Trans. Netw., 23(1):198-211, 2015. URL: http://dx.doi.org/10.1109/TNET.2013.2294052.
  30. Mathew D. Penrose. Random Geometric Graphs. Oxford University Press, 2003. Google Scholar
  31. Yuval Shavitt and Tomer Tankel. Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE/ACM Trans. Netw., 16(1):25-36, 2008. URL: http://dx.doi.org/10.1145/1373452.1373455.
  32. Eleni Stai, Vasileios Karyotis, and Symeon Papavassiliou. A hyperbolic space analytics framework for big network data and their applications. IEEE Network, 30(1):11-17, 2016. URL: http://dx.doi.org/10.1109/MNET.2016.7389825.
  33. Remco van der Hofstad. Random graphs and complex networks. Available at https://www.win.tue.nl/~rhofstad/NotesRGCN.pdf, 2011.
  34. Alexei Vázquez. Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. Phys. Rev. E, 67:056104, May 2003. URL: http://dx.doi.org/10.1103/PhysRevE.67.056104.
  35. Kevin Verbeek and Subhash Suri. Metric embedding, hyperbolic space, and social networks. In 30th Annual Symposium on Computational Geometry (SOCG), page 501, 2014. URL: http://dx.doi.org/10.1145/2582112.2582139.
  36. Moritz von Looz, Henning Meyerhenke, and Roman Prutkin. Generating random hyperbolic graphs in subquadratic time. In 26th Intl. Symp. Algorithms and Computation (ISAAC), pages 467-478. Springer, 2015. Google Scholar
  37. Jörg A. Walter. H-MDS: a new approach for interactive visualization with multidimensional scaling in the hyperbolic space. Inf. Syst., 29(4):273-292, 2004. URL: http://dx.doi.org/10.1016/j.is.2003.10.002.
  38. Jörg A. Walter and Helge J. Ritter. On interactive visualization of high-dimensional data using the hyperbolic plane. In 8th ACM Intl. Conf. Knowledge Discovery and Data Mining (SIGKDD), pages 123-132, 2002. URL: http://dx.doi.org/10.1145/775047.775065.
  39. Zuxi Wang, Qingguang Li, Fengdong Jin, Wei Xiong, and Yao Wu. Hyperbolic mapping of complex networks based on community information. Physica A: Statistical Mechanics and its Applications, 455:104-119, 2016. Google Scholar
  40. Kilian Q Weinberger and Lawrence K Saul. Unsupervised learning of image manifolds by semidefinite programming. International Journal of Computer Vision, 70(1):77-90, 2006. Google Scholar
  41. Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 42(1):181-213, 2015. Google Scholar
  42. Xiaohan Zhao, Alessandra Sala, Haitao Zheng, and Ben Y. Zhao. Efficient shortest paths on massive social graphs. In 7th International Conference on Collaborative Computing (CollaborateCom), pages 77-86, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact