计算两个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距离替换。
网友评论