一对一般性有标签图（Graph）的相似度函数

计算两个Graph的相似性指数，这问题其实就是把高阶的张量用一种映射成为一个标量，来提取差异信息。

提取完美结构差异信息是个NP难问题。在多项式时间内有各种不同的映射方法，可获得不完全信息的近似解。

高阶张量映射成标量，也可以说是降维。把高维信息可以有不同的投影方式投影，完成降维。每种投影都是不完全信息，对应一种网络特征。一个好的投影方式可以获得尽可能全面的信息。

我在此给出了一种相似度函数的实现。源码放在GitHub上，GitHub - fsssosei/similarity_index_of_label_graph: This is the package used to calculate the similarity index of the label graph pairs.

简单的说是两个步骤：

1. 先把两个图（Graph）向量化，也就是“图嵌入向量”；

2. 再对两个向量进行度量计算，得到最终结果。

对于步骤一，我选择了基于点向量（Node embedding）的方法，是一种有关平均最短路径长度的核。

在完成步骤一，对Graph的变换后得到两个向量。

然后在步骤二中我选用了pearson相关系数作为度量函数，来对两个向量做度量，得到最终的标量值。

这整个算法的时间复杂度是 O(V^2*log(V)+VE)。

已经发布到了PyPI上，可以很方便的安装分发：

pip install similarity-index-of-label-graph

similarity_index_of_label_graph包是很易用的。

先在程序里导入：

from similarity_index_of_label_graph_package import similarity_index_of_label_graph_class

再创建一个这个类的实例对象：

similarity_index_of_label_graph = similarity_index_of_label_graph_class()

然后就可以调用此实例对象：

similarity_index_of_label_graph(G1, G2)

对两个图计算了。

我把这个实现写成一个类，而不是一个函数，是为了可以很方便替换掉任意一个步骤里所用的方法。

比如步骤一里可以用随机漫步核替换，步骤二里可以用energy距离替换。