Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00505
Density decompositions of networks
Glencora Borradaile, Theresa Migler, and Gordon Wilfong
Vol. 23, no. 4, pp. 625-651, 2019. Regular paper.
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.
Submitted: February 2018.
Reviewed: June 2019.
Revised: July 2019.
Accepted: July 2019.
Final: July 2019.
Published: September 2019.
Communicated by Ulrik Brandes
article (PDF)
BibTeX