Let’s now consider a real network. The Internet is a very complex system and its rapid growth makes its graph representation very interesting, from a topological point of view. Many projects tried to map the Internet and this implies all kinds of difficulties. DIMES project has the peculiarity of being a collective effort, it is a distributed scientific research project, aimed to study the structure and topology of the Internet, with the help of a volunteer community. What you have to do to participate and become an Active Agent is to download a small program that will run in the background of your computer, consuming very little resources. The network considered for this post is the result of the data gathered from 2004 to 2007, it has 34563 vertices and 62960 edges, with a maximum degree of 2897. In particular this is the Autonomous System (AS) level of the Internet network. Each vertex represents an autonomous system and each edge is a connection between two AS. That is why it may seem small, but every vertex is a collection of routers and networks under the same domain or administrative entity.
I already mentioned here the first characteristic of complex networks, the scale invariance with the typical power-law distribution of degrees. We can see in the picture above that in this case we have indeed a power-law with an exponent of 2.5 and a long exponential tail.
We observed here that for a random graph we have a Poisson distribution of degrees and consequently an homogeneous topology. We may expect now something quite different. How does this k-cores decomposition look like? We can see below in red the distribution of vertices, and in blue the edges, that is the number of vertices and edges in each shell. It seems the opposite of what we saw for random graphs. Most vertices are in the lower shells, and few are very connected. The number of elements in each shell decreases with k. In particular the number of vertices decreases with k following a power-law with an exponent of 2.7.
In the figure below these characteristics become even more clear. This very nice image is obtained with the LaNet-vi visualization tool, mentioned in the previous post and described here. The size of a vertex represents its degree and the color represents its coreness value (or the shell where the vertex is). This graph has clearly an heterogeneous topology, there is an evident hierarchy, most vertices are in the lower shells, pink and purple, whereas a limited number of vertices has an important role in the network, in the center of the picture. These red vertices are called hubs and they have a very large number of connections. Emergence of hubs is a consequence of the scale-free property of networks. Hubs can be found in many real networks and have a significant impact on the topology, but they cannot be observed in a random network, as we already saw.
How this network would resist to damages and attacks? We already saw that removing a random vertex in a network with an homogeneous topology like a random graph we probably would not cause much trouble, because those vertices have a similar role in the network, they are interchangeable. Here instead, we have a group of nodes that are essential, without one of them we would probably find our network divided in disconnected components or clusters. Here of course, removing a random element means to touch more likely one of the less important vertices, but we have a part of the network very sensitive and an attack towards one of the red vertices would have serious consequences. This example of an highly hierarchical network shows us why local failures don’t usually lead to catastrophic global failures. Scale-free networks are resilient with respect to random attacks, whereas targeted attacks are very effective.
chaos like home 