### Constructing and sampling graphs with a prescribed joint degree distributionConstructing and sampling graphs with a prescribed joint degree distribution

Access Restriction
Subscribed

 Author Stanton, Isabelle ♦ Pinar, Ali Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2012 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Graphs ♦ Monte Carlo Markov chain ♦ Graph sampling ♦ Joint degree distribution Abstract One of the most influential recent results in network analysis is that many natural networks exhibit a power-law or log-normal degree distribution. This has inspired numerous generative models that match this property. However, more recent work has shown that while these generative models do have the right degree distribution, they are not good models for real-life networks due to their differences on other important metrics like conductance. We believe this is, in part, because many of these real-world networks have very different joint degree distributions, that is, the probability that a randomly selected edge will be between nodes of degree $\textit{k}$ and $\textit{l}.$ Assortativity is a sufficient statistic of the joint degree distribution, and it has been previously noted that social networks tend to be assortative, while biological and technological networks tend to be disassortative. We suggest understanding the relationship between network structure and the joint degree distribution of graphs is an interesting avenue of further research. An important tool for such studies are algorithms that can generate random instances of graphs with the same joint degree distribution. This is the main topic of this article, and we study the problem from both a theoretical and practical perspective. We provide an algorithm for constructing simple graphs from a given joint degree distribution, and a Monte Carlo Markov chain method for sampling them. We also show that the state space of simple graphs with a fixed degree distribution is connected via endpoint switches. We empirically evaluate the mixing time of this Markov chain by using experiments based on the autocorrelation of each edge. These experiments show that our Markov chain mixes quickly on these real graphs, allowing for utilization of our techniques in practice. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2012-09-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 17 Page Count 25 Starting Page 3.1 Ending Page 3.25

#### Open content in new tab

Source: ACM Digital Library