Many known networks have structure of affiliation networks, where each of$n$network nodes (actors) selects an attribute set from a given collection of$m$attributes, and two nodes (actors) establish adjacency relation whenever they share a common attribute. We study the behavior of a random walk on such networks. For this purpose, we use a common model of such networks, a random intersection graph. We establish the cover time of the simple random walk on the binomial random intersection graph${\mathcal{ G}}(n,m,p)$at the connectivity threshold and above it. We consider the range of$(n,m,p)$, where the typical attribute is shared by a (stochastically) bounded number of actors.

Given integers n, m and a probability distribution $P_*$ on $[m]=\{1,\dots,m\}$, consider the random intersection graph on the vertex set $[n]$, where $i,j\in[n]$ are declared to be adjacent whenever $S(i)\cap S(j)\neq\emptyset$. Here $S(1),\dots,S(n)$ denote independent and identically distributed random subsets of $[m]$ with the distribution $\mathbf{P}(S(i)=A)={m\choose|A|}^{-1}P_*(|A|)$ for $A\subset[m]$. Assuming that m is much larger than n, we show that the order of the largest connected component $N_1=n\rho+o_P(n)$ as $n,m\to\infty$. Here $\rho$ denotes the nonextinction probability of a related multitype Poisson branching process.

Abstract We study a connectivity property of a secure wireless network that uses random pre‐distribution of keys. A network is composed of n sensors. Each sensor is assigned a collection of d different keys drawn uniformly at random from a given set of m keys. Two sensors are joined by a communication link if they share a common key. We show that for large n with high probability the connected component of size Ω( n ) emerges in the network when the probability of a link exceeds the threshold 1/ n . Similar component evolution is shown for networks where sensors communicate if they share at least s common keys. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009