Connectivity of the Uniform Random Intersection Graph

2008/05/19 by Simon R. Blackburn⋆, Blackburn, Simon R., Stefanie Gerke +1
Computer Science · Mathematics · #05C80 #68R10 #94C15 #Combinatorics (math.CO) #FOS: Mathematics #Mobile Ad Hoc Networks #Security in Wireless Sensor Networks #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.0805.2814

openalex publication_date 2008/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A uniform random intersection graph G(n,m,k) is a random graph constructed as follows. Label each of n nodes by a randomly chosen set of k distinct colours taken from some finite set of possible colours of size m. Nodes are joined by an edge if and only if some colour appears in both their labels. These graphs arise in the study of the security of wireless sensor networks. Such graphs arise in particular when modelling the network graph of the well known key predistribution technique due to Eschenauer and Gligor. The paper determines the threshold for connectivity of the graph G(n,m,k) when n→ ∞ with k a function of n such that k≥ 2 and m=\lfloor n^α\rfloor for some fixed positive real number α. In this situation, G(n,m,k) is almost surely connected when \liminf k²n/mlog ngt;1, and G(n,m,k) is almost surely disconnected when \limsup k²n/mlog nlt;1.

Related

• On connectivity in a general random intersection graph
• Random intersection graphs and their applications in security, wireless communication, and social networks
• On k-connectivity and minimum vertex degree in random s-intersection graphs
• On Connectivity Thresholds in the Intersection of Random Key Graphs on Random Geometric Graphs
• Vertex Degree of Random Intersection Graph