The HIM glocal metric and kernel for network comparison and classification

G Jurman, R Visintainer, M Filosi… - … conference on data …, 2015 - ieeexplore.ieee.org
2015 IEEE international conference on data science and advanced …, 2015ieeexplore.ieee.org
Comparing and classifying graphs represent two essential steps for network analysis, across
different scientific and applicative domains. Here we deal with both operations by
introducing the Hamming-Ipsen-Mikhailov (HIM) distance, a novel metric to quantitatively
measure the difference between two graphs sharing the same vertices. The new measure
combines the local Hamming edit distance and the global Ipsen-Mikhailov spectral distance
so to overcome the drawbacks affecting the two components when considered separately …
Comparing and classifying graphs represent two essential steps for network analysis, across different scientific and applicative domains. Here we deal with both operations by introducing the Hamming-Ipsen-Mikhailov (HIM) distance, a novel metric to quantitatively measure the difference between two graphs sharing the same vertices. The new measure combines the local Hamming edit distance and the global Ipsen-Mikhailov spectral distance so to overcome the drawbacks affecting the two components when considered separately. Building the kernel function derived from the HIM distance makes possible to move from network comparison to network classification via the Support Vector Machine (SVM) algorithm. Applications of HIM-based methods on synthetic dynamical networks as well as in trade economy and diplomacy datasets demonstrate the effectiveness of HIM as a general purpose solution. An Open Source implementation is provided by the R package nettools, (already configured for High Performance Computing) and the Django-Celery web interface ReNette http://renette.fbk.eu.
ieeexplore.ieee.org