Features of power-law random graphs

I. Norros (VTT Technical Research Centre of Finland) and H. Reittu, (VTT Technical Research Centre of Finland)

Random graphs with power-law degree distributions have become popular models of strongly inhomogeneous large networks. The most interesting case is obtained when the degrees follow a distribution with finite mean and infinite variance. This talk gives an overview of the remarkable features of such graphs:
(i) the existence of subgraphs with arbitrary edge densities,
(ii) the log log N scalability of typical distances with respect to network size N, where the density hierarchy plays a crucial role, and

(iii) the robustness of the structure with respect to loss of a high density part: the distances grow but the asymptotic relative size of the giant component remains unchanged.

Back