Construction of Directed 2K Graphs
Construction of Directed 2K Graphs
复制标题
DOI：
10.1145/3097983.3098119
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Bálint Tillman;A. Markopoulou;C. Butts;Minas Gjoka
中科院分区：
文献类型：
--
作者：
Bálint Tillman;A. Markopoulou;C. Butts;Minas Gjoka
我们研究的问题，生成合成图，类似于现实世界中的有向图的程度相关性。为了捕捉度相关性，专门为有向图，我们定义有向2K（D2K）的那些图与一个给定的有向度序列（DDS）和一个给定的目标联合度和属性矩阵（JDAM）。我们提供了目标D2 K可实现的充分必要条件，并设计了一种高效的算法，可以精确地生成目标D2 K的图实现。我们应用我们的算法来生成针对现实世界的有向图（如Twitter）的合成图，我们证明了它的好处相比，国家的最先进的建设算法。
We study the problem of generating synthetic graphs that resemble real-world directed graphs in terms of their degree correlations. In order to capture degree correlation specifically for directed graphs, we define directed 2K (D2K) as those graphs with a given directed degree sequence (DDS) and a given target joint degree and attribute matrix (JDAM). We provide necessary and sufficient conditions for a target D2K to be realizable and we design an efficient algorithm that generates graph realizations with exactly the target D2K. We apply our algorithm to generate synthetic graphs that target real-world directed graphs (such as Twitter), and we demonstrate its benefits compared to state-of-the-art construction algorithms.