Universality for distances in power-law random graphs

Universality for distances in power-law random graphs

Van der Hofstad, R.
Hooghiemstra, G.

Electrical Engineering, Mathematics and Computer Science

Delft Institute of Applied Mathematics

2008-12-12

We survey the recent work on phase transition and distances in various random graph models with general degree sequences. We focus on inhomogeneous random graphs, the configuration model, and affine preferential attachment models, and pay special attention to the setting where these random graphs have a power-law degree sequence. This means that the proportion of vertices with degree k in large graphs is approximately proportional to k?? for some ?>1. Since many real networks have been empirically shown to have power-law degree sequences, these random graphs can be seen as more realistic models for real complex networks than classical random graphs such as the Erd?s–Rényi random graph. It is often suggested that the behavior of random graphs should have a large amount of universality, meaning, in this case, that random graphs with similar degree sequences share similar behavior. We survey the available results on graph distances in power-law random graphs that are consistent with this prediction.

complex networks
graph theory
phase transformations
random processes

http://resolver.tudelft.nl/uuid:fccdd752-4b9e-4ff8-827c-ba14709cde31

https://doi.org/10.1063/1.2982927

American Institute of Physics

0022-2488

http://link.aip.org/link/JMAPAQ/v49/i12/p125209/s1

Journal of Mathematical Physics, 49 (12), 2008

Institutional Repository

journal article

(c) 2008 Van der Hofstad, R.; Hooghiemstra, G.; American Institute of Physics