Introduction to the Physics of Complex Networks

veranstaltet von dem Arbeitskreis AKSOE

Introduction to the Physics of Complex Networks

Sonntag, 24. Februar, 14:00 Uhr, EW 203

The tutorial will give an introduction to the field of complex networks. It will show how multi-agent or many-particle systems coming from a variety of fields spanning the social and life sciences can be modeled as networks. Driven by an ever growing amount of empirical data, a number of surprising and interesting results have been obtained by physicists in recent years in this truly interdisciplinary field between discrete mathematics and statistical physics on the one hand, and sociology or biology on the other. They shall be reviewed in this tutorial.

Statistical mechanics traditionally studies many particle systems in which the specificities of the interactions between individual particles are unknown and – worse – unaccessible. For systems such as gases or solids, these details are even unimportant as many system level properties can still be obtained without their knowledge. In contrast, the real world is full of many-particle systems for which the interactions between individual particles are known and accessible. However, being markets, traffic and social networks or gene regulatory networks, such systems have not been traditionally studied by physicists. What makes them interesting is that for such systems the details of the network of interactions does matter for the determination of system level properties. Hence, there are a lot of fascinating phenomena to be explored and the talk will show how this can be done – even with the toolbox of statistical mechanics.

The tutorial will be divided into three parts. Part 1 will focus on the structure and topology of networks and introduce basic concepts of network and graph theory. Key results in the study of empirical networks will be reviewed and a number of important network models such as small world and scale free networks will be discussed. In particular, it will be shown that real world networks are wired far from randomly and how insights into the network generation process may be obtained by studying exactly these deviations from random behavior.

The second part will focus on dynamics on networks. In particular, it will address the intimate relation between the topology of a network and dynamical processes running on a network. Such processes include transport and regulation as well as spreading phenomena. For instance, it will be shown that the scale free topology of many real world networks has important implications for the spreading of diseases across these networks, such as the absence of an epidemic threshold. However, knowledge of these features also allows for the design of efficient immunization strategies and a few of these will be discussed.

The last part of the talk will be devoted to the large scale analysis of networks. While the first two parts have presented a treatment on the level of individual nodes, this last part will show that there exists a hierarchy of coarse structures in many real world networks. Nodes may be grouped into classes based on patterns in the connectivity of the network, and statistical mechanics provides the tools to detect such patterns. Such classes of similar connectivity often correspond to classes of similar function, and analyzing topology may hence provide insights into function. Market and protein interaction networks will give examples, and an excursion into the theory of optimization problems will provide an insight into possibilities and an outlook to the limitations of data driven research on networks.

References:
M. E. J. Newman, The structure and function of complex networks, SIAM Review 45, 167-256 (2003) S. Bornholdt, H.G. Schuster (Hrsg.): Handbook of Graphs and Networks. Wiley, 2003.

Jörg Reichardt
Institute for Theoretical Physics and Astronomy, University of Würzburg