2K+ Graph Construction Framework: Targeting Joint Degree Matrix and Beyond

In this paper, we study the problem of generating synthetic graphs that resemble real-world graphs in terms of their degree correlations and potentially additional properties. We present an algorithmic framework that generates simple undirected graphs with the exact target joint degree matrix, which we refer to as 2K graphs, in linear time in the number of edges. Our framework imposes minimal constraints on the graph structure, which allows us to target additional graph properties during construction, namely, node attributes (2K+A), clustering (both average clustering, 2.25K, and degree-dependent clustering, 2.5K), and number of connected components (2K+CC). We also define, for the first time, the problem of directed 2K graph construction, provide necessary and sufficient conditions for realizability, and develop efficient construction algorithms. We evaluate our approach by creating synthetic graphs that target real-world graphs both undirected (such as Facebook) and directed (such as Twitter), and we show that it brings significant benefits, in terms of accuracy and running time, compared to the state-of-the-art approaches.