{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,5]],"date-time":"2026-11-05T17:53:04Z","timestamp":1793901184907,"version":"4.8.0"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the Internet can be mapped to a hyperbolic space such that geometric greedy routing is close to optimal [M. Bogun\u0342\u00e1, F. Papadopoulos, and D. Krioukov, Nature Commun., 1 (2010), pp. 1--62]. This observation has pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power law degree distribution with controllable exponent $\\beta$ and show high clustering [L. Gugelmann, K. Panagiotou, and U. Peter, Proceedings of the 39 th International Colloquium on Automata, Languages and Programming, 2012, pp. 573--585]. For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is $\\mathcal{O}((\\log n)^{32\/((3-\\beta)(5-\\beta)) + 1})$ [M. Kiwi and D. Mitsche, Proceedings of ANALCO, 2015, pp. 26--39]. We present two much simpler proofs for an improved upper bound of $\\mathcal{O}((\\log n)^{2\/(3-\\beta)})$ and a lower bound of $\\Omega(\\log n)$. If $\\beta &gt; 3$, we show that the latter bound is tight by proving an upper bound of $\\mathcal{O}(\\log n)$ for the diameter.<\/jats:p>","DOI":"10.1137\/17m1123961","type":"journal-article","created":{"date-parts":[[2018,6,12]],"date-time":"2018-06-12T14:01:09Z","timestamp":1528812069000},"page":"1314-1334","source":"Crossref","is-referenced-by-count":32,"title":["On the Diameter of Hyperbolic Random Graphs"],"prefix":"10.1137","volume":"32","author":[{"given":"Tobias","family":"Friedrich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anton","family":"Krohmer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,12]]},"reference":[{"key":"atypb1","unstructured":"M. A. Abdullah, M. Bode, and N. Fountoulakis,\n                      Typical Distances in a Geometric Model for Complex Networks\n                      , preprint,arXiv:1506.07811, 2015."},{"key":"atypb2","first-page":"6","author":"Alanis-Lobato G.","year":"2016","journal-title":"Scientific Reports"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"atypb4","unstructured":"T. Bla\u0308sius, T. Friedrich, and A. Krohmer,\n                      Hyperbolic random graphs: Separators and treewidth\n                      , in Proceedings of the 24th European Symposium on Algorithms, 2016, pp. 15:1-15:16."},{"key":"atypb5","unstructured":"T. Bla\u0308sius, T. Friedrich, A. Krohmer, and S. Laue,\n                      Efficient embedding of scale-free graphs in the hyperbolic plane\n                      , in Proceedings of the 24th European Symposium on Algorithms, 2016, pp. 16:1-16:18."},{"key":"atypb6","first-page":"425","author":"Bode M.","year":"2013","journal-title":"Graph Theory and Applications"},{"key":"atypb7","unstructured":"M. Bode, N. Fountoulakis, and T. Mu\u0308ller,\n                      The Probability That the Hyperbolic Random Graph Is Connected\n                      ,http:\/\/www.math.uu.nl\/~Muell001\/Papers\/BFM.pdf(2014)."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms1063"},{"key":"atypb9","unstructured":"B. Bolloba\u0301s,\n                      Random Graphs\n                      , Springer, New York, 1998."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/0401033"},{"key":"atypb11","unstructured":"K. Bringmann, R. Keusch, and J. Lengler,\n                      Geometric Inhomogeneous Random Graphs\n                      , preprint,arXiv:1511.00576, 2015."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.spa.2015.08.005"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.252631999"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"B. Doerr and L. A. Goldberg,\n                      Drift analysis with tail bounds\n                      , in Proceedings of the 11th International Conference on Parallel Problem Solving from Nature, 2010, pp. 174-183.","DOI":"10.1007\/978-3-642-15844-5_18"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-010-9921-z"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"D. Dubhashi and A. Panconesi,\n                      Concentration of Measure for the Analysis of Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 2009.","DOI":"10.1017\/CBO9780511581274"},{"key":"atypb17","unstructured":"M. Evans, N. Hastings, and B. Peacock,\n                      Statistical Distributions\n                      , 4th ed., Wiley-Interscience, New York, 2000."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"N. Fountoulakis, K. Panagiotou, and T. Sauerwald,\n                      Ultra-fast rumor spreading in social networks\n                      , in Proceedings of the 23rd Symposium on Discrete Algorithms, 2012, pp. 1642-1660.","DOI":"10.1137\/1.9781611973099.130"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"T. Friedrich and A. Krohmer,\n                      Cliques in hyperbolic random graphs\n                      , in Proceedings of the 34th IEEE Conference on Computer Communications, 2015, pp. 1544-1552.","DOI":"10.1109\/INFOCOM.2015.7218533"},{"key":"atypb20","first-page":"614","author":"Friedrich T.","year":"2015","journal-title":"Languages and Programming"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9710-y"},{"key":"atypb22","first-page":"573","author":"Gugelmann L.","year":"2012","journal-title":"Languages and Programming"},{"key":"atypb23","first-page":"17","volume":"26","author":"Jagers P.","year":"1973","journal-title":"Probab. Theory Relat. Fields"},{"key":"atypb24","first-page":"26","author":"Kiwi M.","year":"2015","journal-title":"Proceedings of ANALCO"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.036106"},{"key":"atypb27","unstructured":"P. K. Lehre and C. Witt,\n                      General Drift Analysis with Tail Bounds\n                      , preprint,arXiv:1307.2559, 2013."},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"C. U. Martel and V. Nguyen,\n                      Analyzing Kleinberg's (and other) small-world models\n                      , in Proceedings of 23rd Symposium on Principles of Distributed Computing, 2004, pp. 179-188.","DOI":"10.1145\/1011767.1011794"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher and E. Upfal,\n                      Probability and Computing: Randomized Algorithms and Probabilistic Analysis\n                      , Cambridge University Press, Cambridge, UK, 2005.","DOI":"10.1017\/CBO9780511813603"},{"key":"atypb30","unstructured":"T. Mu\u0308ller and M. Staps,\n                      The Diameter of KPKVB Random Graphs\n                      , preprint,arXiv:1707.09555, 2017."},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"F. Papadopoulos, D. Krioukov, M. Bogun\u0342a\u0301, and A. Vahdat,\n                      Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces\n                      , in Proceedings of the 29th IEEE Conference on Computer Communications, 2010, pp. 2973-2981.","DOI":"10.1109\/INFCOM.2010.5462131"},{"key":"atypb32","first-page":"92","author":"Papadopoulos F.","year":"2015","journal-title":"Phys. Rev. E."},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"M. D. Penrose,\n                      Random Geometric Graphs\n                      , Oxford University Press, New York, 2003.","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000325"},{"key":"atypb35","first-page":"467","author":"von Looz M.","year":"2015","journal-title":"New York"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2016.02.015"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1038\/30918"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1123961","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:10Z","timestamp":1787317570000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1123961"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1123961"],"URL":"https:\/\/doi.org\/10.1137\/17m1123961","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}