Detection of topological patterns in complex networks: correlation profile of the internet

Abstract

A general scheme for detecting and analyzing topological patterns in large complex networks is presented. In this scheme the network in question is compared with its properly randomized version that preserves some of its low-level topological properties. Statistically significant deviation of any topological property of a network from this null model likely reflects its design principles and/or evolutionary history. We illustrate this basic scheme using the example of the correlation profile of the Internet quantifying correlations between degrees of its neighboring nodes. This profile distinguishes the Internet from previously studied molecular networks with a similar scale-free degree distribution. We finally demonstrate that the clustering in a network is very sensitive to both the degree distribution and its correlation profile and compare the clustering in the Internet to the appropriate null model.