Complex Networks

We define a complex network as a set of nodes and links. This sounds hard to understand but it is quite the opposite. For instance, you might have heard about the concept of social network. A social network is a representation of the relationships among people. Each individual is a node and two nodes are connected by a link if they know each other. Think about you and your friends and family. Your relationships with them construct your social network. Each one of you is a node of the network and each relationship is a link.

The basis of complex networks can be understood from that simple example. Now, you change people for web pages and relationships for hyperlinks and just like that, you have the World Wide Web. Something similar for airports and the different flights connecting them, or neurons and their interactions. Just like complex systems, you can find complex networks everywhere!

We can classify complex networks according to different aspects such as the type of connection between nodes. Links can be directional. A network with this characteristic is said to be directed. Think about a food web where the nodes correspond to the different species, and the links connect them if they are predator and prey. But bear in mind this is a directional relationship. For instance, a rabbit eats grass but the opposite does not occur. We represent this with an arrow pointing from the plant to the animal. On the other hand, in an undirected network the relationship between nodes holds in both directions. It is the case for a network of actors (and/or actresses) with a link connecting them if they work together in a film.

Complex networks can be characterized and studied using some basic concepts. The most important one is probably the degree distribution. This is just the indicator of each node's number of links, namely its degree. It is what makes one node stand out from the others. The higher the degree, the higher its ability to infer changes in the whole network.

Another key concept is the path length between nodes. It is defined as the number of links between them. There are some concepts related to this one like the shortest path length, which is the minimum number of links connecting two nodes. Besides, we can average this over the whole network to get the characteristic path length

As an example of a complex network, check the image below.

The picture is a representation of a very small and fictional social network. By taking a quick look at it, you will realize that Lily is the one with a higher number of friends (links). Four to be exact. That is the same as saying she has degree 4. Therefore, she is the one with the most power to influence the rest of the group. She has a friendship relation with everyone but Albert. Even though they don't know each other, there are only two links separating them because they have Jim (and Carly) as a mutual friend. This implies that the shortest path length between them is 2.

With these concepts, we can study different events happening in the network. For instance, we can determine how long will take for a rumor to spread and reach every node of the net. Among other things, it will depend on how many connections has the individual who starts the rumor. Instead of this, imagine the network is affected by a disease. Then, the distribution of connections is crucial in determining the spreading of the disease and also in trying to stop it from becoming a pandemic.

There are plenty more definitions to describe complex networks but we think this is enough for an introduction to the subject. 

Historical background:

Mathematicians use the term graph instead of network. It all started with The Seven Bridges of Königsberg (Kaliningrad). This city is divided by the Pregel River in such a way that there are four regions connected by a total of seven bridges. The aim of the problem was to find a walk through the city that would cross each one of the bridges only once.

You can try to solve the problem, but don't spend too much time on it... Euler proved it has no solution and his technique is considered the starting point of Graph Theory.

Further knowledge:

In the following video, we show you a computer simulation of a complex network. Initially, there are only three nodes and, as time passes, we add more nodes, connecting each one of them to two of the nodes already present. The “preferential attachment” concept is that new nodes will connect to those with a higher number of links. This gives rise to a Scale Free Barabasi-Albert network with a power law degree distribution.