Complex Networks 3

(It is assumed that the reader has read the Second article of this series)

Mathematicians are well known for their eccentric personalities. In fact, the best image of a mathematician for the layman is that of a mad person who solves equations instead of breathing! Of course not all mathematicians are eccentric, but surely, many are and perhaps the best known figure of 20th century is Paul Erdos. From a mathematical point of view, he is best known for having the most number of collaborators, the most number of research papers published in mathematics (more than Euler!) and for working in diverse areas of mathematics.

After Euler solved the seven bridge problem, (see Complex Networks 2), graph theory became amongst mathematicians a subject that dealt with more or less regular graphs. One of the biggest achievements of Erdos (along with his Hungarian collaborator Renyi) is laying the foundation of Random graph theory which he accomplished in the 1950s. Today we are going to look at the model of a graph introduced by Erdos which is known as the Erdos-Renyi graph in the associated literature.

Erdos-Renyi graph (ER graph for brevity) consists of a fixed number of nodes, say $n$. If we connect all these nodes with each other by links (which is to say that every pair of nodes is connected with probability $1$), then we would get what is known as a Complete graph of size $n$. This graph contains $\frac{n(n-1)}{2}$ number of links (Prove!). But instead of connecting every node to every other node, in an ER graph, every pair of nodes is connected with probability $p$ which, in general, is not equal to $1$ (The graph has become random!) Thus the average number of links in the ER graph is $p\frac{n(n-1)}{2}$. The number of nodes which a particular node is connected to is called the degree of that node. Now it is easy to see that the average degree of any node in the ER network is $p(n-1)$ which for a large graph can be approximated to $pn$. We can see that $p$ is the parameter of ER model and it controls the number of links and the average degree of the nodes.

How do we describe the ER graph mathematically? To be concrete, let us say that we actually start with some $n$ number of vertices and we also fix the value of $p$. After going through the whole procedure of construction, we would indeed get an ER graph. As mentioned in the second article, we can store the resulting structure in an adjacency matrix. But now suppose we repeat the whole process again with the same $n$ and $p$. We would get another ER graph. Would this graph be exactly the same as the one we constructed just before? Of course not! After all, the links would have been drawn randomly and hence if you consider the adjacency matrix of this graph, it ought to be different. Does this mean that these two 'realizations' of an ER graph are completely different? No! As emphasized in the second article, only the statistical properties of the network are of real importance. If we make, say, $1000$ such realizations with same $n$ and $p$, then these would have different adjacency matrices, in general. But for example if we calculate the average degree for each of these, it would be very close to $pn$. In this sense, all these graphs are only 'realizations' of the ER graph with a particular set of parameter values and are the same in the statistical sense. Thus, henceforth, when we say that a particular ER graph (in fact any big network) has a certain property, it would mean that that property is the average of the properties of a large number of realizations.

Just like an average degree, a very important statistical property of networks is the 'Degree distribution'. Consider a particular realization of the ER graph. We can actually count, for that realization, the number of nodes with degree $k$ where $k=0,1,2,...$. If we divide these numbers by $n$, the total number of vertices, then we get the probabilities that a randomly chosen node in this graph has degree $k$ (Am I right?). Now we consider the average of these probabilities over a large number of realizations. Let us denote these averaged probabilities by $p(k)$. This function of the discrete variable $k$ (which is a degree) is called the 'Degree distribution' of the network. Take it very seriously because this is perhaps the most important statistical property used to describe networks. In the next article, we will derive the exact form of $p(k)$ for the ER graph (Go ahead and try it for yourself if you want!) and some of the most peculiar properties of the ER model.

Thanks for your response. Some feedback is expected as well. :-)