Introduction:

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

What is the cardinality of ? 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 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:

grows more than exponentially fast:

It’s worth noting that grows more than exponentially fast as a function of 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 to a network with vertices the number of possible networks grows by a factor of . The reason for this is that when a new vertex is added to a graph with vertices there are possible new edges between and the existing set of vertices.

Another way to think about (3) is that given a graph with vertices an additional vertex adds 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 in a graph sampled uniformly from :

\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 has more than half the maximum number of edges, , is also . This doesn’t contradict the last observation since the number of possible edges grows quadratically while the number of possible vertices grows linearly .

Discussion:

This analysis actually preceded my last article on simple graphs that are connected and due to the rapid growth of 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?