The Mathematical Challenge of Large Networks

It is becoming more and more clear that many of the most exciting structures of our world can be described as large networks. The internet is perhaps the foremost example, modeled by different networks (the physical internet, a network of devices; the world wide web, a network of webpages and hyperlinks). Various social networks, several of them created by the internet, are studied by sociologist, historians, epidemiologists, and economists. Huge networks arise in biology (from ecological networks to the brain), physics, and engineering.

These networks pose exciting and challenging problems for the mathematician: these networks are never completely known, and indeed often not even completely defined. At any time, we can only have partial information about them, through sampling locally, or observing the behavior of some global process.

The approach to the study of such networks includes finding procedures (usually
randomized) that produce networks with similar behavior; this relates to the theory of random graphs and randomly growing graphs, and the theory of „Property Testing” in computer science. The methods involve defining a “distance” between two large graphs, defining when a growing sequence of graphs is convergent, and assigning limit objects to such sequences.

The limit theory allows us to answer some basic questions both in theory and practice. For example, in extremal graph theory: Which inequalities between subgraph densities are valid? Can these be proved using just Cauchy-Schwarz? is there always and extremal graph, and what is the possible structure of these?

The limit theory has been developed by Borgs, Chayes, Lovasz, Sos, Szegedy and Vesztergombi in the dense case, and by Aldous, Benjamini, Schramm, Elek and others in the sparse case.