Document Open Access Logo

On the Giant Component of Geometric Inhomogeneous Random Graphs

Authors Thomas Bläsius, Tobias Friedrich , Maximilian Katzmann, Janosch Ruff, Ziena Zeif

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.20.pdf
  • Filesize: 0.75 MB
  • 13 pages

Document Identifiers

Author Details

Thomas Bläsius
  • Karlsruhe Institute of Technology, Germany
Tobias Friedrich
  • Hasso Plattner Institute, University of Potsdam, Germany
Maximilian Katzmann
  • Karlsruhe Institute of Technology, Germany
Janosch Ruff
  • Hasso Plattner Institute, University of Potsdam, Germany
Ziena Zeif
  • Hasso Plattner Institute, University of Potsdam, Germany

Cite AsGet BibTex

Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Janosch Ruff, and Ziena Zeif. On the Giant Component of Geometric Inhomogeneous Random Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.20

Abstract

In this paper we study the threshold model of geometric inhomogeneous random graphs (GIRGs); a generative random graph model that is closely related to hyperbolic random graphs (HRGs). These models have been observed to capture complex real-world networks well with respect to the structural and algorithmic properties. Following comprehensive studies regarding their connectivity, i.e., which parts of the graphs are connected, we have a good understanding under which circumstances a giant component (containing a constant fraction of the graph) emerges. While previous results are rather technical and challenging to work with, the goal of this paper is to provide more accessible proofs. At the same time we significantly improve the previously known probabilistic guarantees, showing that GIRGs contain a giant component with probability 1 - exp(-Ω(n^{(3-τ)/2})) for graph size n and a degree distribution with power-law exponent τ ∈ (2, 3). Based on that we additionally derive insights about the connectivity of certain induced subgraphs of GIRGs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random network models
Keywords
  • geometric inhomogeneous random graphs
  • connectivity
  • giant component

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 power law graphs. Experimental Mathematics, 10(1):53-66, 2001. URL: https://doi.org/10.1080/10586458.2001.10504428.
  2. Martin J.B. Appel and Ralph P. Russo. The connectivity of a graph on uniform points on [0,1]^d. Statistics & Probability Letters, 60(4):351-357, 2002. URL: https://doi.org/10.1016/S0167-7152(02)00233-X.
  3. Thomas Bläsius and Philipp Fischbeck. On the External Validity of Average-Case Analyses of Graph Algorithms. In European Symposium on Algorithms (ESA 2022), pages 21:1-21:14, 2022. URL: https://doi.org/10.4230/LIPIcs.ESA.2022.21.
  4. Thomas Bläsius, Tobias Friedrich, and Christopher Weyand. Efficiently Computing Maximum Flows in Scale-Free Networks. In 29th Annual European Symposium on Algorithms (ESA 2021), volume 204, pages 21:1-21:14, 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.21.
  5. Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently generating geometric inhomogeneous and hyperbolic random graphs. Network Science, 10(4):361-380, 2022. URL: https://doi.org/10.1017/nws.2022.32.
  6. Michel Bode, N. Fountoulakis, and Tobias Müller. On the largest component of a hyperbolic model of complex networks. Electronic Journal of Combinatorics, 22:1-46, August 2015. URL: https://doi.org/10.1214/17-AAP1314.
  7. Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, and Anisur R. Molla. Greedy routing and the algorithmic small-world phenomenon. Journal of Computer and System Sciences, 125:59-105, 2022. URL: https://doi.org/10.1016/j.jcss.2021.11.003.
  8. Yong Chen, Zhi-Zhong Chen, Guohui Lin, Yao Xu, and An Zhang. Approximation Algorithms for Maximally Balanced Connected Graph Partition. Algorithmica, 83:3715-3740, 2021. URL: https://doi.org/10.1007/s00453-021-00870-3.
  9. Fan Chung and Linyuan Lu. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences, 99(25):15879-15882, 2002. URL: https://doi.org/10.1073/pnas.252631999.
  10. Fan Chung and Linyuan Lu. Connected Components in Random Graphs with Given Expected Degree Sequences. Annals of Combinatorics, 6(2):125-145, 2002. URL: https://doi.org/10.1007/PL00012580.
  11. Josep Díaz, Dieter Mitsche, and Xavier Pérez-Giménez. On the Connectivity of Dynamic Random Geometric Graphs. In Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 601-610, 2008. URL: https://dl.acm.org/doi/abs/10.5555/1347082.1347149.
  12. Paul Erdős, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960. Google Scholar
  13. Paul Erdős and Alfréd Rényi. On Random Graphs I. Publicationes Mathematicae Debrecen, 6:290-297, 1959. Google Scholar
  14. Nikolaos Fountoulakis and Tobias Müller. Law of large numbers for the largest component in a hyperbolic model of complex networks. The Annals of Applied Probability, 28(1):607-650, 2018. URL: https://www.jstor.org/stable/26542317.
  15. Tobias Friedrich and Anton Krohmer. On the Diameter of Hyperbolic Random Graphs. SIAM Journal on Discrete Mathematics, 32(2):1314-1334, 2018. URL: https://doi.org/10.1137/17M1123961.
  16. Daniel Gross, Monika Heinig, L. Iswara, L.W. Kazmierczak, Kristi Luttrell, John Saccoman, and C. Suffel. A Survey of Component Order Connectivity Models of Graph Theoretic Networks. WSEAS Transactions on Mathematics, 12:895-910, 2013. Google Scholar
  17. Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random Hyperbolic Graphs: Degree Sequence and Clustering. In 39th International Colloquium on Automata, Languages, and Programming (ICALP), pages 573-585, 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_51.
  18. P. Gupta and P.R. Kumar. Critical power for asymptotic connectivity. In 37th IEEE Conference on Decision and Control, volume 1, pages 1106-1110, 1998. URL: https://doi.org/10.1109/CDC.1998.760846.
  19. Ralph Keusch. Geometric Inhomogeneous Random Graphs and Graph Coloring Games. PhD thesis, ETH Zurich, 2018. URL: https://doi.org/10.3929/ethz-b-000269658.
  20. Marcos Kiwi and Dieter Mitsche. On the second largest component of random hyperbolic graphs. SIAM Journal on Discrete Mathematics, 33(4):2200-2217, 2019. URL: https://doi.org/10.1137/18M121201X.
  21. Júlia Komjáthy, John Lapinskas, and Johannes Lengler. Penalising transmission to hubs in scale-free spatial random graphs. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 57(4):1968-2016, 2021. URL: https://doi.org/10.1214/21-AIHP1149.
  22. Júlia Komjáthy and Bas Lodewijks. Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs. Stochastic Processes and their Applications, 130(3):1309-1367, 2020. URL: https://doi.org/10.1016/j.spa.2019.04.014.
  23. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Physical Review E, 82:036106, 2010. URL: https://doi.org/10.1103/PhysRevE.82.036106.
  24. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. URL: https://doi.org/10.1017/CBO9780511813603.
  25. Tobias Müller and Merlijn Staps. The Diameter of KPKVB Random Graphs. Advances in Applied Probability, 51(2):358-377, 2019. URL: https://doi.org/10.1017/apr.2019.23.
  26. Mathew Penrose. Random Geometric Graphs. Oxford University Press, 2003. Google Scholar
  27. Stephan Schwartz. An overview of graph covering and partitioning. Discrete Mathematics, 345(8):112884, 2022. URL: https://doi.org/10.1016/j.disc.2022.112884.
  28. Bo Söderberg. General formalism for inhomogeneous random graphs. Phys. Rev. E, 66:066121, 2002. URL: https://doi.org/10.1103/PhysRevE.66.066121.
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 Imprint Privacy Contact