The density signature

Graduation date: 2014Access restricted to the OSU Community at author's request from June 2, 2014 - June 2, 2015In real networks, identifying dense regions is of great importance. For example, in a network that represents academic collaboration, authors within the densest component of the graph tend to be the most prolific. Dense subgraphs often identify communities in social networks. And dense subgraphs can be used to discover regulatory motifs in genomic DNA.\ud \ud We present a new topological property, the density decomposition, that identifies regions of uniform density in networks. We obtain the density decomposition by orienting a graph so that each vertex has a fair share of edges directed into it. We then partition the vertices into rings based on how many edges each vertex has directed into it. From the density decomposition we can immediately isolate all vertices that may be in any densest subgraph. We summarize the density decomposition with the density signature, a count of how many vertices are in each ring.\ud \ud In real graphs, the density signature is very similar to the degree distribution. However, this is not the case in existing random graph models. No existing random graph model generates graphs that achieve realistic density signatures. We use the density signature as a framework for new random graph models. We find that our models based on the density signature are competitive in achieving realistic degree distributions, clustering coefficients, and average path lengths