Assortativity and clustering of sparse random intersection graphs

Mindaugas Bloznelis (Vilnius University)
Jerzy Jaworski (Adam Mickiewicz University)
Valentas Kurauskas (Vilnius University)

Abstract


We consider sparse random intersection graphs with the property that the clustering coefficient does not vanish as the number of nodes tends to infinity. We find explicit asymptotic expressions for  the correlation coefficient of degrees of adjacent nodes (called the assortativity coefficient), the expected number of common neighbours of adjacent nodes, and  the expected degree of a neighbour of a node of a given degree k. These expressions are written in terms of the asymptotic degree distribution and, alternatively, in terms of the parameters defining the underlying random graph model.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-24

Publication Date: March 13, 2013

DOI: 10.1214/EJP.v18-2277

References

  • Barbour, A. D.; Reinert, G. The shortest distance in random multi-type intersection graphs. Random Structures Algorithms 39 (2011), no. 2, 179--209. MR2850268
  • Barrat, A.; Weigt, M. On the properties of small-world networks, The European Physical Journal B~ 13 (2000), 547--560.
  • Behrisch, Michael. Component evolution in random intersection graphs. Electron. J. Combin. 14 (2007), no. 1, Research Paper 17, 12 MR2285821
  • Blackburn, Simon R.; Gerke, Stefanie. Connectivity of the uniform random intersection graph. Discrete Math. 309 (2009), no. 16, 5130--5140. MR2548914
  • Bloznelis, M. Degree distribution of a typical vertex in a general random intersection graph. Lith. Math. J. 48 (2008), no. 1, 38--45. MR2398169
  • Bloznelis, M. Degree and clustering coefficient in sparse random intersection graphs, to appear in Annals of Applied Probability.
  • Britton, Tom; Deijfen, Maria; Lagerås, Andreas N.; Lindholm, Mathias. Epidemics on random graphs with tunable clustering. J. Appl. Probab. 45 (2008), no. 3, 743--756. MR2455182
  • Deijfen, Maria; Kets, Willemien. Random intersection graphs with tunable degree distribution and clustering. Probab. Engrg. Inform. Sci. 23 (2009), no. 4, 661--674. MR2535025
  • Eschenauer, L.; Gligor, V. D. A key-management scheme for distributed sensor networks, in: Proceedings of the 9th ACM Conference on Computer and Communications Security (2002), 41--47.
  • Godehardt, Erhard; Jaworski, Jerzy. Two models of random intersection graphs and their applications. Comb01—Euroconference on Combinatorics, Graph Theory and Applications, 4 pp. (electronic), Electron. Notes Discrete Math., 10, Elsevier, Amsterdam, 2001. MR2154493
  • Godehardt, E.; Jaworski, J. Two models of random intersection graphs for classification. Exploratory data analysis in empirical research, 67--81, Stud. Classification Data Anal. Knowledge Organ., Springer, Berlin, 2003. MR2074223
  • Godehardt, E.; Jaworski, J.; Rybarczyk, K. Clustering coefficients of random intersection graphs, in: Studies in Classification, Data Analysis and Knowledge Organization, Springer, Berlin--Heidelberg--New York, 2012, 243--253.
  • Guillaume, Jean-Loup; Latapy, Matthieu. Bipartite structure of all complex networks. Inform. Process. Lett. 90 (2004), no. 5, 215--221. MR2054656
  • Jaworski, Jerzy; Stark, Dudley. The vertex degree distribution of passive random intersection graph models. Combin. Probab. Comput. 17 (2008), no. 4, 549--558. MR2433940
  • Karoński, Michał; Scheinerman, Edward R.; Singer-Cohen, Karen B. On random intersection graphs: the subgraph problem. Recent trends in combinatorics (Mátraháza, 1995). Combin. Probab. Comput. 8 (1999), no. 1-2, 131--159. MR1684626
  • Sang Hoon Lee, Pan-Jun Kim and Hawoong Jeong, Statistical properties of sampled networks, Physical Review E~ 73 (2006), 016102.
  • Newman, M. E. J.; Strogatz S. H.; Watts, D. J. Random graphs with arbitrary degree distributions and their applications, Physical Review E~ 64 (2001), 026118.
  • Newman, M. E. J. Assortative Mixing in Networks, Physical Review Letters~ 89 (2002), 208701.
  • Newman, M. E. J. Mixing patterns in networks. Phys. Rev. E (3) 67 (2003), no. 2, 026126, 13 MR1975193
  • Newman, M. E. J. Properties of highly clustered networks, Physical Review E~ 68 (2003), 026121.
  • Newman, M. E. J.; Watts, D. J.; Strogatz, S. H. Random graph models of social networks, Proc. Natl. Acad. Sci. USA~ 99 (Suppl. 1) (2002), 2566--2572.
  • Nikoletseas, S.; Raptopoulos, C.; Spirakis, P. G. On the independence number and Hamiltonicity of uniform random intersection graphs. Theoret. Comput. Sci. 412 (2011), no. 48, 6750--6760. MR2885093
  • Pastor-Satorras, R.; Vázquez, A.; Vespignani, A. Dynamical and correlation properties of the internet, Phys. Rev. Lett.~ 87 (2001), 258701.
  • Rybarczyk, Katarzyna. Diameter, connectivity, and phase transition of the uniform random intersection graph. Discrete Math. 311 (2011), no. 17, 1998--2019. MR2818878
  • Stark, Dudley. The vertex degree distribution of random intersection graphs. Random Structures Algorithms 24 (2004), no. 3, 249--258. MR2068868
  • Steele, J. Michael. Le Cam's inequality and Poisson approximations. Amer. Math. Monthly 101 (1994), no. 1, 48--54. MR1252705
  • Strogatz, S. H.; Watts, D. J. Collective dynamics of small-world networks, Nature~ 393 (1998), 440--442.
  • Yagan, O.; Makowski, A. M. Zero-one laws for connectivity in random key graphs, IEEE Transactions on Information Theory~ 58 (2012), 2983 - 2999.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.