1
$\begingroup$

I'm interested in the following (pretty open-ended) problem :

Say we have some network of $n$ nodes, labeled by integers $i\in\mathbb{Z}/n\mathbb{Z}$. Each node $i$ chooses a random subset $\mathrm{Out}_i\subset\mathbb{Z}/n\mathbb{Z}\setminus\{0\}$ and establishes (outgoing) connections to its peers $i+j$, where $j\in\mathrm{Out}_i$. While the nodes choose their neighbors, they are unaware of the other nodes' choices. But as soon as the network is turned on, (outgoing) connections (they established) and incoming connections (created by other nodes) become bilateral connections. Suppose that I have some probability distribution $\mathbb{P}$ on the set $\mathscr{P}\big(\mathbb{Z}/n\mathbb{Z}\setminus\{0\}\big)$ of all subsets of $\mathbb{Z}/n\mathbb{Z}\setminus\{0\}$, and suppose furthermore that $$\forall A, B\subset\mathbb{Z}/n\mathbb{Z}\setminus\{0\},~\#A=\#B\implies \mathbb{P}(\{A\})=\mathbb{P}(\{B\}).$$

Let us model the maps $\mathrm{Out}_i$ as iid random variables with range $\mathscr{P}\big(\mathbb{Z}/n\mathbb{Z}\setminus\{0\}\big)$ with distribution $\mathbb{P}$. Associated to some draw $\omega$ of the outgoing connections, we have the set of all connections which is the symmetric relation $\Gamma\subset\mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}$ of all pairs $(i,j)$ s.a. either $j-i\in\mathrm{Out}_i$ or $i-j\in\mathrm{Out}_j$, and thus the (unoriented) graph $G$ whose adjancency matrix is $\Gamma$.

Depending on $\mathbb{P}$, how large are the connected components of $G$ on average ? How many are there on average ?

I'd be perfectly content with a reference to the litterature where this problem has bee considered. Here are some clarifications :

  1. if $i$ creates an outgoing connection to node $j$, then this connection becomes a two-way street as soon as the network is turned on. This is why we define $\Gamma$ to be a symmetric relation.
  2. It might happen that $i$ and $j$ both establish outgoing connections to one-another. In that case nothing special happens.
  3. This construction starts out being nonsymmetric, but in the end we have an undirected graph. We only care about connections between nodes.
  4. $\mathbb{P}$ is nothing more than a sequence of nonnegative real numbers $p_0,p_1,\dots,p_{n-1}$ such that $$\sum_{k=0}^{n-1}\binom{n-1}kp_k=1$$
$\endgroup$
  • $\begingroup$ A simplification I would be fine with is to consider that there are Bernoulli r.v. $X_{i\to j}$ that equal $1$ iff $i$ establishes an outgoing connection to $j$, and have $i+\mathrm{Out}_i=\{j\mid X_{i\to j}=1\}$. $\endgroup$ – Olivier Bégassat Nov 25 '18 at 16:19
2
$\begingroup$

First of all, in the simplification you're considering, where $\text{Out}_i$ is obtained from i.i.d. Bernoulli random variables $X_{i \to j}$, we get an Erdős–Rényi random graph: if $X_{i \to j} = 1$ with probability $p$, then the probability that $i$ and $j$ are adjacent in the final graph $G$ is $1 - (1-p)^2$ independently of all other edges.

Such a graph is almost always disconnected when $1 - (1-p)^2 \ll \frac{\log n}{n}$, and almost always connected when $1 - (1-p)^2 \gg \frac{\log n}{n}$. The explanation for this threshold is that the primary obstacle to connectivity is isolated vertices. When the probability that a vertex is isolated drops substantially below $\frac 1n$, then with high probability there are no such vertices, and then with high probability the graph is connected, because other obstacles are much more rare.

When the Erdős–Rényi random graph is disconnected, lots is known about the size of the components; too much to summarize. Briefly, when $1 - (1-p)^2 \le \frac cn$ with $c<1$, the graph has many small components, and when $1 - (1-p)^2 \ge \frac cn$ with $c>1$, the graph has a single giant component of linear size, and all other components are small. As we increase $p$ further, the small components disappear in order of size, with isolated vertices being the last to go.

Another well-studied special case of your random network is the $k$-out model, where we take $p_k = \binom{n-1}{k}^{-1}$ and set all other values of $p_0, p_1, \dots, p_n$ to $0$. In this model, it's known that the resulting graph is:

  • disconnected when $k=1$, with high probability;
  • $k$-connected, $k$-edge-connected, and has minimum degree $k$ when $k \ge 2$, with high probability.

See chapter 16 in this textbook. (The first few chapters are a good reference on the Erdős–Rényi model, as well, and parts of chapter 15 can help you understand the number of components in the $1$-out model, which is complicated.)

In particular, we can conclude that your graph $G$ is connected with high probability when $p_0 = p_1 = 0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.