American Institute of Mathematics, San Jose, California
Yuliy Baryshnikov, Francis Bonahon, and Edmond Jonckheere
The workshop has two main goals. One is to publicize the wealth of information accumulated by the mathematical community in the general areas of negatively curved spaces and geometric group theory, and to bring this scientific corpus to the attention of network scientists. The other goal is to give to the latter community a chance to educate mathematicians about the challenges arising in real-life large-scale networks, in particular about those that could be addressed in terms of asymptotic geometry.
The hop-distance metric, or some weighted version of it turns the network into a metric space. Rescaling and focusing on the Gromov-Hausdorff limits of the corresponding spaces then provides information on the large-scale geometry of the network. We are particularly interested in the cases where these geometries have negative curvature, such as Gromov hyperbolicity or CAT(-r) comparison properties, and on the potential implications of these properties for the networks considered.
The main themes of the workshop will include:
It is relatively easy to prove general theorems (e.g. on routing and traffic on large-scale networks) if one models the geometry of a network on a (classical, homogeneous) hyperbolic space, or on the Cayley graph of some group acting on a hyperbolic space. Softening the setup to Gromov hyperbolic spaces, or to some other comparison geometry, makes the underlying mathematics far more challenging. The fact that actual networks are finite is another challenge.
Some of the key real-life processes that arise in networks are transport phenomena: networks carry along information, or goods. We will explore the ways in which these problems can be modeled, for instance through the use of so-called mm-spaces. A point of particular interest is the emergence of a highly congested core in the network, and the need for a better understanding of this core. Percolation and epidemic processes on networks provide another rich area to investigate.
Many important spectral properties of graphs do not correlate well with their large scale geometry (for instance, exhausting families of subgraphs can have spectral properties very different from their union). It would be desirable to reach a better understanding of the spectral behavior of growing sequences of graphs.
The cones at infinity of hyperbolic spaces carry a lot of information about the underlying spaces. A discussion theme will be to understand how the geometry at infinity of a space interacts with the properties of large networks converging to this space.
An important part of the agenda will be to discuss how close some real-life networks are to hyperbolicity. In particular, one goal is to figure out benchmarks that will test the validity of the approaches discussed in the workshop.
The workshop schedule.
A report on the workshop activities.
Papers arising from the workshop: