Source-linked AI summary
Connectivity of the Uniform Random Intersection Graph
Simon R. Blackburn, Stefanie Gerke
TL;DR
Uniform random intersection graphs model shared-key links in wireless sensor networks, where connectivity informs key-predistribution parameter choices. The paper establishes connectivity and disconnection thresholds, while identifying a narrow parameter range outside its results.
Problem
The paper seeks a precise connectivity threshold because the Erdős–Rényi approximation used in much WSN literature can differ sharply from uniform random intersection graphs.
Source: §1.1 · p. 2Method
The paper analyzes connectivity across parameter regimes and uses m = ⌊n^α⌋, for fixed positive α, to state a concise result.
Source: §1.2 · pp. 3–4Results
For m ≥ n, G(n, m, k) is almost surely connected when lim inf k^2n/(m log n) > 1 and disconnected when lim sup k^2n/(m log n) < 1.
Source: §1.2 · p. 3Takeaways & Limitations
The connectivity threshold matters for choosing parameters in the Eschenauer–Gligor scheme for secure wireless sensor networks.
Source: §1.1 · p. 2A narrow range remains uncovered when m grows just a little more slowly than n; the stated power-law setting avoids this gap.
Source: §1.2 · p. 4
Abstract
from arXiv · showhide
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 $n\to \infty$ with $k$ a function of $n$ such that $k\geq 2$ and $m=\lfloor n^\alpha\rfloor$ for some fixed positive real number $\alpha$. In this situation, $G(n,m,k)$ is almost surely connected when \[ \liminf k^2n/m\log n>1, \] and $G(n,m,k)$ is almost surely disconnected when \[ \limsup k^2n/m\log n<1. \]
1 Introduction
The paper studies connectivity in uniform random intersection graphs, motivated by secure wireless sensor networks and the need to choose parameters for the Eschenauer–Gligor scheme. It establishes connectivity and disconnection regimes while noting a narrow parameter range not covered by its results.
1.1 Notation and motivation
- The graph models a sensor network in which nodes share an edge when their randomly assigned encryption-key sets overlap, assuming all sensors are within communication range.Connectivity matters for secure communication and parameter selection in the Eschenauer–Gligor scheme.Source: §1.1 · p. 2
1.2 Our results
- For m ≥ n, the graph is almost surely connected when lim inf k^2n/(m log n) > 1 and disconnected when lim sup k^2n/(m log n) < 1; for m ≤ n, connectivity is also established under a stated condition, with the threshold tight for k = 2.The authors leave a narrow range just below m = n uncovered; their power-law setting m = ⌊n^α⌋ avoids this gap.Source: §1.2 · pp. 3–4
1.3 Related results
- Earlier work on non-uniform intersection graphs gives a matching threshold when α > 1, but a higher one when α ≤ 1, where small or empty node sets impede connectivity.Singer-Cohen’s comparison is made with p = k/m, giving expected set size k; the paper notes that the non-uniform and uniform models can behave differently.Source: §1.3 · p. 5
1.4 The structure of the paper
- The paper first treats isolated vertices, then k = 2 for α < 1, then α ≥ 1, and concludes with prospects for tighter thresholds.The isolated-vertex result supports the disconnection direction of the main theorem.Source: §1.4 · p. 5
2 Isolated vertices
This section establishes complementary regimes in which isolated vertices are absent or present almost surely. It uses first- and second-moment arguments to prove the claims.
2 Isolated vertices
- The theorem gives complementary parameter regimes in which G(n, m, k) almost surely has no isolated vertices or contains an isolated vertex.The supplied theorem passages state these two outcomes but do not include their full conditions.Source: §2 · pp. 5–6
- The proof uses standard random-graph techniques; earlier work determines the number of isolated vertices on the threshold, but a direct reduction can fail because k is integer-valued.Changing k by 1 can change k^2n/m by a factor greater than log n.Source: §2 · p. 6
- For the no-isolated-vertex regime, the proof bounds the expected number of isolated vertices and applies Markov’s inequality.It expresses the expected count as n times the isolation probability of any fixed vertex.Source: §2 · p. 6
- For the isolated-vertex regime, the second-moment argument reduces the task to showing Var(X) ≪ E(X)^2, using the joint isolation probability of two fixed vertices.Both vertices must have disjoint colour sets, and every other vertex’s set must avoid their union.Source: §2 · pp. 7–8
3 The case when k = 2 or m = o(n/ log n)
The section proves connectivity results for the case k = 2 and extends connectivity to all k ≥ 2 when m = o(n/ log n). Its k = 2 argument uses a colour graph whose near-connectivity corresponds to connectivity of the original graph.
3 The case when k = 2 or m = o(n/ log n
- For k = 2, as n → ∞ with ω → ∞, G(n, m, 2) is almost surely connected in one passage and almost surely not connected in the other.Source: §3 · p. 8
- When m = o(n/ log n), G(n, m, k) is asymptotically almost surely connected for k ≥ 2.The proof first constructs G(n, m, 2), then adds colours, which can only add edges.Source: §3 · p. 8
- For k = 2, connectivity of G(n, m, 2) is equivalent to near-connectivity of the colour graph H(n, m, 2).H has colours as vertices and an edge for each colour pair assigned to at least one original vertex.Source: §3 · p. 10
- The colour graph has at least n − (log n)^3 distinct edges asymptotically almost surely, because repeated colour pairs are rare.The proof bounds the number of pairs of original vertices with identical colour sets by (log n)^3 asymptotically almost surely.Source: §3 · p. 10
- The proof samples distinct edges of a uniformly chosen graph on m colours and uses monotonicity of near-connectivity to establish the result.It suffices to show that this subgraph is almost surely near-connected.Source: §3 · pp. 10–11
4 The case when m ≥n
For m ≥ n, the section establishes connectivity and disconnection results under the respective conditions of Theorem 5. The connectivity proof rules out components across several size ranges and tightens earlier work by Di Pietro et al..
4 The case when m ≥n
- For m ≥ n, Theorem 5 establishes asymptotic almost-sure connectivity and disconnection in its respective parameter regimes.The supplied passages state the outcomes but do not provide complete expressions for the parameter conditions.Source: §4 · p. 11
- The proof parallels and tightens the work of Di Pietro et al..The section notes that its approach subtly differs from theirs, although the detailed comparison is outside this request’s supplied passages.Source: §4 · p. 11
- Since any disconnected graph has a component of size at most n/2, ruling out such components with probability tending to one yields connectivity.The three lemmas together show that the probability of such a component tends to zero.Source: §4 · pp. 11–12
- Under the connectivity conditions, the graph asymptotically almost surely has no components of sizes s ≤ en^(8/9), en^(8/9) ≤ s ≤ min{m/k, n/2}, or m/k < s ≤ n/2.These three ranges are covered by Lemmas 6, 7, and 8, respectively.Source: §4 · pp. 12, 14, 15
- For a fixed vertex set S, the proof bounds its chance of being a component by considering how many distinct colours S receives and whether outside vertices avoid them.When S receives enough colours, every outside vertex must choose colours disjoint from those assigned to S.Source: §4 · pp. 12, 13, 15
5 Discussion
The discussion conjectures a sharper general connectivity threshold, while noting which parts the paper establishes and what remains unresolved. It also distinguishes proven monotonicity in k from an unproved belief about m.
5 Discussion
- The paper conjectures a sharper connectivity threshold, proves the conjectured disconnected side, and establishes the full conjecture when k = 2.A possible route to the general result would use a hypergraph analogue of the near-connectivity threshold, but the authors say sufficiently strong hypergraph results are not known.Source: §5 · p. 18
- Connectivity probability is non-decreasing in k, while non-increase in m is presented as plausible but unproved.The paper asks whether the latter monotonicity can be proved.Source: §5 · p. 18