具有未知节点对应关系的图相似度

Question

如何在节点数相等或不相等的情况下测量两个图G1和G2之间的相似度，其中，图的节点之间的对应关系未知。例如，G1的节点A已移至G2的中间。是否有任何相似性度量算法返回

sim(G1,G1)=1 
sim(G1,G2)=1
sim(G1,G3)=some number between 0 and 1

其中，1表示最高相似度，0表示最低相似度。

Answer 1

由于您不知道节点的对应关系，一种简单的方法是将图的签名定义为包含所有节点的度的排序数组。然后找到longest common sub-sequence，其中“公共”不是必需的，意味着所有“元素都相等”，但是它们足够接近。然后以某种方式计算出最长的“公共”子序列的两个版本之间的距离。另外，您可以考虑一些不属于该节点的分数。