simrank
背景
度量相似度是许多应用的关键问题。传统方法与问题的领域相关,如文本匹配、计算交集。simrank则利用关联关系度量相似性,即“两个节点的相似性和各自邻域节点的相似度有关”。
算法
simrank的核心公式:
当,并且
,
时,
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191853843-1685459875.png)
当
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191854155-1826610254.png)
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191854374-2124676373.png)
当
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191854593-108705297.png)
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191854874-2020551259.png)
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191855093-1768791271.png)
通过多轮迭代,
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191855311-731054274.png)
mapreduce实现
利用mapreduce,容易进行上述的迭代计算。
(1)初始状态:
相似度矩阵是单位阵:
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191855530-1711585277.png)
邻接集合列
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191855718-2016165120.png)
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191855983-1380891485.png)
(2)每轮迭代
input:
a_b, s(a,b), x_a, x_b
其中,x_a表示所有与a邻接的节点,x_b表示所有与b邻接的节点,则任意的pair
![](https://images2017.cnblogs.com/blog/494740/201712/494740-20171217191856249-1907215707.png)
map:
分别遍历x_a, x_b,构成pair,输出
pair, s(a, b), I(px), I(p_y)
reduce:
累加s(a, b),得到pair的相似度