2017/03/21 by Bálint Tillman, Tillman, Bálint, Athina Markopoulou +5 · 1 citation
Physics and Astronomy · Computer Science · #Complex Network Analysis Techniques #Rough Sets and Fuzzy Logic #Data Visualization and Analytics
paper · pdf · doi:10.48550/arxiv.1703.07340
We study the problem of constructing synthetic graphs that resemble real-world directed graphs in terms of their degree correlations. We define the problem of directed 2K construction (D2K) that takes as input the directed degree sequence (DDS) and a joint degree and attribute matrix (JDAM) so as to capture degree correlation specifically in directed graphs. We provide necessary and sufficient conditions to decide whether a target D2K is realizable, and we design an efficient algorithm that creates realizations with that target D2K. We evaluate our algorithm in creating synthetic graphs that target real-world directed graphs (such as Twitter) and we show that it brings significant benefits compared to state-of-the-art approaches.