Center for Applied Mathematical Sciences Visit USC
USC Donrsife Homepage
Oct 09
3:30 PM - 4:30 PM KAP 414
Hyperbolic geometry of complex networks
Dmitri Krioukov CAIDA, San Diego

We establish a connection between observed scale-free topology and hidden hyperbolic geometry of complex networks. The topologies of many complex networks in nature and society (biological networks, the Internet, social networks, etc.) share two common properties:
(1) strong clustering, i.e., high concentration of triangular subgraphs, and (2) heterogenous (scale-free) node degree distributions, which often closely follow power laws. We show that these two common topological properties of complex networks can be explained by the existence of hidden spaces, which are: (1) metric, and (2) hyperbolic. Strong clustering in a network appears as a reflection of the triangle inequality in its hidden space, while the negative curvature of this hidden space affects the heterogeneity of the degree distribution. We also discuss implications for transport phenomena on networks, such as routing. Embedding a real scale-free network into an appropriate hyperbolic space allows for efficient geometric routing without global knowledge of the network topology, which holds a significant promise to find a variety of practical applications, such as improving the performance of Internet routing.

Previous colloquium: On the Problem of Wing Flutter Instability in AeroElasticity Next colloquium: Optimization without derivatives: consensus and controversies