Structural Sparsity of Complex Networks: Random Graph Models and Linear Algorithms.

Abstract

This research aims to identify strong structural features of real-world complex networks, sufficient to enable a host of graph algorithms that are much more efficient than what is possible for general graphs (and currently used for network analysis). Specifically, we study the property of bounded expansion—roughly, that any subgraph has bounded average degree after contracting disjoint bounded-diameter subgraphs—which formalizes the intuitive notion of “sparsity ” well-observed in real-world complex networks. On the theoretical side, we analyze many previously proposed models for random net-works and characterize, in very general scenarios, which produce graph classes of bounded expansion. We show that, with high probability, (1) Erdős–Rényi random graphs, generalized to have non-uniform edge probabilities and start from any bounded-degree graph, have bounded expansion; (2) the Molloy–Reed configuration model—matching any given degree sequence including “scale-free ” networks given by a power-law degree sequence—results in graphs of bounded expansion; and (3) the Kleinberg model and the Barabási–Albert model, in fairly typical setups, do not result in graphs of bounded expansion.