Hartle Harrison, Klein Brennan, McCabe Stefan, Daniels Alexander, St-Onge Guillaume, Murphy Charles, Hébert-Dufresne Laurent
Network Science Institute, Northeastern University, Boston, MA 02115, USA.
Laboratory for the Modeling of Biological and Socio-Technical Systems, Northeastern University, Boston, MA 02115, USA.
Proc Math Phys Eng Sci. 2020 Nov;476(2243):20190744. doi: 10.1098/rspa.2019.0744. Epub 2020 Nov 4.
Quantifying the differences between networks is a challenging and ever-present problem in network science. In recent years, a multitude of diverse, solutions to this problem have been introduced. Here, we propose that simple and well-understood ensembles of random networks-such as Erdős-Rényi graphs, random geometric graphs, Watts-Strogatz graphs, the configuration model and preferential attachment networks-are natural benchmarks for network comparison methods. Moreover, we show that the expected distance between two networks independently sampled from a generative model is a useful property that encapsulates many key features of that model. To illustrate our results, we calculate this and related quantities for classic network models (and several parameterizations thereof) using 20 distance measures commonly used to compare graphs. The within-ensemble graph distance provides a new framework for developers of graph distances to better understand their creations and for practitioners to better choose an appropriate tool for their particular task.
量化网络之间的差异是网络科学中一个具有挑战性且一直存在的问题。近年来，针对这个问题已经提出了许多不同的解决方案。在这里，我们提出，简单且易于理解的随机网络集合——如厄多斯 - 雷尼图、随机几何图、瓦茨 - 斯托加茨图、配置模型和偏好依附网络——是网络比较方法的自然基准。此外，我们表明，从生成模型中独立采样的两个网络之间的预期距离是一个有用的属性，它封装了该模型的许多关键特征。为了说明我们的结果，我们使用通常用于比较图的20种距离度量，计算了经典网络模型（及其几种参数化）的这个以及相关量。集合内的图距离为图距离开发者提供了一个新框架，以便更好地理解他们的创作成果，也为从业者提供了一个新框架，以便为其特定任务更好地选择合适的工具。
