Waste less time on Facebook — follow Brilliant.

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. :-)

Note by Snehal Shekatkar
2 years, 10 months ago

No vote yet
1 vote


Sort by:

Top Newest

This is truly a beautiful article....Neat and very precise......Thank you Snehal Shekatkar. Samarth M.O. · 2 years, 9 months ago

Log in to reply

I am a big fan of this series, thank you Snehal. I was just wondering whether you might write a touch more about the analysis we can do on some specific examples? Although of course i understand that you have to lay the groundwork with terminology and basic properties first. Do you have an estimate on the date of #4? Josh Rowley · 2 years, 9 months ago

Log in to reply

@Josh Rowley I have already published 5 of them.. just click on the complex network tag below the article.. Snehal Shekatkar · 2 years, 9 months ago

Log in to reply

is there any relation between complex network and classical physics (especially classical mechanic)? Johan Setiawan · 2 years, 9 months ago

Log in to reply

@Johan Setiawan I understand your point.. at first sight this doesn't seem to be physics at all.. ;-)

But the point of physics is to describe the world around you and in this sense all physical sciences including chemistry and biology are just branches of physics. When we talk about 'complex systems' in general then we actually try to find out generic properties: the properties which would be common to many, seemingly different, systems. Thus you can have collection of harmonic oscillators as one complex systems and group of biological cells as another complex system. One can go ahead and try to describe oscillators using classical mechanics and cells using biological mechanisms. But if we follow the network approach then it may reveal properties which are common o both and then we may realize that these systems are actually not that different. Hence if we find something in oscillator model (which we solved using classical mechanics for example), we will directly reveal something very important about biological cells!

Just to make you happy, let me tell you that we use classical mechanics heavily in the theory of networks and nonlinear dynamics.. :-) Snehal Shekatkar · 2 years, 9 months ago

Log in to reply

I am extremely grateful to Mr. Pradeep Thakur for reading the draft of the article carefully and correcting many syntax errors. Snehal Shekatkar · 2 years, 10 months ago

Log in to reply

So, in case of an ER graph, we are not really interested in the adjacency matrix of each ER graph; what we are really interested in knowing is the average of all possible ER graphs? And is average ER graph sufficient to describe all statistical properties of the network?

I know this may be asking too much but small examples shall do good and make this series much more interesting. (my personal opinion)

Thanks for #3 Sir!

P.S. Will the derivation of exact form of \(p(k)\) make use of advanced mathematics? Kou$htav Chakrabarty · 2 years, 10 months ago

Log in to reply

@Kou$htav Chakrabarty As I already pointed out couple of times, only important properties of networks are their statistical properties and ER model is not an exception. Later we will study other models of graphs and even for them, statistical properties like degree distribution' would be most important. Its not that adjacency matrix is of no importance at all. Adjacency matrix is perhaps the only way to describe a particular realization of model. But surely we don't expect that all ER graphs with different adjacency matrices would have different properties. We will give some concrete examples in future articles so that you will understand this fully.

Derivation of \(p(k)\) makes use of simple combinatorics so just try it! Snehal Shekatkar · 2 years, 10 months ago

Log in to reply

@Snehal Shekatkar I intend to revisit this article sometime later when I see the examples :) Thanks! Kou$htav Chakrabarty · 2 years, 10 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...