Hostname: page-component-6898cfcb55-zsp5v Total loading time: 0 Render date: 2026-11-11T15:38:02.661Z Has data issue: false hasContentIssue false
  • English
  • Français

On the evolution of topology in dynamic clique complexes

Part of:Probability theory on algebraic and topological structuresCombinatorial probabilityApplied homological algebra and category theoryGraph theory

Published online by Cambridge University Press:  11 January 2017

Gugan C. Thoppe,
D. Yogeshwaran and
Robert J. Adler
Gugan C. Thoppe*
Affiliation:
Technion – Israel Institute of Technology
D. Yogeshwaran*
Affiliation:
Indian Statistical Institute
Robert J. Adler*
Affiliation:
Technion – Israel Institute of Technology
*
* Postal address: Faculty of Electrical Engineering, Technion, Haifa, 32000, Israel.
*** Postal address: Statistics and Mathematics Unit, Indian Statistical Institute, Bangalore, 560059, India.
* Postal address: Faculty of Electrical Engineering, Technion, Haifa, 32000, Israel.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider a time varying analogue of the Erdős–Rényi graph and study the topological variations of its associated clique complex. The dynamics of the graph are stationary and are determined by the edges, whichevolve independently as continuous-time Markov chains. Our main result is that when the edgeinclusion probability is of the form p=n α, where n is the number of vertices and α∈(-1/k, -1/(k + 1)), then the process of the normalised kth Betti number of these dynamic clique complexes convergesweakly to the Ornstein–Uhlenbeck process as n→∞.

Keywords

Dynamic Erdős–Rényi graphBetti numbersOrnstein–Uhlenbeck

MSC classification

Primary:05C80: Random graphs
Secondary:60C05: Combinatorial probability55U10: Simplicial sets and complexes60B10: Convergence of probability measures

Information

Type
Research Article
Information
Advances in Applied Probability , Volume 48 , Issue 4 , December 2016, pp. 989 - 1014
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Babson, E., Hoffman, C. and Kahle, M. (2011). The fundamental group of random 2-complexes. J.~Amer. Math. Soc. 24, 1–28.Google Scholar
[2] Barbour, A. D., Karoński, M.and Ruciński, A. (1989). A central limit theorem for decomposable random variables with applications to random graphs. J.~Combin. Theory B 47, 125–145.Google Scholar
[3] Basu, P., Bar-Noy, A., Ramanathan, R. and Johnson, M. P. (2010). Modeling and analysis of time-varying graphs. Preprint. Available at http://arxiv.org/abs/1012.0260.Google Scholar
[4] Billingsley, P. (2012). Probability and Measure. John Wiley, Hoboken, NJ.Google Scholar
[5] Burke, C. J. and Rosenblatt, M. (1958). A Markovian function of a Markov chain. Ann. Math. Statist. 29, 1112–1122.Google Scholar
[6] Clementi, A. E. F. (2010). Flooding time of edge-Markovian evolving graphs. SIAM J. Discrete Math. 24, 1694–1712.Google Scholar
[7] Clementi, A. et al. (2015). Distributed community detection in dynamic graphs. Theoret. Comput. Sci. 584, 19–41.Google Scholar
[8] Edelsbrunner, H. and Harer, J. L. (2010). Computational Topology: An Introduction, American Mathematical Society, Providence, RI.Google Scholar
[9] Erdős, P. and Rényi, A. (1959). On random graphs. I. Publ. Math. Debrecen 6, 290–297.CrossRefGoogle Scholar
[10] Ethier, S. N. and Kurtz, T. G. (2005). Markov Processes: Characterization and Convergence. John Wiley, Hoboken, NJ.Google Scholar
[11] Gut, A. (YEAR). An Intermediate Course in Probability, 2nd edn. Springer, New York.Google Scholar
[12] Hatcher, A. (2002). Algebraic Topology. Cambridge University Press.Google Scholar
[13] Kahle, M. (2007). The neighborhood complex of a random graph. J. Combin. Theory A 114, 380–387.Google Scholar
[14] Kahle, M. (2009). Topology of random clique complexes. Discrete Math. 309, 1658–1671.Google Scholar
[15] Kahle, M. (2011). Random geometric complexes. Discrete Comput. Geometry 45, 553–573.CrossRefGoogle Scholar
[16] Kahle, M. (2014). Sharp vanishing thresholds for cohomology of random flag complexes. Ann. Math. (2) 179, 1085–1107.Google Scholar
[17] Kahle, M. (2014). Topology of random simplicial complexes: a survey. In Algebraic Topology: Applications and New Directions, (Contemp. Math. 620), American Mathematical Society, Providence, RI, pp.201–221.Google Scholar
[18] Kahle, M. and Meckes, E. (2013). Limit theorems for Betti numbers of random simplicial complexes. Homology Homotopy Appl. 15, 343–374. (Erratum: 18 (2016), 129–142.)CrossRefGoogle Scholar
[19] Linial, N. and Meshulam, R. (2006). Homological connectivity of random 2-complexes. Combinatorica 26, 475–487.Google Scholar
[20] Meshulam, R. and Wallach, N. (2009). Homological connectivity of random k-dimensional complexes. Random Structures Algorithms 34, 408–417.CrossRefGoogle Scholar
[21] Musolesi, M., Hailes, S. and Mascolo, C. (2005). Adaptive routing for intermittently connected mobile ad hoc networks. In Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks, IEEE, New York, pp.183–189.CrossRefGoogle Scholar
[22] Spyropoulos, T., Psounis, K. and Raghavendra, C. S. (2005). Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In WDTN `OS Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking, ACM, New York, pp.252–259.Google Scholar
[23] Yogeshwaran, D., Subag, E. and Adler, R. J. (2016). Random geometric complexes in the thermodynamic regime. To appear in Prob. Theory Relat. Fields Google Scholar