相关文章：
SimRank: A Measure of Structural-Context Similarity
simRank是一种与领域无关的节点相似度评价，即它只会根据节点在图中的上下文信息来评价其相似度，而不会考虑领域知识相关的内容。其遵循的假设是“如果两个节点的相关节点是相似的，则它们就是相似的”。还有一个基本假设是相同节点之间是相似的。
simRank小例子：在图一中，G是原始图，G^2是在G的基础上构建的，其特点是节点为一对G中的节点。其构造过程为：以（Univ, Univ)为起点，对于已有的一个节点（a，b），如果a指向了c，b指向了d，则（a，b）会指向（c，d），由于相似函数应该是对称的，因此（a，b）和（b，a）被认为是一样的。
由simRank的计算公式可知，simRank的计算过程是递归的，在图1中的则表示了各节点对之间在计算过程中的依赖关系，即计算某一节点对的相似度是，会使用到所有指向它们的节点对的相似度。由图可以看出，有些点对之间的相似度可直接得出，有些则需要在别的结果的基础上得出，有的节点对之间的相似度的计算还要拿自己做输入。
simRank的计算公式
因此，有的节点之间的simRank其实是没办法计算的（但却会收敛到一个点上），而估计simRank的一个最单纯的想法便是通过一种规则不断地对每对节点的simRank值进行更新。
1.对每一对节点之间的simRank值进行初始化，如果是同一节点则为1，否则为0
2.领用上一步得到的值，通过公式对simRank进行更新。
更新算法
3.重复2直至收敛
这个过程比较简单，可以写段代码。https://www.jianshu.com/p/cde25338064c
迭代一般会在K=5时就收敛了，时间复杂度为O（K），K是迭代次数，n是节点个数，
是邻居数的平均值，复杂度还是相当高，最好能优化一下，使用剪枝等。（好像剪完枝也快不到哪儿去，这段就略过吧）
对于预期距离公式：
预期距离
在公式中，要针对每一条从u到v的路径进行求和。记,则它的长度是k-1，
，解释起来就是从
到
有O种选择，所以有1/O的可能性到了
在预期距离的启发下，定义相遇距离：
相遇距离
很容易理解，就是一个从a，一个从b，然后两个人都到了x的概率乘上距离再求和
由于所求的图谱中可能存在环，因此m是可以无限大的，为了让式子可以收敛，引入f函数下的期望相遇距离：
f函数下的期望相遇距离
其实就是把原来的，替换成了
经过一番证明，这个式子竟然跟之前那个simRank的式子的定义是等价的
数学好神奇！
不过证明真的想略过啊，看起来好复杂：
证明过程
让我们回到我们本来要看的那个论文哈：
首先对期望相遇距离的公式进行了改写，但意思没变：
期望相遇距离
由于遍历很麻烦，所以采用蒙特卡洛方法：
蒙特卡洛
算法思想很简单，先随机生成两个路径，然后找到第一个重合的点（记为t），就认为这次采用中，距离是t，最后求个平均。
网友评论