Math Insight

Random networks

When analyzing a network, one approach is look at the network as a single fixed entity. But sometimes, it is useful to think of the edges as random variables. With this random network perspective, a given network is more than a single object. Instead, we can view the random network as a sample from a probability distribution. We can then study the whole probability distribution to gain insight into the network.

We can view the probability distribution of random networks as defining a whole ensemble of many different networks, where the probability of any particular network is determined by the probability distribution. Rather than looking at the particular properties of a single network, we can study the properties of the whole ensemble of networks.

For unweighted graphs, we can describe the network by the probability distribution of the adjacency matrix $A$. Let $P_A(X)$ be this probability distribution, describing the probability that $A=X$, \begin{align} P_A(X) &= \Pr(A=X)\notag\\ &= \Pr(A_{ij}=X_{ij} \text{ for all node indices $i$ and $j$}). \label{probability_adjacency_matrix}\tag{1} \end{align}

One advantage of looking at an ensemble of networks defined by a probability distribution is that we can zero in on the influence of different statistical properties. We can imagine taking many samples from the probability distribution and look for properties that are common to most of the samples. In some cases, we might be able to take an ensemble average of a quantity, where we take an average over the probability distribution.

Besides the mathematical convenience, in many cases, looking for properties over a whole network ensemble makes sense in a real world application. For example, despite the fact that people's brains are wired differently, most people are able to perform similar motor tasks, such as picking up an object. If we want to discover the network properties that facilitate such an action, we might not be interested in the network variations among individuals but the features that are common among the individual. A random network framework where the different networks are samples from the same probability distribution may be useful for examining such questions.

Without any restrictions, a random network model is very high-dimensional, but one can make tractable random network models through various simplifcations. The simplest random network model is the Erdös-Rényi random network (ER random network), where all edges are independent. Other random networks models are the configuration model, the small world network, the scale free network, and the SONET model.