Multiscale planar graph generation
Multiscale planar graph generation
复制标题
DOI：
10.1007/s41109-019-0142-3
复制
发表时间：
2018-02
影响因子：
2.2
通讯作者：
Varsha Chauhan;Alexander Gutfraind;Ilya Safro
中科院分区：
文献类型：
--
作者：
Varsha Chauhan;Alexander Gutfraind;Ilya Safro
研究物理、生物和社会现象的网络表征可以帮助我们更好地理解它们的结构和功能动态，并建立这些现象的预测模型。然而，由于收集网络数据所需的成本和精力以及这些数据对盗窃和滥用的敏感性等因素，现实世界网络数据的稀缺性，工程师和研究人员经常依赖合成数据进行模拟，假设检验，决策制定和算法工程。基础设施网络（如道路、配水和其他公用事业系统）的一个重要特征是，它们可以（几乎完全）嵌入在一个平面中，因此，为了模拟这些系统，我们需要现实的平面网络。虽然目前可用的合成网络生成器可以模拟显示现实主义的网络，但它们不能保证或实现平面性。本文提出了一种灵活的算法，可以合成平面的真实网络。该方法采用多尺度随机化编辑方法，生成给定平面图形的粗化网络层次，并在层次中引入不同层次的编辑。该方法以最小的偏差保留了网络的结构特性，包括网络的平面性，同时在多个尺度上引入了真实的可变性。可重复性：本工作中提出的所有数据集和算法实现可在https://bit.ly/2CjOUAS上获得
The study of network representations of physical, biological, and social phenomena can help us better understand their structure and functional dynamics as well as formulate predictive models of these phenomena. However, due to the scarcity of real-world network data owing to factors such as cost and effort required in collection of network data and the sensitivity of this data towards theft and misuse, engineers and researchers often rely on synthetic data for simulations, hypothesis testing, decision making, and algorithm engineering. An important characteristic of infrastructure networks such as roads, water distribution and other utility systems is that they can be (almost fully) embedded in a plane, therefore to simulate these system we need realistic networks which are also planar. While the currently-available synthetic network generators can model networks that exhibit realism, they do not guarantee or achieve planarity. In this paper we present a flexible algorithm that can synthesize realistic networks that are planar. The method follows a multi-scale randomized editing approach generating a hierarchy of coarsened networks of a given planar graph and introducing edits at various levels in the hierarchy. The method preserves the structural properties with minimal bias including the planarity of the network, while introducing realistic variability at multiple scales.Reproducibility: All datasets and algorithm implementation presented in this work are available at https://bit.ly/2CjOUAS