论文标题
邻域结构配置模型
Neighborhood Structure Configuration Models
论文作者
论文摘要
我们开发了一种新方法来有效采样合成网络，该网络为任何给定的d保留给定网络的D-HOP邻域结构。拟议的算法将网络样本中的多样性与保存的邻里结构深度进行了交易。我们的关键创新是采用彩色配置模型，其颜色从所谓的颜色改进算法的迭代中得出。我们证明，随着迭代的增加，保留的结构信息增加了：生成的合成网络和原始网络变得越来越相似，并且最终在中心度度量（例如Pagerank，hits，hits，katz Centrality和eigenvector Centrarity）方面无法区分。我们的工作使能够有效地生成与原始网络相似的样本，尤其是对于大型网络。
We develop a new method to efficiently sample synthetic networks that preserve the d-hop neighborhood structure of a given network for any given d. The proposed algorithm trades off the diversity in network samples against the depth of the neighborhood structure that is preserved. Our key innovation is to employ a colored Configuration Model with colors derived from iterations of the so-called Color Refinement algorithm. We prove that with increasing iterations the preserved structural information increases: the generated synthetic networks and the original network become more and more similar, and are eventually indistinguishable in terms of centrality measures such as PageRank, HITS, Katz centrality and eigenvector centrality. Our work enables to efficiently generate samples with a precisely controlled similarity to the original network, especially for large networks.
