Complex Networks

The most famous network today is probably Internet. The figure on the right shows the map of Internet routers as obtained in 2005 by the Opte project. The intricacy of the structure can be immediately appreciated. This map of Internet plotted as a graph is a way to represent a complex system, in which the nodes correspond to the basic elements (routers in this case) and the links to the relations between them (physical connections).

The idea of using graphs as mathematical tools to characterize real world systems is quite old, going back to Euler and the problem of the bridges of Königsberg.

Graphs can be in general use to represent Complex Systems where many elements are interacting between them. The nodes correspond to elements and the links to pairwise interactions.

An example can be seen on the left. The network is the so called Zachary karate club for which nodes are people since these data proceeds from a sociological study. Students, teachers and administrators of a college karate club that suffered a strong conflict that led to the club excision in two groups. Node colors in the graph describe the final faction of each individual.

The Zachary club network has become in clustering literature a classic for the use of graphs
in understanding social conflicts. The graph representation permits to put the question of
finding the groups after the excision in a sound mathematical form. Given the graph of interactions,
are we able to find structure in it? Do such structures reflect real world processes underlying the
evolution of the whole system?

These are the type of questions that, in a more general framework, are faced in the section
of my work titled Network Structure Inference.

Back