We study a preferential attachment model G_n^h. The graph G_n^h is generated from a finite initial graph by adding new vertices one at a time. Each new vertex connects to h ≥ 1 already existing vertices, and these are chosen with probability proportional to their current degrees. We are particularly interested in the community structure of G_n^h, which is expressed in terms of the so-called modularity. We prove that the modularity of G_n^h is, with high probability, upper bounded by a function that tends to 0 as h tends to infinity. This resolves a conjecture of Prokhorenkova, Prałat, and Raigorodskii from 2016. As a byproduct, we obtain novel concentration results (which are interesting in their own right) for the volume and edge density parameters of vertex subsets of G_n^h. The key ingredient here is the definition of a function μ, which serves as a natural measure for vertex subsets, and is proportional to the average size of their volumes. This extends previous results on the topic by Frieze, Pérez-Giménez, Prałat, and Reiniger from 2019.

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.

Let $\mathbb{H}^{(k)}(n, N)$, where $k \ge 2$, be a random hypergraph on the vertex set $[n] = \{1, 2, \dots, n\}$ with $N$ edges drawn independently with replacement from all subsets of $[n]$ of size $k$. For $\bar{d} = k N/n$ and any $\varepsilon > 0$ we show that if $k = o(\ln ({\bar d}/\ln n))$ and $k = o(\ln (n/\ln {\bar d}))$, then with probability $1-o(1)$ a random greedy algorithm produces a proper edge coloring of $\mathbb{H}^{(k)}(n, N)$ with at most $\bar{d} (1+\varepsilon)$ colors. This yields the asymptotic chromatic number of the corresponding uniform random intersection graph.

A key distribution scheme for wireless sensor networks based on a system of dynamic, pairwise keys is considered. In the scheme, each pair of communicating nodes shares pairwise symmetric keys and changes them at every transmission using a set of hashing functions. This article examines security aspects of the protocol. The most important issue is to ensure that it is infeasible for an adversary to restrict exhaustive key search to a subset of the keyspace. This desirable property holds if, after a small number of random key transitions, the distribution of keys among the nodes is close to uniform. The article provides a rigorous mathematical analysis of the distribution of keys and supplements it with experimental results. The problem is reduced to the question of determining mixing time and the stationary distribution of a random walk on a random digraph. It is shown that with probability close to 1, the mixing time is of small order and the fluctuations of the distribution are limited. This ensures the ongoing security of the protocol by making the communications forward secure and protecting against node compromise.

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