Topological structural classes of complex networks

Abstract

We use theoretical principles to study how complex networks are topologically organized at large scale. Using spectral graph theory we predict the existence of four different topological structural classes of networks. These classes correspond, respectively, to highly homogenous networks lacking structural bottlenecks, networks organized into highly interconnected modules with low inter-community connectivity, networks with a highly connected central core surrounded by a sparser periphery, and networks displaying a combination of highly connected groups (quasicliques) and groups of nodes partitioned into disjoint subsets (quasibipartites). Here we show by means of the spectral scaling method that these classes really exist in real-world ecological, biological, informational, technological, and social networks. We show that neither of three network growth mechanisms—random with uniform distribution, preferential attachment, and random with the same degree sequence as real network—is able to reproduce the four structural classes of complex networks. These models reproduce two of the network classes as a function of the average degree but completely fail in reproducing the other two classes of networks.