Density decompositions of networks

Abstract

We introduce a new topological descriptor of a graph called the density decomposition which is a partition of the vertices of a graph into regions of uniform density. The decomposition we define is unique in the sense that a given graph has exactly one density decomposition. The number of vertices in each partition defines a density distribution which we find is measurably similar to the degree distribution of given real-world networks (social, internet, etc.) and measurably dissimilar in synthetic networks (preferential attachment, small world, etc.). We also show how to build networks having given density distributions, which gives us further insight into the structure of real-world networks.