Waste less time on Facebook — follow Brilliant.

Complex Networks 2

This article assumes that you have already read the first article.

As promised in the first article, I will now try to describe meaning of network or graph. Mathematically, network is simply a set of points (called vertices or nodes) connected by line segments (called edges or links) to each other.



Figure 1

How such a naive looking structure of nodes and links can help us in studying extremely complicated systems which were described in first part of this article? To answer this, let us look at some specific physical systems. As already said, our brain is an extremely complicated system but after all it is made up of units called neurons which are connected with each other! So the whole brain can be represented as a picture shown in Figure 1). We can think of neurons as some kind of nodes and if two neurons are connected then we will show that by a link between those nodes. The whole brain is a network in which neurons are nodes and connections between them are links! As a second example, consider our society. We can represent every person in the world by a node and if two persons know each other, we will draw a link between corresponding nodes. The whole society is a complex network! As a third example consider world wide web, a system consisting of web-pages. Everybody who is using Internet knows that to land on a particular page, you don't always have to type the address of that page in our browser. Instead, we usually navigate from page to page using hyperlinks. Thus, it is easy to see that the whole world wide web is nothing but a big complex network in which web-pages are nodes and hyper-links are links between these pages. There is a countless number of complex networks around and inside us and we are part of many of them! You can try to amuse yourself by trying to find more examples. (Post them below if you find!).

Historically, concept of graph or network came from great mathematician Leonhard Euler while he was trying to solve the "Seven bridge problem". This is a really interesting story and you must read it.

Now to the mathematics of the networks! We have already introduced the terms 'nodes' and 'links' and I will stick to them. The structure of a network describing a particular complex system can be very different than other networks which describe different physical systems. Even when systems are same, we can't expect exactly same type of connections among the nodes. For example, the detailed structure of connections among neurons for two different persons would be very different. What really matter are the statistical properties of these systems. If the statistical properties of two networks are same, then we will say that they have same 'topology'. (Sometimes, the word 'same topology' is also used to indicate that networks have exactly same structure). Now let me tell you an efficient way to store the topology of a given network (we can't use pictures of networks every time!). Suppose in a given network, there are \(n\) nodes and we number them as \(1,2,...,n\). Now consider \(n\times n\) matrix. In our network, if node \(i\) is connected to node \(j\), then we will make \((i,j)\)th entry of this matrix equal to \(1\), otherwise we will make it \(0\). This matrix is called 'Adjacency matrix' or 'Connectivity matrix' of the network. The whole information about topology can be stored in adjacency matrix and this makes theoretical and computational analysis of structure of networks way too easy!

In the next article, l will introduce a special network called ER network and related ideas. Please feel free to ask any questions about the ideas which I have presented so far. Also if there is any issue with the way I am presenting, please let me know. Thank you for your response. :)

Note by Snehal Shekatkar
2 years, 10 months ago

No vote yet
1 vote


Sort by:

Top Newest

Find the third article of this series Here Snehal Shekatkar · 2 years, 10 months ago

Log in to reply

Ya Its a gd Article.. Krishna Jyotish · 2 years, 9 months ago

Log in to reply

Sir, I hope you are continuing this series! I and many others(I guess) probably want #3 ;) Kou$htav Chakrabarty · 2 years, 10 months ago

Log in to reply

@Kou$htav Chakrabarty Yes.. soon I will upload 3rd article. Somehow I didn't see the kind of response that I got for my first article. Thank you for your response by the way! :-) Snehal Shekatkar · 2 years, 10 months ago

Log in to reply

@Snehal Shekatkar Maybe it's possible that all those who responded in #1 are also waiting but are not asking explicitly like I did :-)

But I find #2 more interesting as it involves more technical details (and also 'little' bit maths). Kou$htav Chakrabarty · 2 years, 10 months ago

Log in to reply

Thanks for #2!

So, for the adjacency matrix \(A_{m \times n}\), if the \((m_{i}, n_{j})\) and \((m_{k}, n_{l})\) are two nodes and have link between them, then why do we decide to make the element themselves equal to 1?

For example, if \((m_{i}, n_{j})\) is linked to \((m_{k}, n_{l})\) but not related to \((m_{o}, n_{p})\), then if we consider only \((m_{i}, n_{j})\) and \((m_{o}, n_{p})\), then \((m_{i}, n_{j})\) has a value 0 but if \((m_{i}, n_{j})\) and \((m_{k}, n_{l})\) are considered, \((m_{i}, n_{j})\) has a value of 1.

Have I misunderstood you somewhere? Kou$htav Chakrabarty · 2 years, 10 months ago

Log in to reply

@Kou$htav Chakrabarty I think you misunderstood this.. we label each node in the network by a single index, we don't specify \((x,y)\) coordinates or something.. that doesn't make sense most of the time. So as per your notation, there will be nodes \(m\) and \(n\). Now if these two nodes are connected, then \((m,n)th\) entry of \(A\) would be \(1\), if they are not connected then this entry would be \(0\). Hope this answers your question. :) Snehal Shekatkar · 2 years, 10 months ago

Log in to reply

@Snehal Shekatkar Oh! That clears it. Thanks! Waiting for #3.

That means in my above question if \(m^{th}\) and \(n^{th}\) node are connected, that makes the \((m,n)^{th}\) element in the adacency matrix 1. If the \(m^{th}\) and \(p^{th}\) nodes are not connected, that makes the \((m,p)^{th}\) element 0. Kou$htav Chakrabarty · 2 years, 10 months ago

Log in to reply

@Kou$htav Chakrabarty Exactly! :-) Please keep resharing.. Snehal Shekatkar · 2 years, 10 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...