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. Published in:
The HIM glocal metric and kernel for network comparison and classification
Jurman, Giuseppe;Visintainer, Roberto;Filosi, Michele;Riccadonna, Samantha;Furlanello, Cesare
2015-01-01
Abstract
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. Published in:I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
