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
未完待续...