4
$\begingroup$

Two days ago it occurred to me that almost all simple graphs are small world networks in the sense that if $G_N$ is a simple graph with $N$ nodes sampled from the Erdös-Rényi random graph distribution with probability half then when $N$ is large:

\begin{equation} \mathbb{E}[d(v_i,v_j)] \leq \log_2 N \tag{1} \end{equation}

My strategy for proving this was to show that when $N$ is large, $\forall v_i \in G_N$ there exists a chain of distinct nodes of length $\log_2 N$ originating from $v_i$ almost surely. This implies that:

\begin{equation} \forall v_i, v_j \in G_N, d(v_i,v_j) \leq \log_2 N \tag{2} \end{equation}

almost surely when $N$ is large.

Now, by using the above method of proof I managed to show that almost all simple graphs are very small in the sense that:

\begin{equation} \mathbb{E}[d(v_i,v_j)] \leq \log_2\log_2 N \tag{3} \end{equation}

when $N$ tends to infinity. My question is whether there is an elementary proof that almost all simple graphs are very small world networks and if so in what sense are small world networks special?

Note: I would consider the probabilistic proof I found elementary though I am not a graph theorist so I am not sure whether it's simpler or more complex than the standard proof.

$\endgroup$
5
  • 1
    $\begingroup$ What do you mean by "a Hamiltonian path of length $\log_2N$"? A Hamiltonian path have length $N$. $\endgroup$ Jul 29, 2019 at 11:05
  • 1
    $\begingroup$ @Bullet51 I changed the phrasing to avoid confusion. I mean that there is a path of length log2N starting from vi where each node in that path is distinct. $\endgroup$ Jul 29, 2019 at 11:09
  • 1
    $\begingroup$ Most graphs have diameter 2. This is elementary. $\endgroup$ Jul 29, 2019 at 13:08
  • $\begingroup$ @BrendanMcKay This wasn't obvious to me. In fact, until very recently I used to think that small world networks, such as social networks, were somehow exceptional in a mathematical sense. $\endgroup$ Jul 29, 2019 at 14:38
  • 2
    $\begingroup$ Just a side point, small-world graphs are not necessarily good models of social networks (Erdos-Renyi graphs definitely aren't) and the Erdos-Renyi measure on graphs is a very specific one that imposes a lot of structure behind the phrase "almost all". $\endgroup$
    – usul
    Jul 29, 2019 at 16:32

1 Answer 1

1
$\begingroup$

whether there is an elementary proof that almost all simple graphs are very small world networks

Following up on Brendan McKay's comment. The chance that an Edos-Renyi$(0.5,n)$ graph has diameter one is $0.5^{n(n-1)/2}$, which of course goes to zero exponentially fast.

On the other hand, two vertices have a distance of at most two if there exists a third vertex with edges to both of them. For a fixed third vertex, this chance is $0.5^2 = 1/4$. By independence, the chance this fails to occur for all $n-2$ choices of third vertex is $(3/4)^{n-2}$.

There are $n(n-1)/2$ pairs of vertices, so by a union bound, the chance that there exists a pair of distance strictly more than $2$ is at most $$ \frac{n(n-1)}{2} \left(\frac{3}{4}\right)^{n-2} .$$

So the diameter of the graph is $2$ with probability $1 - e^{-\Theta(n)}$.

if so in what sense are small world networks special

Of course people more expert than I can go on about it at length. But (1) networks arising in Euclidean space, like road networks, don't have these kinds of properties. And many of our networks, even social networks, are roughly related to a geographical embedding, making small degrees of separation surprising. (2) Often we are thinking of more properties than just small-world (low diameter). Social networks have lots of unusual properties that Erdos-Renyi graphs don't have. (Come to think of it, their diameter is more than $2$, and we just showed this is extremely unusual.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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