Document Open Access Logo

Sampling Geometric Inhomogeneous Random Graphs in Linear Time

Authors Karl Bringmann, Ralph Keusch, Johannes Lengler

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.20.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Karl Bringmann
Ralph Keusch
Johannes Lengler

Cite As Get BibTex

Karl Bringmann, Ralph Keusch, and Johannes Lengler. Sampling Geometric Inhomogeneous Random Graphs in Linear Time. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.20

Abstract

Real-world networks, like social networks or the internet infrastructure, have structural properties such as large clustering coefficients that can best be described in terms of an underlying geometry. This is why the focus of the literature on theoretical models for real-world networks shifted from classic models without geometry, such as Chung-Lu random graphs, to modern geometry-based models, such as hyperbolic random graphs. 
  
With this paper we contribute to the theoretical analysis of these modern, more realistic random graph models. Instead of studying directly hyperbolic random graphs, we introduce a generalization that we call geometric inhomogeneous random graphs (GIRGs). Since we ignore constant factors in the edge probabilities, GIRGs are technically simpler (specifically, we avoid hyperbolic cosines), while preserving the qualitative behaviour of hyperbolic random graphs, and we suggest to replace hyperbolic random graphs by this new model in future theoretical studies.
  
We prove the following fundamental structural and algorithmic results on GIRGs. (1) As our main contribution we provide a sampling algorithm that generates a random graph from our model in expected linear time, improving the best-known sampling algorithm for hyperbolic random graphs by a substantial factor O(n^0.5). (2) We establish that GIRGs have clustering coefficients in Omega(1), (3) we prove that GIRGs have small separators, i.e., it suffices to delete a sublinear number of edges to break the giant component into two large pieces, and (4) we show how to compress GIRGs using an expected linear number of bits.

Subject Classification

Keywords
  • real-world networks
  • random graph models
  • sampling algorithms
  • compression algorithms
  • hyperbolic random graphs

Metrics

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

References

  1. M. A. Abdullah, M. Bode, and N. Fountoulakis. Typical distances in a geometric model for complex networks. Preprint available at arXiv:1506.07811, 2015. Google Scholar
  2. W. Aiello, A. Bonato, C. Cooper, J. Janssen, and P. Prałat. A spatial web graph model with local influence regions. Internet Mathematics, 5(1-2):175-196, 2008. Google Scholar
  3. A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. Google Scholar
  4. V. Batagelj and U. Brandes. Efficient generation of large random networks. Physical Review E, 71(3):036113, 2005. Google Scholar
  5. D. K. Blandford, G. E. Blelloch, and I. A. Kash. Compact representations of separable graphs. In Proceedings of the 14 annual ACM-SIAM Symposium on Discrete algorithms (SODA), pages 679-688. SIAM, 2003. Google Scholar
  6. T. Bläsius, T. Friedrich, and A. Krohmer. Hyperbolic random graphs: Separators and treewidth. In European Symposium on Algorithms (ESA), pages 15:1-15:16, 2016. Google Scholar
  7. T. Bläsius, T. Friedrich, and A. Krohmer. Cliques in hyperbolic random graphs. Algorithmica, 2017. Google Scholar
  8. T. Bläsius, T. Friedrich, A. Krohmer, and S. Laue. Efficient embedding of scale-free graphs in the hyperbolic plane. In European Symposium on Algorithms (ESA), pages 16:1-16:18, 2016. Google Scholar
  9. M. Bode, N. Fountoulakis, and T. Müller. On the giant component of random hyperbolic graphs. In 7th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), pages 425-429. Springer, 2013. Google Scholar
  10. M. Bode, N. Fountoulakis, and T. Müller. On the geometrisation of the Chung-Lu model and its component structure. Preprint, 2014. Google Scholar
  11. M. Boguñá, F. Papadopoulos, and D. Krioukov. Sustaining the Internet with hyperbolic mapping. Nature Communications, 1(6), September 2010. Google Scholar
  12. P. Boldi and S. Vigna. The WebGraph framework I : compression techniques. In 13th International Conference on World Wide Web (WWW), pages 595-602, 2004. Google Scholar
  13. B. Bollobás, S. Janson, and O. Riordan. The phase transition in inhomogeneous random graphs. Random Structures &Algorithms, 31(1):3-122, 2007. Google Scholar
  14. A. Bonato, J. Janssen, and P. Prałat. A geometric model for on-line social networks. In 1st International Workshop on Modeling Social Media (WOSM), 2010. Google Scholar
  15. M. Bradonjić, A. Hagberg, and A. G. Percus. The structure of geographical threshold graphs. Internet Mathematics, 5(1-2):113-139, 2008. Google Scholar
  16. K. Bringmann and T. Friedrich. Exact and efficient generation of geometric random variates and random graphs. In 40th International Colloquium on Automata, Languages, and Programming (ICALP), pages 267-278, 2013. Google Scholar
  17. K. Bringmann, R. Keusch, and J. Lengler. Average distance in a general class of scale-free networks with underlying geometry. Preprint avaiable at arxiv:1602.05712, 2016. Google Scholar
  18. K. Bringmann, R. Keusch, and J. Lengler. Sampling geometric inhomogeneous random graphs in linear time. Preprint available at arXiv:1511.00576, 2016. Google Scholar
  19. K. Bringmann, R. Keusch, J. Lengler, Y. Maus, and A. Molla. Greedy routing and the algorithmic small-world phenomenon. Preprint available at arXiv:1612.05539, 2017. Google Scholar
  20. E. Candellero and N. Fountoulakis. Clustering and the hyperbolic geometry of complex networks. In 11th International Workshop on Algorithms and Models for the Web Graph (WAW), pages 1-12, 2014. Google Scholar
  21. E. Candellero and N. Fountoulakis. Bootstrap percolation and the geometry of complex networks. Stochastic Processes and their Applications, 126:234-264, 2016. Google Scholar
  22. F. Chierichetti, R. Kumar, S. Lattanzi, M. Mitzenmacher, A. Panconesi, and P. Raghavan. On compressing social networks. In 15th International Conference on Knowledge Discovery and Data Mining (KDD), pages 219-228, 2009. Google Scholar
  23. F. Chierichetti, R. Kumar, S. Lattanzi, A. Panconesi, and P. Raghavan. Models for the Compressible Web. In 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 331-340, 2009. Google Scholar
  24. F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences (PNAS), 99(25):15879-15882, 2002. Google Scholar
  25. 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
  26. F. Chung and L. Lu. The average distance in a random graph with given expected degrees. Internet Mathematics, 1(1):91-113, 2004. Google Scholar
  27. D. R. Clark and I. Munro. Efficient suffix trees on secondary storage. In Proceedings of the 7 annual ACM-SIAM Symposium on Discrete algorithms (SODA), pages 383-391. SIAM, 1996. Google Scholar
  28. M. Deijfen, R. van der Hofstad, and G. Hooghiemstra. Scale-free percolation. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 49(3):817-838, 2013. Google Scholar
  29. P. Deprez, R. S. Hazra, and M. V. Wüthrich. Inhomogeneous long-range percolation for real-life network modeling. Risks, 3(1), 2015. Google Scholar
  30. L. Devroye. Nonuniform random variate generation. Springer, New York, 1986. Google Scholar
  31. S. N. Dorogovtsev and J. F. F. Mendes. Evolution of networks. Advances in Physics, 51(4):1079-1187, 2002. Google Scholar
  32. T. Friedrich and A. Krohmer. On the diameter of hyperbolic random graphs. In 42nd International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, 2015. Google Scholar
  33. L. Gugelmann, K. Panagiotou, and U. Peter. Random hyperbolic graphs: degree sequence and clustering. In 39th International Colloquium on Automata, Languages, and Programming (ICALP), pages 573-585, 2012. Google Scholar
  34. M. Heydenreich, T. Hulshof, and J. Jorritsma. Structures in supercritical scale-free percolation. Preprint available at arXiv:1604.08180, 2016. Google Scholar
  35. E. Jacob and P. Mörters. A spatial preferential attachment model with local clustering. In Algorithms and Models for the Web Graph, pages 14-25. Springer, 2013. Google Scholar
  36. G. Jacobson. Space-efficient static trees and graphs. In 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 549-554, 1989. Google Scholar
  37. M. Kiwi and D. Mitsche. A bound for the diameter of random hyperbolic graphs. In 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pages 26-39. SIAM, 2015. Google Scholar
  38. M. Kiwi and D. Mitsche. Spectral gap of random hyperbolic graphs and related parameters. Preprint available at arXiv:1606.02240, 2016. Google Scholar
  39. C. Koch and J. Lengler. Bootstrap percolation on geometric inhomogeneous random graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 147:1-147:15, 2016. Google Scholar
  40. J. C. Miller and A. Hagberg. Efficient generation of networks with given expected degrees. In 8th International Conference on Algorithms and Models for the Web Graph (WAW), pages 115-126, 2011. Google Scholar
  41. I. Norros and H. Reittu. On a conditionally Poissonian graph process. Advances in Applied Probability, 38(1):59-75, 2006. Google Scholar
  42. F. Papadopoulos, D. Krioukov, M. Boguñá, and A. Vahdat. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In INFOCOM 2010. 29th IEEE International Conference on Computer Communications, pages 1-9, March 2010. Google Scholar
  43. M. Pătraşcu. Succincter. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 305-313, 2008. Google Scholar
  44. M. Penrose. Random geometric graphs, volume 5. Oxford University Press Oxford, 2003. Google Scholar
  45. U. Peter. Random Graph Models for Complex Systems. PhD thesis, ETH Zurich, 2014. Google Scholar
  46. R. van der Hofstad and J. Komjathy. Explosion and distances in scale-free percolation. arXiv preprint arXiv:1706.02597, 2017. Google Scholar
  47. M. Von Looz, C. L. Staudt, H. Meyerhenke, and R. Prutkin. Fast generation of dynamic complex networks with underlying hyperbolic geometry. Preprint available at arXiv:1501.03545, 2015. 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