Physics and Geometry of Large Networks

When: Wednesday, February 27, 2013 at 3:00 pm
Where: DA 114
Speaker: Dmitri Krioukuv
Organization: Senior Research Scientist, Cooperative Association for Internet Data Analysis (CAIDA), University of California San Diego (UCSD)
Sponsor: Physics Colloquium

Large networks of different types permeate many aspects of daily human life, yet it remains unclear if there exist any universal laws of network dynamics. Certain structural and dynamical similarities found in many different networks suggest that such laws might exist, but differences are so abundant, and details are so often important, that the search for these laws looks like an impossible adventure. In this search one enters a territory with many unknowns. Many pieces an unknown puzzle are scattered around.

Surprisingly, random geometric graphs in hyperbolic spaces helped to glue many of these pieces together, resulting in a number of unexpected “coincidences”. To name just a few examples: these graphs reproduce common structural properties of many real networks including self-similarity and scale-invariance, they generalize many popular random graph models, they are maximally navigable (most conductive with respect to transport processes common to many networks), they provide a lucid interpretation of auxiliary fields in exponential random graphs (Boltzmann ensembles of graphs maximizing Gibbs entropy under certain constraints), their dynamic version generalizes preferential attachment, casting it as a consequence of underlying optimization-driven dynamics, and this dynamics turns out to be the same as the dynamics of causal sets (quantizations of Lorentzian manifolds) in asymptotically de Sitter spacetimes, such as the spacetime of our accelerating universe.

I will review some of these pieces and connections between them. Many pieces are still missing, and many holes in the puzzle remain, awaiting to be filled.