Sampling Graphs with a Prescribed Joint Degree Distribution UsingMarkov ChainsIsabelle Stanton∗Ali Pinar†UC Berkeley Sandia National Laboratories‡[email protected] [email protected] of the most influential results in network analysisis that many natural networks exhibit a power-lawor log-normal degree distribution. This has inspirednumerous generative models that match this property.However, more recent work has shown that while thesegenerative models do have the right degree distribution,they are not good models for real life networks dueto their differences on other important metrics likeconductance. We believe this is, in part, because manyof these real-world networks have very different jointdegree distributions, i.e. the probability that a randomlyselected edge will be between nodes of degree k and l.Assortativity is a sufficient statistic of the joint degreedistribution, and it has been previously noted thatsocial networks tend to be assortative, while biologicaland technological networks tend to be disassortative.We suggest that the joint degree distribution ofgraphs is an interesting avenue of study for further re-search into network structure. We provide a simplegreedy algorithm for constructing simple graphs froma given joint degree distribution, and a Monte CarloMarkov Chain method for sampling them. We also showthat the state space of simple graphs with a fixed degreedistribution is connected via endpoint switches. We em-pirically evaluate the mixing time of this Markov Chainby using experiments based on the autocorrelation ofeach edge.∗Supported by a National Defense Science and EngineeringGraduate Fellowship. Work performed while at Sandia NationalLaboratories, Livermore CA.†This work is supported by the DOE ASCR Applied Mathe-matics Program.‡Sandia National Laboratories is a multi-program laboratoryoperated by Sandia Corporation, a wholly owned subsidiaryof Lockheed Martin Corporation, for the U.S. Department ofEnergys National Nuclear Security Administration under contractDE-AC04-94AL85000.1 IntroductionThere have been numerous studies about the topolog-ical structures of real-world networks, from the Inter-net to social, biological and technological networks [6].One common result is the existence of power-law or log-normal distributions over many quantities and in par-ticular the degree distribution: the number of nodesof degree k is proportional to k−α. The ubiquity ofthis distribution has been a motivator for many dif-ferent generative models, like Preferential Attachment,the Copying model, the Barabasi Hierarchical model,Forest-Fire Model, the Kronecker Graph Model andGeometric Preferential Attachment [7, 16, 18, 27, 17].Many of these models also match other observed fea-tures, such as small diameter or densification [14]. How-ever, recent studies comparing the generative modelswith real networks on metrics like conductance showthat the models do not match other important featuresof the networks [19].Intuitively, if the degree distribution (DD) of agraph describes the probability that a vertex selecteduniformly at random will be of degree k then the jointdegree distribution (JDD) is the probability that a ran-domly selected edge will be between nodes of degree kand l. Graphs with the same degree distribution mayhave very different joint degree distributions. For ex-ample, the assortativity of a network measures whethernodes prefer to attach to other similar or dissimilarnodes. When similarity is defined in terms of a node’sdegree, it is a sufficient statistic of the joint degree dis-tribution and measures how different the joint degreedistribution is from one where all of the edges are be-tween nodes of the same degree. Studies of the assorta-tivity of networks show that social networks tend to beassortative, while biological and technological networkslike the internet tend to be dissortative [24, 23].Before attempting to use the joint degree distribu-tion as a metric for designing generative models, it isimportant to know how tractable it is to work with.Given a joint degree distribution and an integer n, is itpossible to construct a graph of size n with that joint de-gree distribution? Is it possible to construct or generatea uniformly random graph with that same joint degreedistribution? We address both of these problems in thispaper.Contributions. First, we discuss the necessaryand sufficient conditions for a given joint degree vectorto be graphical. We prove that these conditions aresufficient by providing a new constructive algorithm.Next, we introduce a new configuration model for thejoint degree matrix problem which is a natural extensionof the configuration model for the degree sequenceproblem. Finally, using this configuration model, wedevelop Markov Chains for sampling both pseudographsand simple graphs with a fixed joint degree vector. Weprove the correctness of both chains and mixing timefor the pseudograph chain by using previous work. Thesimple graph chain is experimentally evaluated usingautocorrelation.In practice, Monte Carlo Markov Chains are a verypopular method for sampling from difficult distribu-tions. However, it is often very difficult to theoreti-cally evaluate the mixing time of the chain, and manypractioners simply stop the chain after 5,000, 10,000 or20,000 iterations without much justification. Our ex-perimental design with autocorrelation provides a set ofstatistics that can be used as a justification for chosinga stopping point.Related work. The related work can be roughlydivided into two categories: constructing and samplinggraphs with a fixed DD using sequential importancesampling or Monte Carlo Markov Chain methods, andexperimental work on heuristics for generating randomgraphs with a fixed JDD.The methods for constructing graphs with a givendegree distribution are primarily either reductions toperfect matchings or sequential sampling methods.There are two popular perfect matching methods. Thefirst is the configuration model [1]: k mini-vertices arecreated for each degree k vertex, and all the mini-vertices are connected. Given any perfect matching inthe configuration the edges in the graph correspond tothe connected mini-vertices. This allows multiple edgesand self-loops, which are often undesirable. The secondapproach, the gadget configuration model, prevents thisproblem by creating a gadget for each vertex. If vihasdegree di, then it is replaced with a complete bipartitegraph (Ui, Vi)