simrank

背景

度量相似度是许多应用的关键问题。传统方法与问题的领域相关,如文本匹配、计算交集。simrank则利用关联关系度量相似性,即“两个节点的相似性和各自邻域节点的相似度有关”。

算法

simrank的核心公式:

simrank-LMLPHP,并且simrank-LMLPHPsimrank-LMLPHP时,

simrank-LMLPHP

simrank-LMLPHP,

simrank-LMLPHP

simrank-LMLPHP,或者simrank-LMLPHP

simrank-LMLPHP

通过多轮迭代,simrank-LMLPHP可以收敛。

mapreduce实现

利用mapreduce,容易进行上述的迭代计算。

(1)初始状态:

相似度矩阵是单位阵:

simrank-LMLPHP

邻接集合列simrank-LMLPHPsimrank-LMLPHP

(2)每轮迭代

input:

a_b, s(a,b), x_a, x_b

其中,x_a表示所有与a邻接的节点,x_b表示所有与b邻接的节点,则任意的pairsimrank-LMLPHP都需要累加s(a, b)

map:

分别遍历x_a, x_b,构成pair,输出

pair, s(a, b), I(px), I(p_y)

reduce:

累加s(a, b),得到pair的相似度

05-11 22:55