一种SimRank迭代删点框架的上界计算方法

摘要

一种SimRank迭代删点框架的上界计算方法，其特征在于，包括：(1)通过先验信息，建立超点，使得每个点与超点的相似度值不小于此点和其他点的相似度值；(2)通过以上特性，预估每个点与超点的相似度作为该点上界，在每次迭代中，预估值会不断减小，上界收敛。本发明方法snbUB的效果比现有技术geoUB的效果持续时间长，每轮迭代snbUB都能保持删点，并且snbUB的删点力度比geoUB的删点力度更大。本发明的上界不仅易于计算且十分逼近真实值。本发明可广泛应用于竞价搜索排名、网络垃圾监测和模式匹配等网络结构中结点相似度计算领域。

主权项

一种SimRank迭代删点框架的上界计算方法，其特征在于，包括以下步骤：(1)通过先验信息，建立超点，使得每个点与超点的相似度值不小于此点和其他点的相似度值；给定一个点集R和其中某点v,此节点v的超点V_s是一个虚拟的点,满足V_s到达某点x的概率是是网络上除v以外的其他点到以相同步数到达该点的最大值，即：其中R_v代表点集R中除v以外的点，代表从点u出发走l步到达点x的概率；以S(v,u)表示点相似度v和点u的相似度，则对于点v和其超点V_s的相似度不小于点v和其他点的相似度，即如下不等式成立:S(v,V_s)≥S(v,u),u∈R_v＝R/{v}.(2)通过以上特性，预估每个点与超点的相似度作为该点上界，在每次迭代中，预估值会不断减小，上界因此收敛；上界的计算公式为：其中ρ(y,i)为二次相遇概率，代表了从点y出发走i步的两条随机路径再次相遇的概率，T代表了已经被计算出的二次相遇概率，凡是代表上界的地方用Snb表示，snbUB(v,u)是S(v,u)的一个估计。