Quantification of network structural dissimilarities

Tiago A. Schieber, Laura Carpi, Albert Díaz-Guilera, Panos M. Pardalos, Cristina Masoller and Martín G. Ravetti ()
Additional contact information
Tiago A. Schieber: Engineering School, Universidade Federal de Minas Gerais
Laura Carpi: Departament de Física, Universitat Politècnica de Catalunya
Albert Díaz-Guilera: Departament de Física Fonamental, Universitat de Barcelona
Panos M. Pardalos: Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611-6595, USA
Cristina Masoller: Departament de Física, Universitat Politècnica de Catalunya
Martín G. Ravetti: Engineering School, Universidade Federal de Minas Gerais

Nature Communications, 2017, vol. 8, issue 1, 1-10

Abstract: 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.

Date: 2017
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://www.nature.com/articles/ncomms13928 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:8:y:2017:i:1:d:10.1038_ncomms13928

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/ncomms13928

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().