Quantification of network structural dissimilarities

By Tiago A. Schieber, Laura C. Carpi, Albert Díaz-Guilera, P. Pardalos, Cristina Masoller, Martín Gómez Ravetti. 2017

225 citations recorded by the source corpus.

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. Identifying and quantifying dissimilarities among graphs is a problem of practical importance, but current approaches are either limited or computationally demanding. Here, the authors propose an efficiently computable measure for network comparison that can identify structural topological differences.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Mianzhi Wang
2. Zhen Zhang
3. Arye Nehorai
4. Yijian Xiang
5. Yan Huang
6. Georgios K. Papageorgiou

Citations in the corpus

• RetGK: Graph Kernels based on Return Probabilities of Random Walks (2018, methodology): “[24] uses the shortest path distance, and [29] uses the diffusion distance.”