图的相似度计算系统和方法

摘要

以适当的计算时间求出SNS、WWW的链接等具有很多节点的图之间的相似度。对图的节点，向该节点的标签值赋予唯一的值。优选，该值是固定长位串。此时的位串的长度选为比用于表现标签的种类足够的位数充分大的数。关于一个图，通过深度优先搜索、宽度优选搜索等原有的图搜索技术方法，依次访问该图的节点。此时，本发明的系统，在位于一个节点时，对与该节点相邻的所有节点的位串标签值和该节点的位串标签值实施计算，计算位串值。本发明的系统根据该计算出的位串值和该节点本来具有的位串标签值实施散列计算，计算另外的位串标签值，将其作为该节点的标签值。这样，结束访问一个图的所有节点时，所有节点的标签值被改写。对想要比较图的相似度的另外图也进行同样的处理后，其他的图中也改写所有节点的标签值。这样，在一个图中通过计算相对于所有节点数的与其他图一致的标签值的比例，能够求出相似度。

主权项

一种方法，通过计算机的处理计算在各节点赋予离散标签的两个图之间的相似度，包括：在各自的所述两个图，向给定的节点及其相邻的节点赋予标签值使得不同的值对应于不同的离散标签的步骤；在所述两个图依次搜索节点的步骤；在搜索所述节点的期间，通过正访问的节点的标签值和与该正访问的节点相邻的节点的标签值的散列计算来计算新的标签值，通过该新的标签值更新该正访问的节点的标签值的步骤；以及基于向所述两个图的节点赋予的、一致的标签值的个数，计算所述两个图之间的相似度的步骤。