Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-30T16:54:00.822Z Has data issue: false hasContentIssue false
  • English
  • Français

Random intersection graphs with communities

Part of: Combinatorial probability Graph theory Operations research and management science

Published online by Cambridge University Press:  22 November 2021

Remco van der Hofstad Open the ORCID record for Remco van der Hofstad [Opens in a new window] ,
Júlia Komjáthy Open the ORCID record for Júlia Komjáthy [Opens in a new window]  and
Viktória Vadon
Remco van der Hofstad*
Affiliation:
Eindhoven University of Technology
Júlia Komjáthy*
Affiliation:
Delft University of Technology
Viktória Vadon*
Affiliation:
University of Miskolc
*
*Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB, Eindhoven, The Netherlands. Email address: [email protected]
**Postal address: Department of Applied Mathematics, Delft University of Technology, Postbus 5, 2600AA, Delft, The Netherlands. Email address: [email protected]
***Postal address: Institute of Mathematics, University of Miskolc, Egyetem ut 1, 3515, Miskolc, Hungary. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Random intersection graphs model networks with communities, assuming an underlying bipartite structure of communities and individuals, where these communities may overlap. We generalize the model, allowing for arbitrary community structures within the communities. In our new model, communities may overlap, and they have their own internal structure described by arbitrary finite community graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, show local weak convergence (including convergence of subgraph counts), and derive the asymptotic degree distribution and the local clustering coefficient.

Keywords

Random networkscommunity structureoverlapping communitiesrandom intersection graphslocal weak convergence

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05C80: Random graphs 90B15: Network models, stochastic
Type
Original Article
Information
Advances in Applied Probability , Volume 53 , Issue 4 , December 2021 , pp. 1061 - 1089
Check for updates
Copyright
© The Author(s) 2021. 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 Steele, J. M. (2004). The objective method: probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures (Encyclopaedia Math. Sci., Vol. 110), Springer, Berlin, pp. 1–72.CrossRefGoogle Scholar
Ball, F., Sirl, D. and Trapman, P. (2009). Threshold behaviour and final outcome of an epidemic on a random network with household structure. Adv. Appl. Prob. 41, 765–796.CrossRefGoogle Scholar
Ball, F., Sirl, D. and Trapman, P. (2010). Analysis of a stochastic SIR epidemic on a random network incorporating household structure. Math. Biosci. 224, 53–73.CrossRefGoogle ScholarPubMed
Benjamini, I., Lyons, R. and Schramm, O. (2015). Unimodular random trees. Ergod. Theory Dynam. Systems 35, 359–373.10.1017/etds.2013.56CrossRefGoogle Scholar
Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Prob. 6, paper no. 23, 13 pp.CrossRefGoogle 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.CrossRefGoogle Scholar
Blackburn, S. R. and Gerke, S. (2009). Connectivity of the uniform random intersection graph. Discrete Math. 309, 5130–5140.10.1016/j.disc.2009.03.042CrossRefGoogle Scholar
Bloznelis, M. (2010). Component evolution in general random intersection graphs. SIAM J. Discrete Math. 24, 639–654.10.1137/080713756CrossRefGoogle Scholar
Bloznelis, M. (2013). Degree and clustering coefficient in sparse random intersection graphs. Ann. Appl. Prob. 23, 1254–1289.CrossRefGoogle Scholar
Bloznelis, M. (2017). Degree–degree distribution in a power law random intersection graph with clustering. Internet Math. Available at https://doi.org/10.24166/im.03.2017.Google Scholar
Bloznelis, M. and Damarackas, J. (2013). Degree distribution of an inhomogeneous random intersection graph. Electron. J. Combinatorics 20, paper no. 3, 13 pp.CrossRefGoogle Scholar
Bloznelis, M. et al. (2015). Recent progress in complex network analysis: properties of random intersection graphs. In Data Science, Learning by Latent Structures, and Knowledge Discovery, Springer, Heidelberg, pp. 79–88.10.1007/978-3-662-44983-7_7CrossRefGoogle Scholar
Bloznelis, M., Jaworski, J. and Kurauskas, V. (2013). Assortativity and clustering of sparse random intersection graphs. Electron. J. Prob. 18, paper no. 38, 24 pp.CrossRefGoogle Scholar
Bollobás, B. (2001). Random Graphs, 2nd edn. Cambridge University Press.CrossRefGoogle Scholar
Britton, T., Deijfen, M. and Martin-Löf, A. (2006). Generating simple random graphs with prescribed degree distribution. J. Statist. Phys. 124, 1377–1397.10.1007/s10955-006-9168-xCrossRefGoogle Scholar
Chen, N. and Olvera-Cravioto, M. (2013). Directed random graphs with given degree distributions. Stoch. Systems 3, 147–186.CrossRefGoogle Scholar
Coupechoux, E. and Lelarge, M. (2015). Contagions in random networks with overlapping communities. Adv. Appl. Prob. 47, 973–988.CrossRefGoogle Scholar
Deijfen, M. and Kets, W. (2009). Random intersection graphs with tunable degree distribution and clustering. Prob. Eng. Inf. Sci. 23, 661–674.CrossRefGoogle Scholar
Derényi, I., Palla, G. and Vicsek, T. (2005). Clique percolation in random networks. Phys. Rev. Lett. 94, 160202.10.1103/PhysRevLett.94.160202CrossRefGoogle ScholarPubMed
Durrett, R. (2007). Random Graph Dynamics. Cambridge University Press.Google Scholar
Fill, J. A., Scheinerman, E. R. and Singer-Cohen, K. B. (2000). Random intersection graphs when $m=\omega(n)$ : an equivalence theorem relating the evolution of the G(n,m,p) and G(n,p) models. Random Structures Algorithms 16, 156–176.3.0.CO;2-H>CrossRefGoogle Scholar
Fortunato, S. (2010). Community detection in graphs. Phys. Rep. 486, 75–174.CrossRefGoogle Scholar
Fortunato, S. and Hric, D. (2016). Community detection in networks: a user guide. Phys. Rep. 659, 1–44.CrossRefGoogle Scholar
Garavaglia, A., van der Hofstad, R. and Litvak, N. (2020). Local weak convergence for PageRank. Ann. Appl. Prob. 30, 40–79.CrossRefGoogle Scholar
Girvan, M. and Newman, M. E. J. (2002). Community structure in social and biological networks. Proc. Nat. Acad. Sci. USA 99, 7821–7826.CrossRefGoogle Scholar
Godehardt, E. and Jaworski, J. (2003). Two models of random intersection graphs for classification. In Exploratory Data Analysis in Empirical Research, Springer, Berlin, Heidelberg, pp. 67–81.CrossRefGoogle Scholar
Guillaume, J.-L. and Latapy, M. (2004). Bipartite structure of all complex networks. Inf. Process. Lett. 90, 215–221.CrossRefGoogle Scholar
Guillaume, J.-L. and Latapy, M. (2006). Bipartite graphs as models of complex networks. Physica A 371, 795–813.CrossRefGoogle Scholar
Van der Hofstad, R. (2017). Random Graphs and Complex Networks, Vol. 1. Cambridge University Press.CrossRefGoogle Scholar
Van der Hofstad, R. (2020+). Random Graphs and Complex Networks, Vol. 2. In preparation. Available at http://www.win.tue.nl/rhofstad/NotesRGCNII.pdf. 16 November 2020 version referenced.Google Scholar
Van der Hofstad, R., Komjáthy, J. and Vadon, V. (2018). Random intersection graphs with communities, extended version. Preprint. Available at https://arxiv.org/abs/1809.02514.Google Scholar
Van der Hofstad, R., Komjáthy, J. and Vadon, V. (2019). Phase transition in random intersection graphs with communities. Preprint. Available at https://arxiv.org/abs/1905.06253.Google Scholar
Van der Hofstad, R., van Leeuwaarden, J. S. H. and Stegehuis, C. (2016). Hierarchical configuration model. Internet Math. Available at https://doi.org/10.24166/im.01.2017.Google Scholar
Van der Hofstad, R., van Leeuwaarden, J. S. H. and Stegehuis, C. (2016). Power-law relations in random networks with communities. Phys. Rev. E 94, 012302.Google Scholar
Janson, S., Łuczak, T. and Ruciński, A. (2000). Random Graphs. John Wiley, New York.CrossRefGoogle Scholar
Karjalainen, J., van Leeuwaarden, J. S. H. and Leskelä, L. (2018). Parameter estimators of sparse random intersection graphs with thinned communities. In International Workshop on Algorithms and Models for the Web-Graph (WAW 2018), Springer, Cham, pp. 44–58.CrossRefGoogle Scholar
Karonski, M., Scheinerman, E. R. and Singer-Cohen, K. B. (1999). On random intersection graphs: the subgraph problem. Combinatorics Prob. Comput. 8, 131–159.CrossRefGoogle Scholar
Kurauskas, V. (2015). On local weak limit and subgraph counts for sparse random graphs. Preprint. Available at https://arxiv.org/abs/1504.08103.Google Scholar
Newman, M. E. J. (2003). Properties of highly clustered networks. Phys. Rev. E 68, 026121.10.1103/PhysRevE.68.026121CrossRefGoogle ScholarPubMed
Newman, M. E. J. (2010). Networks. Oxford University Press.CrossRefGoogle Scholar
Norros, I. and Reittu, H. (2006). On a conditionally Poissonian graph process. Adv. Appl. Prob. 38, 59–75.CrossRefGoogle Scholar
Palla, G., Derényi, I., Farkas, I. and Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818.CrossRefGoogle ScholarPubMed
Rybarczyk, K. (2011). Diameter, connectivity, and phase transition of the uniform random intersection graph. Discrete Math. 311, 1998–2019.CrossRefGoogle Scholar
Singer, K. B. (1996). Random intersection graphs. Doctoral Thesis, Johns Hopkins University.Google Scholar
Vadon, V., Komjáthy, J. and van der Hofstad, R. (2019). A new model for overlapping communities with arbitrary internal structure. Appl. Network Sci. 4, article no. 42.CrossRefGoogle Scholar