Connectivity of the uniform random intersection graph

DOI10.1016/J.DISC.2009.03.042MaRDI QIDQ1044989zbMATH OpenOpenAlexFDO

Authors Simon R. Blackburn, Stefanie Gerke

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.2814

zbMATH Keywords

key predistributionrandom intersection graphwireless sensor network

Mathematics Subject Classification ID

Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80)

Abstract: A emph{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 $noinfty$ with $k$ a function of $n$ such that $kgeq2$ and $m=lfloor{n}^{a}lphafloor$ for some fixed positive real number $alpha$. In this situation, $G(n,m,k)$ is almost surely connected when [ liminf k^2n/mlog n>1, ] and $G(n,m,k)$ is almost surely disconnected when [ limsup k^2n/mlog n<1. ]

Recommendations

• \(k\)-connectivity of uniform \(s\)-intersection graphs
• Diameter, connectivity, and phase transition of the uniform random intersection graph
• On k-connectivity and minimum vertex degree in random s-intersection graphs
• On the isolated vertices and connectivity in random intersection graphs
• On Some Combinatorial Properties of Random Intersection Graphs

Cites work

• Component evolution in a secure wireless sensor network
• Efficiently covering complex networks with cliques of similar vertices
• Paths in graphs
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• The degree of a typical vertex in generalized random intersection graph models
• The vertex degree distribution of random intersection graphs

Cited in

(29)

• Zero-one law for connectivity in superposition of random key graphs on random geometric graphs
• Asymptotic distribution of isolated nodes in secure wireless sensor networks under transmission constraints
• Degree and clustering coefficient in sparse random intersection graphs
• Asymptotic connectedness of random interval graphs in a one dimensional data delivery problem
• Phase transitions for detecting latent geometry in random graphs
• Diameter, connectivity, and phase transition of the uniform random intersection graph
• Perfect matchings in random intersection graphs
• Threshold behavior of multi-path random key pre-distribution for sparse wireless sensor networks
• Graph-theoretic design and analysis of key predistribution schemes
• Selected Combinatorial Properties of Random Intersection Graphs
• Random subcube intersection graphs. I: Cliques and covering
• Degree distribution of an inhomogeneous random intersection graph
• \(k\)-connectivity of uniform \(s\)-intersection graphs
• On the complexity of the herding attack and some related attacks on hash functions
• Poisson approximation of the number of cliques in random intersection graphs
• A new random graph model with self-optimizing nodes: connectivity and diameter
• Random intersection graphs with communities
• Component evolution in a secure wireless sensor network
• On k-connectivity and minimum vertex degree in random s-intersection graphs
• On Connectivity and Robustness in Random Intersection Graphs
• On the isolated vertices and connectivity in random intersection graphs
• Phase transition in random intersection graphs with communities
• A note on hamiltonicity of uniform random intersection graphs
• On the independence number and Hamiltonicity of uniform random intersection graphs
• Existence of connected intersection-free subgraphs in graphs with redundancy and coexistence property
• Connectivity threshold for superpositions of Bernoulli random graphs
• Dynamic random intersection graph: dynamic local convergence and giant structure
• A random intersection digraph: indegree and outdegree distributions
• Connectivity in a random interval graph with access points

This page was built for publication: Connectivity of the uniform random intersection graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1044989)