公开(公告)号：CN105760503A

公开(公告)日：2016-07-13

申请号：CN201610097429.6

申请日：2016-02-23

申请人： 清华大学

发明人： 唐杰 ,  张静 ,  荆榆 ,  刘德兵 ,  李涓子

IPC分类号： G06F17/30

CPC分类号： G06F17/30539

摘要： 本发明公开了一种快速计算图节点相似度的方法，包括步骤：对于给定的图，进行路径采样并构建从节点到路径的倒排索引；对于所述图中的每个节点，根据所述倒排索引得到每个节点的共现路径节点，计算每个节点和所述共现路径节点之间的近邻相似度；对于所述图中的每个节点，选择top?k个近邻相似点的相似值作为每个节点的特征向量；对于所述图中的每个节点的特征向量构建kd?tree索引；根据所述kd?tree索引，计算所述图中每个节点向量的top?k个结构相似点。本发明具有如下优点：能够统一且快速地计算近邻和结构两种相似度。

公开(公告)号：CN105760503B

公开(公告)日：2019-02-05

申请号：CN201610097429.6

申请日：2016-02-23

申请人： 清华大学

发明人： 唐杰 ,  张静 ,  荆榆 ,  刘德兵 ,  李涓子

IPC分类号： G06F16/903

摘要： 本发明公开了一种快速计算图节点相似度的方法，包括步骤：对于给定的图，进行路径采样并构建从节点到路径的倒排索引；对于所述图中的每个节点，根据所述倒排索引得到每个节点的共现路径节点，计算每个节点和所述共现路径节点之间的近邻相似度；对于所述图中的每个节点，选择top‑k个近邻相似点的相似值作为每个节点的特征向量；对于所述图中的每个节点的特征向量构建kd‑tree索引；根据所述kd‑tree索引，计算所述图中每个节点向量的top‑k个结构相似点。本发明具有如下优点：能够统一且快速地计算近邻和结构两种相似度。