COMPLEX NETWORKS

We review recent results obtained in empirical numerical and theoretical studies of complex networks that characterize many systems in nature and society. Examples are the Internet, the world wide web, and food webs, as well as networks of neurons, of the metabolism of biological cells, of transportation, of distribution, of citations and many more. The empirical and theoretical analysis of general complex networks has only recently been approached by physicists, seminal papers in this field dating from the late 1990s. In this course the perspective has moved from the analysis of single small graphs and properties of individual vertices and edges to the consideration of statistical properties of ensembles of graphs (networks). This induced the need for the introduction of methods as they are provided by statistical physics. In this review we sketch the evolution of network science and present some natural and man-made networks in detail, their main features and quantitative characteristics. Starting with three basic network models, the Erdos-Renyi random graph, the Watts Strogatz small world network, and the Barabasi Albert scale free network, we introduce the statistical mechanics of complex networks. We consider phase transitions and critical phenomena on complex networks and, in particular, we elaborate network phenomena that can be described in terms of percolation theory.