Degree and clustering coefficient in sparse random intersection graphs

Abstract

We establish asymptotic vertex degree distribution and examine its relation to the clustering coefficient in two popular random intersection graph models of Godehardt and Jaworski [Electron. Notes Discrete Math. 10 (2001) 129-132]. 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 Foudalis et al. [In Algorithms and Models for Web Graph (2011) Springer] 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 Ravasz and Barabasi [Phys. Rev. E 67 (2003) 026112].

Published in at http://dx.doi.org/10.1214/12-AAP874 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Random graphs with arbitrary degree distributions and their applications
• Hierarchical Organization in Complex Networks
• Properties of highly clustered networks

Cited by in corpus (17)

• Assortativity and clustering of sparse random intersection graphs
• On resilience and connectivity of secure wireless sensor networks under node capture attacks
• Topological properties of secure wireless sensor networks under the q-composite key predistribution scheme with unreliable links
• On Connectivity and Robustness in Random Intersection Graphs
• On the strengths of connectivity and robustness in general random intersection graphs
• On Topological Properties of Wireless Sensor Networks under the q-Composite Key Predistribution Scheme with On/Off Channels
• Random intersection graphs with communities
• Scale-free network clustering in hyperbolic and other random graphs
• Probabilistic key predistribution in mobile networks resilient to node-capture attacks
• On secure communication in sensor networks under q-composite key predistribution with unreliable links
• Analyzing connectivity of heterogeneous secure sensor networks
• Analyzing resilience of interest-based social networks against node and link failures
• Clique and cycle frequencies in a sparse random graph model with overlapping communities
• Degree-penalized contact processes
• Collecting Influencers: A Comparative Study of Online Network Crawlers
• Geometric random intersection graphs with general connection probabilities
• Secure Connectivity of Wireless Sensor Networks Under Key Predistribution with on/off Channels