Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-05T06:40:46.675Z Has data issue: false hasContentIssue false
  • English
  • Français

On the evolution of topology in dynamic clique complexes

Part of: Combinatorial probability Probability theory on algebraic and topological structures Applied homological algebra and category theory Graph 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.
Get access Rights & Permissions [Opens in a new window]

Abstract

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, which evolve independently as continuous-time Markov chains. Our main result is that when the edge inclusion 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 converges weakly 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 probability 55U10: Simplicial sets and complexes 60B10: Convergence of probability measures
Type
Research Article
Information
Advances in Applied Probability , Volume 48 , Issue 4 , December 2016 , pp. 989 - 1014
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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