Departmento de Engenharia de Produção, Engineering School, Universidade Federal de Minas Gerais, Avenida Antonio Carlos 6627, Belo Horizonte 31.270-901, Brazil.
Departament de Física, Universitat Politècnica de Catalunya, 08222 Terrassa, Spain.
Nat Commun. 2017 Jan 9;8:13928. doi: 10.1038/ncomms13928.
Identifying and quantifying dissimilarities among graphs is a fundamental and challenging problem of practical importance in many fields of science. Current methods of network comparison are limited to extract only partial information or are computationally very demanding. Here we propose an efficient and precise measure for network comparison, which is based on quantifying differences among distance probability distributions extracted from the networks. Extensive experiments on synthetic and real-world networks show that this measure returns non-zero values only when the graphs are non-isomorphic. Most importantly, the measure proposed here can identify and quantify structural topological differences that have a practical impact on the information flow through the network, such as the presence or absence of critical links that connect or disconnect connected components.
识别和量化图之间的差异是许多科学领域中具有实际重要性的基本和具有挑战性的问题。当前的网络比较方法仅限于提取部分信息或计算要求非常高。在这里，我们提出了一种用于网络比较的有效且精确的度量方法，该方法基于从网络中提取的距离概率分布之间的差异进行量化。在合成和真实网络上的广泛实验表明，只有当图是非同构的时，该度量才会返回非零值。最重要的是，这里提出的度量可以识别和量化对信息流通过网络产生实际影响的结构拓扑差异，例如存在或不存在连接或断开连通分量的关键链路。
