Assortativity in Chung Lu Random Graph Models

Due to the widespread interest in networks as a representation to investigate the properties of complex systems, there has been a great deal of interest in generative models of graph structure that can capture the properties of networks observed in the real world. Recent models have focused primarily on accurate characterization of sparse networks with skewed degree distributions, short path lengths, and local clustering. While assortativity---degree correlation among linked nodes---is used as a measure to both describe and evaluate connectivity patterns in networks, there has been little effort to explicitly incorporate patterns of assortativity into model representations. This is because many graph models are edge-based (modeling whether a link should be placed between a pair of nodes i and j) and assortativity is a second-order characteristic that depends on the global properties of the graph (i.e., the final degree of i and j). As such, it is difficult to incorporate direct optimization of assortativity into edge-based generative models.

One exception is the BTER method [5], which generates graphs with positive assortativity (e.g., high degree nodes link to each other). However, BTER does not directly estimate assortativity and also is not applicable for networks with negative assortativity (e.g, high degree nodes link primarily to low degree nodes). In this work, we present a novel approach to directly model observed assortativity (both positive and negative) via accept-reject sampling. Our key observation is to use a coarse approximation of the observed joint degree distribution and modify the likelihood that two nodes i, j should link based on the output properties of the original model. We implement our approach as an augmentation of Chung-Lu models and refer to it as Binning Chung Lu (BCL). We apply our method to six network datasets and show that it captures assortativity significantly more accurately than other methods while maintaining other graph properties of the original CL models. Also, our BCL approach is efficient (linear in the number of observed edges), thus it scales easily to large networks.