Introduction to Network Theory

Modern network theory was introduced at the end of the nineties by the PhD student Reka Albert and then monopolized by her tutor L.A. Barabasi, who made an empire out of it.

The idea was not new, network theory is based on graph theory and graph theory had been already introduced by Euler in 1736, in order to solve the popularly known problem of the seven bridges of Königsberg. Well, the thing is, at that time the king wanted to make a parade crossing all the seven bridges without passing by the same street more than once and the great genius of Euler solved maybe the first optimization problem by translating a metrical problem in a topological one, that is to say a problem dealing with relationships. After that, graph theory developed as a branch of math. Then there was also Prim in 1957, he found exactly the same model that is now well known as the Barabasi-Albert model, but nearly nobody took notice about it. You wonder why? Easy enough to say, the internet was not around then, and yes, thirst thing Barabasi did was to forecast the diameter of the whole internet, not only that, he did it right.

However, if you are reading this article is because you don’t know a lot about the theory of networks, and I’m just talking about history as if the main heart of the thing was already known. But let me follow just a bit on this line and I swear you’ll get what you want or at least a bite of it!

So well, we are at the end of the nineties and a Rumanian guy says he can theoretically calculate the diameter of the internet. What happens is, a total madness starts going on. An uncountable number of scientist and enterprises turn their head towards Boston and a whole new theory gets structured in a handful of years. General relativity, quantum theory, string theory, the big bang, not one within those got so much attention in terms of the number of citations, scientific papers published, media, international conferences, funds, brand new research centers. You might be thinking, well that is the internet power, load of dough in it, and this is partly true, but it is not the whole cake. Network theory showed to be useful in order to describe a huge number of phenomena, with the same set of tools (take notice, I said to describe, not to explain, but the difference sometimes is feeble and you might get used not to think much about it). Social physics, genetics, linguistics, semantics, geography, history, urbanism, microbiology, and many other disciplines. And then the applications in medicine, policy, security, mobile technologies, control, classification, and so on.

Network theory in the real world

Let’s see why and how network theory could have such an impact in the world. A network in its simplest form is a set of elements (nodes) related by links. As a network is not generally embedded in a geographical space, we do not talk about the geometry of a network, but about topology, which we can look at as to a geometry of relationships. Each different network has a different topology, which is the result of that special kind of relationships that grow within its elements. In the internet, for example, the nodes are the servers, and the links the connections between them. In the WWW, the nodes are the pages, the relationships the hyperlinks between them. The example of the social networks is well known for the topic of the six degrees of separation and the small world phenomena. Protein networks can be built connecting all those proteins that share some attributes, such as functional groups. Network theory is now central in the research for the production of enzymes. Emails can be the nodes of the network and the relationship imposed if the semantic content shows a certain degree of similarity and this goes well with big data semantic analysis. Whatever system you could possibly imagine made by objects related to each other, than it can be turned into a network. The nodes can be single elements or they can carry a set of information (content-based networks), the links can be simple relationships, but they also can be weighted, directional, etc. Different networks can be related to each other, forming multilayers networks.

Figure 1: a portion of the minimum spanning tree of the network representing the Semantic Space in the neighbourhood of the word Nature. Vertices are Wikipedia pages and links represent semantic relations between the two pages. Different colors represent different semantic clusters.

Once you have your network, first thing you observe is its topology, that will tell you which kind of phenomena the network belongs to (it might be random, but it might come from different strategies of aggregation and all this you can get it from its topology!). And then there are a load of network metrics to apply in order to classify, cluster, categorize the elements of your network. Many metrics are problems related, but the most used ones are the degree (the number of connections each node has), the clustering coefficient (how much clustered is your surrounding), the betweeness centrality (how many shortest paths between nodes pass through one node), and many others. For big data you can easily find hot spots, important links of information flow, segregated areas, topic related clusters, etc.

Well, I guess you already got an idea on how all the fuss about network theory, now that big data analysis is central, smart whatever, AI and so on. Network theory in a few years became central in scientific research and technological application. It was not rare to see members of intelligence or also ministers of different countries trying to grab what they could during international conferences.

L.A. Barabasi indulged himself confessing of (and also being proud of) having helped USA intelligence in finding the hidings of Saddam Hussein during the Gulf war thanks to the study of his social network!