Introduction:

Let’s suppose we have a graph with \(N\) vertices. How many ways can these vertices be wired to each other assuming that these vertices are distinct and each vertex \(v_i\) may be connected to at most \(N-1\) distinct vertices? Alternately, let’s consider the set \(G_N\) of simple graphs with \(N\) vertices. This set may correspond to the set of potential social networks among a community of \(N\) individuals.

What is the cardinality of \(G_N\)? We may show that:

\begin{equation} \lvert G_N \rvert = \sum_{k=0}^{N \choose 2} { {N \choose 2} \choose k} = 2^{N \choose 2} \end{equation}

and we may note that \(\lvert G_N \rvert\) very quickly becomes astronomical:

\begin{equation} \forall N > 50, \lvert G_N \rvert > 10^{368} \end{equation}

which is many times greater than the number of atoms in the universe.

A few observations:

\(\lvert G_N \rvert\) grows more than exponentially fast:

It’s worth noting that \(\lvert G_N \rvert\) grows more than exponentially fast as a function of \(N\) since:

\begin{equation} \frac{\lvert G_{N+1} \rvert}{\lvert G_{N} \rvert} = 2^N \end{equation}

so we have:

\begin{equation} \lvert G_{N+1} \rvert = 2^N \cdot \lvert G_{N} \rvert \end{equation}

and this means that whenever we add a vertex \(\widehat{v_{N+1}}\) to a network with \(N\) vertices the number of possible networks grows by a factor of \(2^N\). The reason for this is that when a new vertex \(\widehat{v_{N+1}}\) is added to a graph with \(N\) vertices there are \(N\) possible new edges between \(\widehat{v_{N+1}}\) and the existing set of vertices.

Another way to think about (3) is that given a graph with \(N\) vertices an additional vertex \(\widehat{v_{N+1}}\) adds \(N\) bits of information. Between any two vertices we have either a connection or we don’t so:

\begin{equation} \log_2(\lvert G_{N+1} \rvert) - \log_2(\lvert G_{N} \rvert) = N \end{equation}

Probabilistic analysis:

Now, let’s consider the probability of a connection between a random pair of vertices \((v_i,v_j)\) in a graph \(\Gamma_N\) sampled uniformly from \(G_N\):

\begin{equation} P(\overline{v_iv_j} \in \Gamma_N) = \frac{ {N \choose 2} }{2^{N \choose 2}} \end{equation}

and this probability goes down exponentially quickly since:

\begin{equation} \frac{P(\overline{v_iv_j} \in \Gamma_{N+1})}{P(\overline{v_lv_k} \in \Gamma_N)} = \frac{(N+1) \cdot 2^{-N}}{N-1} \approx 2^{-N} \end{equation}

Within the context of social networks, if we suppose that a connection between any pair of individuals occurs with probability half then the probability of a connection between a randomly chosen pair of individuals drops off to zero exponentially fast as the size of the network, i.e. number of individuals, grows.

We can make one more relatively simple observation that is also useful. Given the symmetry of binomial coefficients, the probability that a randomly chosen graph \(\Gamma_N \sim G_N\) has more than half the maximum number of edges, \({N \choose 2}\), is also \(\frac{1}{2}\). This doesn’t contradict the last observation since the number of possible edges grows quadratically \(\sim \frac{N^2}{2}\) while the number of possible vertices grows linearly \(\sim N\).

Discussion:

This analysis actually preceded my last article on simple graphs that are connected and due to the rapid growth of \(\lvert G_N \rvert\) we may ask what does a typical graph look like.

We know that almost all simple graphs are connected but generally speaking what are the properties of almost all simple graphs?