The HIM glocal metric and kernel for network comparison and classification
The HIM glocal metric and kernel for network comparison and classification
复制标题
DOI：
10.1109/dsaa.2015.7344816
复制
发表时间：
2012-01
期刊：
影响因子：
--
通讯作者：
Giuseppe Jurman;R. Visintainer;M. Filosi;S. Riccadonna;Cesare Furlanello
中科院分区：
文献类型：
--
作者：
Giuseppe Jurman;R. Visintainer;M. Filosi;S. Riccadonna;Cesare Furlanello
比较和分类图代表了网络分析的两个基本步骤，跨越不同的科学和应用领域。在这里，我们通过引入Hamming-Ipsen-Mikhailov（HIM）距离来处理这两种操作，HIM距离是一种定量测量共享相同顶点的两个图之间差异的新度量。新的测度结合了局部Hamming编辑距离和全局Ipsen-Mikhailov谱距离，克服了单独考虑两个分量时影响两个分量的缺点。构建从HIM距离导出的核函数使得可以经由支持向量机（SVM）算法从网络比较移动到网络分类。基于HIM的方法在合成动态网络以及贸易、经济和外交数据集上的应用证明了HIM作为通用解决方案的有效性。开源实现由R包nettools（已经为高性能计算配置）和Django-Celery Web接口ReNette http://renette.fbk.eu提供。
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.