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.

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