title: Quantification of network structural dissimilarities.
abstract: 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.
authors.affiliation: Departmento de Engenharia de Produção, Engineering School, Universidade Federal de Minas Gerais, Avenida Antonio Carlos 6627, Belo Horizonte 31.270-901, Brazil.
authors.forename: Tiago A
authors.initials: TA
authors.lastname: Schieber
authors.affiliation: Departament de Física, Universitat Politècnica de Catalunya, 08222 Terrassa, Spain.
authors.forename: Laura
authors.initials: L
authors.lastname: Carpi
authors.affiliation: Departament de Física Fonamental, Universitat de Barcelona, 08028 Barcelona, Spain.|Universitat de Barcelona, Institute of Complex Systems (UBICS), 08028 Barcelona, Spain.
authors.forename: Albert
authors.initials: A
authors.lastname: Díaz-Guilera
authors.affiliation: Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611-6595, USA.
authors.forename: Panos M
authors.initials: PM
authors.lastname: Pardalos
authors.affiliation: Departament de Física, Universitat Politècnica de Catalunya, 08222 Terrassa, Spain.
authors.forename: Cristina
authors.initials: C
authors.lastname: Masoller
authors.affiliation: 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 Fonamental, Universitat de Barcelona, 08028 Barcelona, Spain.
authors.forename: Martín G
authors.initials: MG
authors.lastname: Ravetti