网络中顶点相似度的计算 node similarity measurement in network

Graph的一个最大好处，是他可以用尽量少的空间来存储物体(object)直接的相似度。如果我们有N个物体，要存储他们两两直接的相似度，需要用N*N的存储空间。但是用Graph可以节省很多空间，因为他可以将很多相似度隐含到网络的结构中去。

相似度图G(V,E,W).如果两个顶点直接有边连接，那么边的权重就代表两个顶点直接的相似度。那么如果两个顶点之间没有边连接呢？虽然没有边连接，但只要图是联通的，那么肯定有若干条路径连接，这就是前面所说的，顶点的相似度蕴含在图的结构当中。那么我们的相似度函数必须在考虑图的边的同时，还要考虑图中的路径。

以下是本文用到的一些记号
inv(A) : A的逆矩阵
pow(A,n) ：A的n次方

1.Katz的方法
A new status index derived from sociometric analysis 1953
如果G的邻接矩阵是A，a(i,j)是顶点i,j的相似度。那么Katz用一下的方法来度量相似度：
S = inv(I - pA) - I = pA + pow(pA,2) + ... + pow(pA,n) + ...
这个方法通过邻接矩阵的n次方来考虑图中小于n的路径。这个方法的优点是定义很简单，意义也很清楚。缺点就是，矩阵的求逆计算太耗时。 而且这个方法一次性的计算了图中所有顶点对之间的相似度，如果我们仅仅要知道两个顶点直接的相似度，复杂度就太高了。

2.RandomWalk 随机游走
这个方法首先计算出图的马尔可夫转移概率矩阵。然后在图中进行随机游走。假设从i开始随机游走，如果i,j之间有一条边，那么从i到j的转移概率是p(i,j). 那么我们考虑图中的任意一个点k，那么我们考虑如果从i出发，随机在图中游走，那么第一次走到k需要的平均步数，可以看作i,k之间的相似度。
Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation. 2007 Francois Fouss


未完待续...