Degree and clustering coefficient in sparse random intersection graphs. (English) Zbl 1273.05197

Summary: We establish asymptotic vertex degree distribution and examine its relation to the clustering coefficient in two popular random intersection graph models of E. Godehardt and J. Jaworski [Electron. Notes Discrete Math. 10, 129–132 (2001; Zbl 1182.05108)]. For sparse graphs with a positive clustering coefficient, we examine statistical dependence between the (local) clustering coefficient and the degree. Our results are mathematically rigorous. They are consistent with the empirical observation of I. Foudalis et al. [Lect. Notes Comp. Sci. 6732, 85–102 (2011; Zbl 1328.91262)] that, “clustering correlates negatively with degree.” Moreover, they explain empirical results on \(k^{-1}\) scaling of the local clustering coefficient of a vertex of degree \(k\) reported in E. Ravasz and A.L. Barabási [Phys. Rev. E67, 026112 (2003)].


05C80 Random graphs (graph-theoretic aspects)
91D30 Social networks; opinion dynamics
05C07 Vertex degrees
Full Text: DOI arXiv Euclid


[1] Barbour, A. D. and Reinert, G. (2011). The shortest distance in random multi-type intersection graphs. Random Structures Algorithms 39 179-209. · Zbl 1231.05081
[2] Barrat, A. and Weigt, M. (2000). On the properties of small-world networks. Eur. Phys. J. B 13 547-560.
[3] Blackburn, S. R. and Gerke, S. (2009). Connectivity of the uniform random intersection graph. Discrete Math. 309 5130-5140. · Zbl 1207.05110
[4] Bloznelis, M. (2008). Degree distribution of a typical vertex in a general random intersection graph. Lith. Math. J. 48 38-45. · Zbl 1223.05269
[5] Bloznelis, M. (2010). A random intersection digraph: Indegree and outdegree distributions. Discrete Math. 310 2560-2566. · Zbl 1210.05156
[6] Bloznelis, M. (2010). The largest component in an inhomogeneous random intersection graph with clustering. Electron. J. Combin. 17 Research Paper 110, 17. · Zbl 1193.05144
[7] Breiman, L. (1968). Probability . Addison-Wesley, Reading, MA. · Zbl 0174.48801
[8] Britton, T., Deijfen, M., Lagerås, A. N. and Lindholm, M. (2008). Epidemics on random graphs with tunable clustering. J. Appl. Probab. 45 743-756. · Zbl 1147.92034
[9] Deijfen, M. and Kets, W. (2009). Random intersection graphs with tunable degree distribution and clustering. Probab. Engrg. Inform. Sci. 23 661-674. · Zbl 1180.68212
[10] Eschenauer, L. and Gligor, V. D. (2002). A key-management scheme for distributed sensor networks. In Proceedings of the 9 th ACM Conference on Computer and Communications Security , Washington , DC 41-47.
[11] Foss, S., Korshunov, D. and Zachary, S. (2011). An Introduction to Heavy-Tailed and Subexponential Distributions . ACM, New York. · Zbl 1250.62025
[12] Foudalis, I., Jain, K., Papadimitriou, C. and Sideri, M. (2011). Modeling social networks through user background and behavior. In Algorithms and Models for the Web Graph. Lecture Notes in Computer Science 6732 85-102. Springer, Heidelberg. · Zbl 1328.91262
[13] Godehardt, E. and Jaworski, J. (2001). Two models of random intersection graphs and their applications. Electron. Notes Discrete Math. 10 129-132. · Zbl 1182.05108
[14] Godehardt, E. and Jaworski, J. (2003). Two models of random intersection graphs for classification. In Exploratory Data Analysis in Empirical Research 67-81. Springer, Berlin. · Zbl 1182.05108
[15] Godehardt, E., Jaworski, J. and Rybarczyk, K. (2012). Clustering coefficients of random intersection graphs. In Studies in Classification , Data Analysis and Knowledge Organization 243-253. Springer, Berlin. · Zbl 1233.05184
[16] Guillaume, J.-L. and Latapy, M. (2004). Bipartite structure of all complex networks. Inform. Process. Lett. 90 215-221. · Zbl 1178.68031
[17] Jaworski, J., Karoński, M. and Stark, D. (2006). The degree of a typical vertex in generalized random intersection graph models. Discrete Math. 306 2152-2165. · Zbl 1102.05057
[18] Jaworski, J. and Stark, D. (2008). The vertex degree distribution of passive random intersection graph models. Combin. Probab. Comput. 17 549-558. · Zbl 1170.05054
[19] Karoński, M., Scheinerman, E. R. and Singer-Cohen, K. B. (1999). On random intersection graphs: The subgraph problem. Combin. Probab. Comput. 8 131-159. · Zbl 0924.05059
[20] Newman, M. E. J. (2003). Properties of highly clustered networks. Phys. Rev. E 68 026121.
[21] 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.
[22] Newman, M. E. J., Watts, D. J. and Strogatz, S. H. (2002). Random graph models of social networks. Proc. Natl. Acad. Sci. USA 99 (Suppl. 1) 2566-2572. · Zbl 1114.91362
[23] Nikoletseas, S., Raptopoulos, C. and Spirakis, P. G. (2011). On the independence number and Hamiltonicity of uniform random intersection graphs. Theoret. Comput. Sci. 412 6750-6760. · Zbl 1233.05186
[24] Ravasz, L. and Barabási, A. L. (2003). Hierarchical organization in complex networks. Phys. Rev. E 67 026112. · Zbl 1151.91744
[25] Rybarczyk, K. (2011). Diameter, connectivity, and phase transition of the uniform random intersection graph. Discrete Math. 311 1998-2019. · Zbl 1223.05283
[26] Rybarczyk, K. (2012). The degree distribution in random intersection graphs. In Challenges at the Interface of Data Analysis , Computer Science , and Optimization 291-299. Springer, Berlin. · Zbl 1233.68181
[27] Stark, D. (2004). The vertex degree distribution of random intersection graphs. Random Structures Algorithms 24 249-258. · Zbl 1042.05091
[28] Steele, J. M. (1994). Le Cam’s inequality and Poisson approximations. Amer. Math. Monthly 101 48-54. · Zbl 0802.60019
[29] Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of “small-world” networks. Nature 393 440-442. · Zbl 1368.05139
[30] Yagan, O. and Makowski, A. M. (2009). Random key graphs-Can they be small worlds? In NETCOM’ 09: Proceedings of the 2009 First International Conference on Networks & Communications 313-318. IEEE Computer Society, Washington, DC.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.