Hostname: page-component-6bf8c574d5-zc66z Total loading time: 0 Render date: 2025-03-11T17:26:50.112Z Has data issue: false hasContentIssue false
  • English
  • Français

The asymptotics of the expected Betti numbers of preferential attachment clique complexes

Part of: Combinatorial probability Applied homological algebra and category theory Algebraic combinatorics Graph theory

Published online by Cambridge University Press:  10 March 2025

Chunyin Siu ,
Gennady Samorodnitsky ,
Christina Lee Yu  and
Rongyi He
Chunyin Siu*
Affiliation:
Cornell University and Stanford University
Gennady Samorodnitsky*
Affiliation:
Cornell University
Christina Lee Yu*
Affiliation:
Cornell University
Rongyi He*
Affiliation:
Cornell University
*
*Postal address: The Center for Applied Mathematics, 657 Rhodes Hall, Cornell University, Ithaca, NY 14853, USA.
*Postal address: The Center for Applied Mathematics, 657 Rhodes Hall, Cornell University, Ithaca, NY 14853, USA.
*Postal address: The Center for Applied Mathematics, 657 Rhodes Hall, Cornell University, Ithaca, NY 14853, USA.
*Postal address: The Center for Applied Mathematics, 657 Rhodes Hall, Cornell University, Ithaca, NY 14853, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

The preferential attachment model is a natural and popular random graph model for a growing network that contains very well-connected ‘hubs’. We study the higher-order connectivity of such a network by investigating the topological properties of its clique complex. We concentrate on the Betti numbers, a sequence of topological invariants of the complex related to the numbers of holes (equivalently, repeated connections) of different dimensions. We prove that the expected Betti numbers grow sublinearly fast, with the trivial exceptions of those at dimensions 0 and 1. Our result also shows that preferential attachment graphs undergo infinitely many phase transitions within the parameter regime where the limiting degree distribution has an infinite variance. Regarding higher-order connectivity, our result shows that preferential attachment favors higher-order connectivity. We illustrate our theoretical results with simulations.

Keywords

Topological data analysiscomplex networkphase transition

MSC classification

Primary: 05C82: Small world graphs, complex networks 60C05: Combinatorial probability 05E45: Combinatorial aspects of simplicial complexes
Secondary: 55U10: Simplicial sets and complexes
Type
Original Article
Information
Advances in Applied Probability , First View , pp. 1 - 29
Check for updates
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of Applied Probability Trust

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

Aktas, M. E., Akbas, E. and Fatmaoui, A. E. (2019). Persistence homology of networks: methods and applications. Appl. Network Sci. 4, article no. 61.CrossRefGoogle Scholar
Albert, R. (2005). Scale-free networks in cell biology. J. Cell Sci. 118, 4947–4957.CrossRefGoogle ScholarPubMed
Ayzenberg, A. and Rukhovich, A. (2020). Clique complexes of multigraphs, edge inflations, and tournaplexes. Preprint. Available at https://arxiv.org/abs/2012.07600.Google Scholar
Bauer, U. (2021). Ripser: efficient computation of Vietoris–Rips persistence barcodes. J. Appl. Comput. Topol. 5, 391–423.CrossRefGoogle Scholar
Bianconi, G. and Rahmede, C. (2016). Network geometry with flavor: from complexity to quantum geometry. Phys. Rev. E 93, article no. 032315.CrossRefGoogle ScholarPubMed
Bobrowski, O. and Kahle, M. (2018). Topology of random geometric complexes: a survey. J. Appl. Comput. Topol. 1, 331–364.CrossRefGoogle Scholar
Bobrowski, O. and Krioukov, D. (2022). Random simplicial complexes: models and phenomena. In Higher-Order Systems, Springer, Cham, pp. 59–96.CrossRefGoogle Scholar
Bollobás, B. and Riordan, O. M. (2003). Mathematical results on scale-free random graphs. In Handbook of Graphs and Networks: From the Genome to the Internet, Wiley-VCH, Weinheim, pp. 1–34.Google Scholar
Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18, 279–290.CrossRefGoogle Scholar
Carlsson, G. (2009). Topology and data. Bull. Amer. Math. Soc. 46, 255–308.CrossRefGoogle Scholar
Chazal, F. and Michel, B. (2021). An introduction to topological data analysis: fundamental and practical aspects for data scientists. Frontiers Artificial Intellig. 4, article no. 667963.CrossRefGoogle ScholarPubMed
Courtney, O. T. and Bianconi, G. (2017). Weighted growing simplicial complexes. Phys. Rev. E 95, article no. 062301.CrossRefGoogle ScholarPubMed
Csardi, G. and Nepusz, T. (2006). The igraph software package for complex network research. InterJournal 1695, 1–9.Google Scholar
Duncan, P., Kahle, M. and Schweinhart, B. (2023). Homological percolation on a torus: plaquettes and permutohedra. Preprint. Available at https://arxiv.org/abs/2011.11903.Google Scholar
Eggemann, N. and Noble, S. (2011). The clustering coefficient of a scale-free random graph. Discrete Appl. Math. 159, 953–965.CrossRefGoogle Scholar
Erdös, P. and Rényi, A. (1959). On random graphs I. Publ. Math. Debrecen 6, 290–297.CrossRefGoogle Scholar
Forman, R. (2002). A user’s guide to discrete Morse theory. Sém. Lotharingien Combinatoire 48, article no. B48c.Google Scholar
Gal, S. R. (2005). Real root conjecture fails for five- and higher-dimensional spheres. Discrete Comput. Geom. 34, 269–284.CrossRefGoogle Scholar
Garavaglia, A. (2019). Preferential attachment models for dynamic networks. Doctoral Thesis, Technische Universiteit Eindhoven.Google Scholar
Garavaglia, A. and Stegehuis, C. (2019). Subgraphs in preferential attachment models. Adv. Appl. Prob. 51, 898–926.CrossRefGoogle Scholar
Giblin, P. (2010). Graphs, Surfaces and Homology, 3rd edn. Cambridge University Press.CrossRefGoogle Scholar
Harris, C. R. et al. (2020). Array programming with NumPy. Nature 585, 357–362.CrossRefGoogle ScholarPubMed
Hatcher, A. (2002). Algebraic Topology. Cambridge University Press.Google Scholar
Hirsch, C. and Juhasz, P. (2023). On the topology of higher-order age-dependent random connection models. Preprint. Available at https://arxiv.org/abs/2309.11407.Google Scholar
Holme, P. and Kim, B. J. (2002). Growing scale-free networks with tunable clustering. Phys. Rev. E 65, article no. 026107.CrossRefGoogle ScholarPubMed
Hunter, J. D. (2007). Matplotlib: a 2D graphics environment. Comput. Sci. Eng. 9, 90–95.CrossRefGoogle Scholar
Kahle, M. (2009). Topology of random clique complexes. Discrete Math. 309, 1658–1671.CrossRefGoogle Scholar
Kahle, M. (2011). Random geometric complexes. Discrete Comput. Geom. 45, 553–573.CrossRefGoogle Scholar
Kahle, M. (2014a). Sharp vanishing thresholds for cohomology of random flag complexes. Ann. Math. 179, 1085–1107.CrossRefGoogle Scholar
Kahle, M. (2014b). Topology of random simplicial complexes: a survey. In Algebraic Topology: Applications and New Directions, American Mathematical Society, Providence, RI, pp. 201–222.Google Scholar
Kahle, M. and Meckes, E. (2013). Limit theorems for Betti numbers of random simplicial complexes. Homology Homotopy Appl. 15, 343–374.CrossRefGoogle Scholar
Lam, S. K., Pitrou, A, and Seibert, S. (2015). Numba: a LLVM-based Python JIT compiler. In LLVM ’15: Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, Association for Computing Machinery, New York, article no. 7, 6 pp.Google Scholar
Móri, T. (2002). On random trees. Studia Sci. Math. Hung. 39, 143–155.Google Scholar
Munkres, J. R. (1984). Elements of Algebraic Topology. Benjamin/Cummings, Menlo Park, CA.Google Scholar
Oh, S. M., Lee, Y., Lee, J. and Kahng, B. (2021). Emergence of Betti numbers in growing simplicial complexes: analytical solutions. J. Statist. Mech. 2021, article no. 083218.CrossRefGoogle Scholar
Ostroumova, L., Ryabchenko, A. and Samosvat, E. (2013). Generalized preferential attachment: tunable power-law degree distribution and clustering coefficient. In Algorithms and Models for the Web Graph, eds Bonato, A., Mitzenmacher, M., and P. Praat, Springer, Cham, pp. 185–202.CrossRefGoogle Scholar
Ostroumova Prokhorenkova, L. (2017). General results on preferential attachment and clustering coefficient. Optimization Lett. 11, 279–298.CrossRefGoogle Scholar
Penrose, M. (2003). Random Geometric Graphs. Oxford University Press.CrossRefGoogle Scholar
Reimann, M. W. et al. (2017). Cliques of neurons bound into cavities provide a missing link between structure and function. Frontiers Comput. Neurosci. 11, article no. 48.CrossRefGoogle ScholarPubMed
Rotman, J. (2008). An Introduction to Homological Algebra. Springer, New York.Google Scholar
Siu, C. (2024). The topological behavior of preferential attachment graphs. Preprint. Available at https://arxiv.org/abs/2406.17619.Google Scholar
Tralie, C., Saul, N. and Bar-On, R. (2018). Ripser.py: a lean persistent homology library for python. J. Open Source Software 3, article no. 925.Google Scholar
Van der Hofstad, R. (2016). Random Graphs and Complex Networks, Vol. 1. Cambridge University Press.CrossRefGoogle Scholar
Van der Hofstad, R. (2024a). Random Graphs and Complex Networks, Vol. 2. Cambridge University Press.CrossRefGoogle Scholar
Van der Hofstad, R. (2024b). Corrigenda Random Graphs and Complex Networks Volume Two. Available at https://www.win.tue.nl/rhofstad/CorrigendaNotesRGCNII.pdf.CrossRefGoogle Scholar
Virtanen, P. et al. (2020). SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Meth. 17, 261–272.CrossRefGoogle Scholar
Yogeshwaran, D. and Adler, R. J. (2015). On the topology of random complexes built over stationary point processes. Ann. Appl. Prob. 25, 3338–3380.CrossRefGoogle Scholar