Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-30T15:57:07.088Z Has data issue: false hasContentIssue false
  • English
  • Français

On local weak limit and subgraph counts for sparse random graphs

Part of: Combinatorial probability Graph theory

Published online by Cambridge University Press:  21 July 2022

Valentas Kurauskas
Valentas Kurauskas*
Affiliation:
Faculty of Mathematics and Informatics, Vilnius University
*
*Postal address: Akademijos 4, LT-08412 Vilnius, Lithuania. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We use an inequality of Sidorenko to show a general relation between local and global subgraph counts and degree moments for locally weakly convergent sequences of sparse random graphs. This yields an optimal criterion to check when the asymptotic behaviour of graph statistics, such as the clustering coefficient and assortativity, is determined by the local weak limit.

As an application we obtain new facts for several common models of sparse random intersection graphs where the local weak limit, as we see here, is a simple random clique tree corresponding to a certain two-type Galton–Watson branching process.

Keywords

Local weak limitsubgraph countclique treerandom intersection graph

MSC classification

Primary: 60C05: Combinatorial probability 05C80: Random graphs
Secondary: 05C82: Small world graphs, complex networks
Type
Original Article
Information
Journal of Applied Probability , Volume 59 , Issue 3 , September 2022 , pp. 755 - 776
Check for updates
Copyright
© The Author(s), 2022. 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

Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Prob. 12, 1454–1508.10.1214/EJP.v12-463CrossRefGoogle Scholar
Aldous, D. and Steele, J. M. (2004). The objective method: probabilistic combinatorial optimization and local weak convergence, In Probability on Discrete Structures (Encyclopaedia Math. Sci. 110), pp. 1–72. Springer, Berlin.Google Scholar
Andersson, H. (1998). Limit theorems for a random graph epidemic model. Ann. Appl. Prob. 8, 1331–1349.10.1214/aoap/1028903384CrossRefGoogle Scholar
Arratia, R., Goldstein, L. and Kochman, F. (2019). Size bias for one and all. Prob. Surv. 16, 1–61.10.1214/13-PS221CrossRefGoogle Scholar
Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Prob. 6, 1–13.10.1214/EJP.v6-96CrossRefGoogle Scholar
Benjamini, I., Lyons, R. and Schramm, O. (2013). Unimodular random trees. Ergodic Theory Dyn. Syst. 35, 1–15.Google Scholar
Berger, N., Borgs, C., Chayes, J. T. and Saberi, A. (2014). Asymptotic behavior and distributional limits of preferential attachment graphs. Ann. Prob. 42, 1–40.10.1214/12-AOP755CrossRefGoogle Scholar
Billingsley, P. (1971). Weak Convergence of Measures: Applications in Probability. Society for Industrial and Applied Mathematics, Philadelphia.10.1137/1.9781611970623CrossRefGoogle Scholar
Billingsley, P. (1999). Convergence of Probability Measures, 2nd edn. John Wiley, New York.10.1002/9780470316962CrossRefGoogle Scholar
Bloznelis, M. (2008). Degree distribution of a typical vertex in a general random intersection graph. Lith. Math. J. 48, 38–45.10.1007/s10986-008-0004-7CrossRefGoogle Scholar
Bloznelis, M. (2010). The largest component in an inhomogeneous random intersection graph with clustering. Electron. J. Combin. 17, R110.10.37236/382CrossRefGoogle Scholar
Bloznelis, M. (2013). Degree and clustering coefficient in sparse random intersection graphs. Ann. Appl. Prob. 23, 1254–1289.10.1214/12-AAP874CrossRefGoogle Scholar
Bloznelis, M. (2015). Degree-degree distribution in a power law random intersection graph with clustering. In Algorithms and Models for the Web Graph: 12th International Workshop (WAW 2015) (Lecture Notes Comput. Sci. 9479), eds D. F. Gleich et al., pp. 42–53. Springer.10.1007/978-3-319-26784-5_4CrossRefGoogle Scholar
Bloznelis, M. and Damarackas, J. (2013). Degree distribution of an inhomogeneous random intersection graph. Electron. J. Combin. 20, P3.10.37236/2786CrossRefGoogle Scholar
Bloznelis, M. and Kurauskas, V. (2017). Large cliques in sparse random intersection graphs. Electron. J. Combin. 24, P2.5.10.37236/6233CrossRefGoogle Scholar
Bloznelis, M., Jaworski, J., Godehardt, E., Kurauskas, V. and Rybarczyk, K. (2015). Recent progress in complex network analysis: models of random intersection graphs. In Data Science, Learning by Latent Structures and Knowledge Discovery (Studies in Classification, Data Analysis and Knowledge Organization), eds B. Lausen et al., pp. 69–78. Springer, Berlin and Heidelberg.10.1007/978-3-662-44983-7_6CrossRefGoogle Scholar
Bloznelis, M., Jaworski, J., Godehardt, E., Kurauskas, V. and Rybarczyk, K. (2015). Recent progress in complex network analysis: properties of random intersection graphs. In Data Science, Learning by Latent Structures and Knowledge Discovery (Studies in Classification, Data Analysis and Knowledge Organization), eds B. Lausen et al., pp. 79–88. Springer, Berlin and Heidelberg.10.1007/978-3-662-44983-7_7CrossRefGoogle Scholar
Bloznelis, M., Jaworski, J. and Kurauskas, V. (2013). Assortativity and clustering in sparse random intersection graphs. Electron. J. Prob. 18, 1–24.10.1214/EJP.v18-2277CrossRefGoogle Scholar
Bollobás, B. and Riordan, O. (2011). Sparse graphs: metrics and random models. Random Structures Algorithms 39, 1–38.10.1002/rsa.20334CrossRefGoogle Scholar
Bollobás, B. and Riordan, O. (2015). An old approach to the giant component problem. J. Combinatorial Theory B 113, 236–260.10.1016/j.jctb.2015.03.002CrossRefGoogle Scholar
Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31, 3–122.10.1002/rsa.20168CrossRefGoogle Scholar
Bollobás, B., Janson, S. and Riordan, O. (2011). Sparse random graphs with clustering. Random Structures Algorithms 38 269–323.10.1002/rsa.20322CrossRefGoogle Scholar
Bordenave, C. and Lelarge, M. (2010). Resolvent of large random graphs. Random Structures Algorithms 37, 332–352.10.1002/rsa.20313CrossRefGoogle Scholar
Csikvári, P. and Zhicong, L. (2014). Graph homomorphisms between trees. Electron. J. Prob. 21, P4.9.10.37236/4096CrossRefGoogle Scholar
Dembo, A. and Montanari, A. (2010). Gibbs measures and phase transitions on sparse random graphs. Braz. J. Prob. Stat. 24, 137–211.10.1214/09-BJPS027CrossRefGoogle Scholar
Durrett, R. (2010). Probability: Theory and Examples, 4th edn. Cambridge University Press.10.1017/CBO9780511779398CrossRefGoogle Scholar
Fiol, M. A. and Garriga, E. (2009). Number of walks and degree powers in a graph. Discrete Math. 309, 2613–2614.10.1016/j.disc.2008.03.025CrossRefGoogle Scholar
Gamarnik, D. and Misra, S. (2015). Giant component in multipartite graphs with given degree sequences. Stoch. Syst. 5, 372–408.10.1287/13-SSY135CrossRefGoogle Scholar
Georgakopoulos, A. and Wagner, S. (2016). Limits of subcritical random graphs and random graphs with excluded minors. Available at arXiv:1512.03572.Google Scholar
Godehardt, E., Jaworski, J. and Rybarczyk, K. (2012). Clustering coefficients of random intersection graphs. In Challenges at the Interface of Data Analysis, Computer Science and Optimization, eds W. Gaul et al., pp. 243–253. Springer, Berlin.10.1007/978-3-642-24466-7_25CrossRefGoogle Scholar
Grimmett, G. and Stirzaker, D. (2001). Probability and Random Processes. Oxford University Press.Google Scholar
Guillaume, J.-L. and Latapy, M. (2006). Bipartite graphs as models of complex networks. Physica A 371, 795–813.10.1016/j.physa.2006.04.047CrossRefGoogle Scholar
van der Hofstad, R. (2020+). Random Graphs and Complex Networks, Vol. II, preliminary version. https://www.win.tue.nl/~rhofstad/NotesRGCNII_colleagues_25_04_2022.pdf, accessed 2022-06-09.Google Scholar
Janson, S. and Luczak, M. J. (2009). A new approach to the giant component problem. Random Structures Algorithms 34, 197–216.10.1002/rsa.20231CrossRefGoogle Scholar
Litvak, N. and van der Hofstad, R. (2013). Uncovering disassortativity in large scale-free networks. Phys. Rev. E 87, 022801.10.1103/PhysRevE.87.022801CrossRefGoogle ScholarPubMed
Lovász, L. (2012). Large Networks And Graph Limits (American Mathematical Society Colloquium Publications 60). American Mathematical Society, Providence, RI.Google Scholar
Lyons, R. (2005). Asymptotic enumeration of spanning trees. Combinatorics Prob. Comput. 14, 491–522.10.1017/S096354830500684XCrossRefGoogle Scholar
Karoński, M., Scheinerman, E. R. and Singer-Cohen, K. B. (1999). On random intersection graphs: the subgraph problem. Combinatorics Prob. Comput. 8, 131–159.10.1017/S0963548398003459CrossRefGoogle Scholar
Karrer, B. and Newman, M. E. J. (2010). Random graphs containing arbitrary distributions of subgraphs. Phys. Rev. E 82, 066118.10.1103/PhysRevE.82.066118CrossRefGoogle ScholarPubMed
Kurauskas, V. (2015). On local weak limit and subgraph counts for sparse random graphs. Available at arXiv:1504.08103.Google Scholar
Newman, M. E. J., Strogatz, S. H. and Watts, D. J. (2001). Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118.10.1103/PhysRevE.64.026118CrossRefGoogle ScholarPubMed
Panagiotou, K., Stufler, B. and Weller, K. (2016). Scaling limits of random graphs from subcritical classes. Ann. Prob. 44, 3291–3334.10.1214/15-AOP1048CrossRefGoogle Scholar
Richardson, T. and Urbanke, R. (2008). Modern Coding Theory. Cambridge University Press.10.1017/CBO9780511791338CrossRefGoogle Scholar
Salez, J. (2011). Some implications of local weak convergence for sparse random graphs. Doctoral thesis, Université Pierre et Marie Curie – Paris VI, Ecole Normale Supérieure de Paris – ENS Paris.Google Scholar
Sidorenko, A. (1994). A partially ordered set of functionals corresponding to graphs. Discrete Math. 131, 263–277.10.1016/0012-365X(94)90388-3CrossRefGoogle Scholar
Stufler, B. (2021). Local convergence of random planar graphs. In Extended Abstracts EuroComb 2021 (Trends in Mathematics 14), eds J. Nešetřil et al. Birkhäuser, Cham.10.1007/978-3-030-83823-2_10CrossRefGoogle Scholar
Vadon, V., Komjáthy, J. and van der Hofstad, R. (2019). A new model for overlapping communities with arbitrary internal structure. Applied Network Science 4, 1–19.10.1007/s41109-019-0149-9CrossRefGoogle Scholar
Wormald, N. C. (1999). Models of random regular graphs. In Surveys in Combinatorics 1999 (Canterbury) (London Math. Soc. Lecture Notes 267), pp. 239–298. Cambridge University Press.10.1017/CBO9780511721335.010CrossRefGoogle Scholar