Document Open Access Logo

Cover and Hitting Times of Hyperbolic Random Graphs

Authors Marcos Kiwi , Markus Schepers , John Sylvester

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.30.pdf
  • Filesize: 0.84 MB
  • 19 pages

Document Identifiers

Author Details

Marcos Kiwi
  • Department of Industrial Engineering and Center for Mathematical Modeling, Universidad de Chile, Santiago, Chile
Markus Schepers
  • Institut für Medizinische Biometrie, Epidemiologie und Informatik, Johannes-Gutenberg-University Mainz, Germany
John Sylvester
  • School of Computing Science, University of Glasgow, UK

Funding

  • Kiwi, Marcos: gratefully acknowledges the support of grant GrHyDy ANR-20-CE40-0002 and BASAL funds for centers of excellence from ANID-Chile grants ACE210010 and FB210005.
  • Schepers, Markus: gratefully acknowledges the support of the DIAMANT PhD travel grant for a 2-week research stay in Santiago de Chile.
  • Sylvester, John: was supported by EPSRC project EP/T004878/1: Multilayer Algorithmics to Leverage Graph Structure and the ERC Starting Grant 679660 (DYNAMIC MARCH).

Cite AsGet BibTex

Marcos Kiwi, Markus Schepers, and John Sylvester. Cover and Hitting Times of Hyperbolic Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.30

Abstract

We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range (2,3). In particular, we focus on the expected times for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that up to multiplicative constants: the cover time is n(log n)², the maximum hitting time is nlog n, and the average hitting time is n. The first two results hold in expectation and a.a.s. and the last in expectation (with respect to the HRG). We prove these results by determining the effective resistance either between an average vertex and the well-connected "center" of HRGs or between an appropriately chosen collection of extremal vertices. We bound the effective resistance by the energy dissipated by carefully designed network flows associated to a tiling of the hyperbolic plane on which we overlay a forest-like structure.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Theory of computation → Random network models
  • Mathematics of computing → Stochastic processes
Keywords
  • Random walk
  • hyperbolic random graph
  • cover time
  • hitting time
  • average hitting time
  • target time
  • effective resistance
  • Kirchhoff index

Metrics

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

Related Versions

References

  1. Mohammed Amin Abdullah, Michel Bode, and Nikolaos Fountoulakis. Typical distances in a geometric model for complex networks. Internet Math., page 38, 2017. Google Scholar
  2. Tasweer Ahmad, Lianwen Jin, Luojun Lin, and Guozhi Tang. Skeleton-based action recognition using sparse spatio-temporal GCN with edge effective resistance. Neurocomputing, 423:389-398, 2021. URL: https://doi.org/10.1016/j.neucom.2020.10.096.
  3. David Aldous and James Allen Fill. Reversible Markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014. URL: https://www.stat.berkeley.edu/~aldous/RWG/book.html.
  4. Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979, pages 218-223. IEEE Computer Society, 1979. URL: https://doi.org/10.1109/SFCS.1979.34.
  5. Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph clustering using effective resistance. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.41.
  6. Nima Anari and Shayan Oveis Gharan. Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 20-39. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.11.
  7. Chen Avin and Gunes Ercal. On the cover time and mixing time of random geometric graphs. Theor. Comput. Sci., 380(1-2):2-22, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02.065.
  8. Anna Ben-Hamou, Roberto I. Oliveira, and Yuval Peres. Estimating graph parameters via random walks with restarts. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1702-1714. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.111.
  9. Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Hyperbolic random graphs: Separators and treewidth. In 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  10. Mindaugas Bloznelis, Jerzy Jaworski, and Katarzyna Rybarczyk. The cover time of a sparse random intersection graph, 2019. URL: https://doi.org/10.48550/ARXIV.1910.09639.
  11. Michel Bode, Nikolaos Fountoulakis, and Tobias Müller. On the largest component of a hyperbolic model of complex networks. Electron. J. Comb., 22(3):P3.24, 2015. URL: https://doi.org/10.37236/4958.
  12. Michel Bode, Nikolaos Fountoulakis, and Tobias Müller. The probability of connectivity in a hyperbolic model of complex networks. Random Struct. Algorithms, 49(1):65-94, 2016. Google Scholar
  13. Marián Boguná, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping. Nature communications, 1(1):1-8, 2010. Google Scholar
  14. Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. Theoretical Computer Science, 760:35-54, 2019. Google Scholar
  15. Elisabetta Candellero and Nikolaos Fountoulakis. Bootstrap percolation and the geometry of complex networks. Stochastic Processes and their Applications, 126(1):234-264, 2016. Google Scholar
  16. Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times. Comput. Complex., 6(4):312-340, 1997. URL: https://doi.org/10.1007/BF01270385.
  17. Jordan Chellig, Nikolaos Fountoulakis, and Fiona Skerman. The modularity of random graphs on the hyperbolic plane, 2021. URL: http://arxiv.org/abs/2104.01041.
  18. Paul F. Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 273-282. ACM, 2011. URL: https://doi.org/10.1145/1993636.1993674.
  19. Alessandra Cipriani and Michele Salvi. Scale-free percolation mixing time, 2021. URL: https://doi.org/10.48550/ARXIV.2111.05201.
  20. Colin Cooper and Alan M. Frieze. The cover time of sparse random graphs. Random Struct. Algorithms, 30(1-2):1-16, 2007. URL: https://doi.org/10.1002/rsa.20151.
  21. Colin Cooper and Alan M. Frieze. The cover time of the preferential attachment graph. J. Comb. Theory B, 97(2):269-290, 2007. URL: https://doi.org/10.1016/j.jctb.2006.05.007.
  22. Colin Cooper and Alan M. Frieze. The cover time of the giant component of a random graph. Random Struct. Algorithms, 32(4):401-439, 2008. URL: https://doi.org/10.1002/rsa.20201.
  23. Colin Cooper and Alan M. Frieze. The cover time of random geometric graphs. Random Struct. Algorithms, 38(3):324-349, 2011. URL: https://doi.org/10.1002/rsa.20320.
  24. Colin Cooper and Alan M. Frieze. Stationary distribution and cover time of random walks on random digraphs. J. Comb. Theory B, 102(2):329-362, 2012. URL: https://doi.org/10.1016/j.jctb.2011.11.001.
  25. Colin Cooper, Alan M. Frieze, and Eyal Lubetzky. Cover time of a random graph with a degree sequence II: Allowing vertices of degree two. Random Struct. Algorithms, 45(4):627-674, 2014. URL: https://doi.org/10.1002/rsa.20573.
  26. Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, and Christian Sohler. Planar graphs: Random walks and bipartiteness testing. Random Struct. Algorithms, 55(1):104-124, 2019. URL: https://doi.org/10.1002/rsa.20826.
  27. Maria Deijfen, Remco Van der Hofstad, and Gerard Hooghiemstra. Scale-free percolation. Annales de l'IHP Probabilités et statistiques, 49(3):817-838, 2013. Google Scholar
  28. Jian Ding, James R. Lee, and Yuval Peres. Cover times, blanket times, and majorizing measures. Ann. of Math. (2), 175(3):1409-1471, 2012. URL: https://doi.org/10.4007/annals.2012.175.3.8.
  29. Nikolaos Fountoulakis, Dieter Mitsche, Tobias Müller, and Markus Schepers. Hamilton cycles and perfect matchings in the KPKVB model. Stochastic Processes and their Applications, 131:340-358, 2021. Google Scholar
  30. Nikolaos Fountoulakis and Tobias Müller. Law of large numbers for the largest component in a hyperbolic model of complex networks. Ann. Appl. Probab., 28(1):607-650, 2018. URL: https://doi.org/10.1214/17-AAP1314.
  31. Nikolaos Fountoulakis, Pim van der Hoorn, Tobias Müller, and Markus Schepers. Clustering in a hyperbolic model of complex networks. Electron. J. Probab., 26:Paper No. 13, 132, 2021. URL: https://doi.org/10.1214/21-ejp583.
  32. Tobias Friedrich and Anton Krohmer. Cliques in hyperbolic random graphs. In 2015 IEEE Conference on Computer Communications (INFOCOM), pages 1544-1552. IEEE, 2015. Google Scholar
  33. Tobias Friedrich and Anton Krohmer. On the diameter of hyperbolic random graphs. SIAM J. Discret. Math., 32(2):1314-1334, 2018. URL: https://doi.org/10.1137/17M1123961.
  34. David Gans. A new model of the hyperbolic plane. The American Mathematical Monthly, 73(3):291-295, 1966. Google Scholar
  35. Christos Gkantsidis, Milena Mihail, and Amin Saberi. Hybrid search schemes for unstructured peer-to-peer networks. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 13-17 March 2005, Miami, FL, USA, pages 1526-1537. IEEE, 2005. URL: https://doi.org/10.1109/INFCOM.2005.1498436.
  36. Peter Gracar, Markus Heydenreich, Christian Mönch, and Peter Mörters. Recurrence versus transience for weight-dependent random connection models, 2021. URL: http://arxiv.org/abs/1911.04350.
  37. Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random hyperbolic graphs: Degree sequence and clustering. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Part II, volume 7392 of Lecture Notes in Computer Science, pages 573-585. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_51.
  38. Brieuc Guinard and Amos Korman. Tight bounds for the cover times of random walks with heterogeneous step lengths. In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 28:1-28:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.28.
  39. Markus Heydenreich, Tim Hulshof, and Joost Jorritsma. Structures in supercritical scale-free percolation. Ann. Appl. Probab., 27(4):2569-2604, 2017. URL: https://doi.org/10.1214/16-AAP1270.
  40. Jeremy G. Hoskins, Cameron Musco, Christopher Musco, and Babis Tsourakakis. Inferring networks from random walk-based node similarities. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 3708-3719, 2018. URL: https://proceedings.neurips.cc/paper/2018/hash/2f25f6e326adb93c5787175dda209ab6-Abstract.html.
  41. Johan Jonasson. On the cover time for random walks on random graphs. Comb. Probab. Comput., 7(3):265-279, 1998. URL: http://journals.cambridge.org/action/displayAbstract?aid=46637.
  42. Jeff Kahn, Jeong Han Kim, László Lovász, and Van H. Vu. The cover time, the blanket time, and the Matthews bound. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, pages 467-475. IEEE Computer Society, 2000. URL: https://doi.org/10.1109/SFCS.2000.892134.
  43. Varun Kanade, Frederik Mallmann-Trenn, and Thomas Sauerwald. On coalescence time in graphs: When is coalescing as fast as meeting? In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 956-965. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.59.
  44. David Kempe, Jon M. Kleinberg, and Alan J. Demers. Spatial gossip and resource location protocols. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 163-172. ACM, 2001. URL: https://doi.org/10.1145/380752.380796.
  45. Marcos Kiwi, Amitai Linker, and Dieter Mitsche. Tail bounds for detection times in mobile hyperbolic graphs, 2022. URL: https://doi.org/10.48550/ARXIV.2203.00209.
  46. Marcos Kiwi and Dieter Mitsche. A bound for the diameter of random hyperbolic graphs. In Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015, pages 26-39. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973761.3.
  47. Marcos Kiwi and Dieter Mitsche. Spectral gap of random hyperbolic graphs and related parameters. Ann. Appl. Probab., 28(2):941-989, 2018. Google Scholar
  48. Marcos Kiwi and Dieter Mitsche. On the second largest component of random hyperbolic graphs. SIAM J. Discrete Math., 33(4):2200-2217, 2019. URL: https://doi.org/10.1137/18M121201X.
  49. Marcos Kiwi, Markus Schepers, and John Sylvester. Cover and hitting times of hyperbolic random graphs, 2022. URL: https://doi.org/10.48550/ARXIV.2207.06956.
  50. Christoph Koch and Johannes Lengler. Bootstrap percolation on geometric inhomogeneous random graphs. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 147:1-147:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.147.
  51. 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.
  52. D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 82(3):036106, 18, 2010. URL: https://doi.org/10.1103/PhysRevE.82.036106.
  53. Akash Kumar, C. Seshadhri, and Andrew Stolman. Finding forbidden minors in sublinear time: A n^1/2+o(1)-query one-sided tester for minor closed properties on bounded degree graphs. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 509-520. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00055.
  54. Akash Kumar, C. Seshadhri, and Andrew Stolman. Random walks and forbidden minors II: A poly(d/ε)-query tester for minor-closed properties of bounded degree graphs. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 559-567. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316330.
  55. G. Last and M. Penrose. Lectures on the Poisson Process. IMS Textbooks. Cambridge University Press, 2018. Google Scholar
  56. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, Providence, RI, 2009. Google Scholar
  57. Huan Li and Zhongzhi Zhang. Kirchhoff index as a measure of edge centrality in weighted networks: Nearly linear time algorithms. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2377-2396. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.153.
  58. Amitai Linker, Dieter Mitsche, Bruno Schapira, and Daniel Valesin. The contact process on random hyperbolic graphs: metastability and critical exponents. Ann. Probab., 49(3):1480-1514, 2021. URL: https://doi.org/10.1214/20-aop1489.
  59. László Lovász. Random walks on graphs: A survey. In Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 353-397. János Bolyai Math. Soc., Budapest, 1996. Google Scholar
  60. Russell Lyons and Yuval Peres. Probability on trees and networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, New York, 2016. URL: https://doi.org/10.1017/9781316672815.
  61. Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random spanning trees and the effective resistance metric. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 2019-2036. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.134.
  62. Francesco Manzo, Matteo Quattropani, and Elisabetta Scoppola. A probabilistic proof of Cooper & Frieze’s "First visit time lemma". ALEA Lat. Am. J. Probab. Math. Stat., 18(2):1739-1758, 2021. URL: https://doi.org/10.30757/alea.v18-64.
  63. Christine Marshall, Colm O’Riordan, and James Cruickshank. Targeting influential nodes for recovery in bootstrap percolation on hyperbolic networks. In European Network Intelligence Conference, pages 3-16. Springer, 2017. Google Scholar
  64. Tobias Müller and Merlijn Staps. The diameter of KPKVB random graphs. Adv. Appl. Probab., 51(2):358-377, 2019. URL: https://doi.org/10.1017/apr.2019.23.
  65. Takashi Owada and D Yogeshwaran. Sub-tree counts on hyperbolic random geometric graphs. To appear in Advances in Applied Probability, 2022+. Google Scholar
  66. José Luis Palacios. Closed-form formulas for Kirchhoff index. International J. of Quantum Chemistry, 81(2):135-140, 2001. Google Scholar
  67. Stacy Patterson and Bassam Bamieh. Consensus and coherence in fractal networks. IEEE Trans. Control. Netw. Syst., 1(4):338-348, 2014. URL: https://doi.org/10.1109/TCNS.2014.2357552.
  68. Thomas Sauerwald and He Sun. Tight bounds for randomized load balancing on arbitrary network topologies. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 341-350. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.86.
  69. Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput., 40(6):1913-1926, 2011. URL: https://doi.org/10.1137/080734029.
  70. John Sylvester. Random walk hitting times and effective resistance in sparsely connected Erdős-Rényi random graphs. J. Graph Theory, 96(1):44-84, 2021. URL: https://doi.org/10.1002/jgt.22551.
  71. Prasad Tetali. Random walks and the effective resistance of networks. J. Theor. Probab., 4(1):101-109, 1991. URL: https://doi.org/10.1007/BF01046996.
  72. Ulrike von Luxburg, Agnes Radl, and Matthias Hein. Hitting and commute times in large random neighborhood graphs. J. Mach. Learn. Res., 15(52):1751-1798, 2014. Google Scholar
  73. Felix Ming Fai Wong, Zhenming Liu, and Mung Chiang. On the efficiency of social recommender networks. IEEE/ACM Trans. Netw., 24(4):2512-2524, 2016. URL: https://doi.org/10.1109/TNET.2015.2475616.
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