The physics of networks

In its simplest form, a network is a collection of points, or nodes, joined by lines, or edges. As purely theoretical objects, networks have been the subject of academic scrutiny since at least the 18th century. But they have taken on a new practical role in recent years as a primary tool in the study of complex systems—real-world systems of interacting components, for which networks provide a simple but tremendously useful representation.1 The internet, for example, can be represented as a network of computers linked by data connections. The World Wide Web is a network of information stored on webpages and connected by hyperlinks. Social networks of friendships between individuals have received a lot of recent attention, and other kinds of social networks, such as those of professional or business contacts, are also attracting their share of interest. Biological networks, such as the interrelated metabolic reactions that run the cell or the food web of predator–prey relations in an ecosystem, are of interest in both experimental and theoretical biology. And networks are increasingly common in the study of epidemiology, computer viruses, computer software, genetics, human transportation and communication, human language, books, movies, music, and many other things. But how do physicists enter the picture?

Physicists’ interest in networks is relatively recent. Progress in the first 200 years of the field was mostly the work of mathematicians and social scientists. Leonhard Euler is often credited with the first rigorous result in graph theory (the mathematical study of networks), with his solution of the famous Königsberg bridge problem in 1765. Kenneth Appel and Wolfgang Haken’s 1976 proof of the four-color theorem—that four colors are sufficient to color any map in such a way that any two adjacent regions are of different colors—is perhaps the best known recent achievement of graph theory. The empirical study of networks, meanwhile, has its foundations in sociology, in which researchers have been studying social networks since the 1930s.

Interest in networks has, however, seen its most spectacular growth in the past 10 years, with much of the fundamental research in the area being conducted, perhaps surprisingly, by physicists, whose methods turn out to be well suited to the problems of the field. The approach taken by physicists differs from those of mathematicians and sociologists in two important ways. First, unlike most mathematical work, it is founded on and largely inspired by empirical studies of real-world networks such as the internet, friendship networks, and biological networks. One reason for the subject’s rise in popularity has certainly been the increased availability of accurate and substantial network data sets.

Second, unlike most sociologists, physicists have been concerned largely with statistical properties of networks—their overall shapes and statistical signatures—rather than with properties of individual nodes or groups of nodes. Whereas a sociologist might have asked, “Which nodes in this network have the most connections?” a physicist might ask, “What is the average number of connections a node has?” or, “What is the distribution of the number of connections?” In asking those questions, physicists have stumbled across a number of intriguing network properties, mostly unremarked in earlier work, that have inspired an impressive array of new theories, techniques, algorithms, models, and measures to describe and illuminate the function of networked systems. Physicists are by no meansthe only contributors to the outpouring of new work—mathematicians, computer scientists, social scientists, biologists, and many others have made fundamental contributions—but physicists have played a central role, and physics journals have published much of the foundational work in the field.

[Taken from Physics Today November 2008 p33]