PathSim

Network Schema: network schema is a meta template for a heterogeneous G=(V,E) with the object type mapping ϕ:VA and the link mapping ψ:ER, which is a directed graph defined over object types A, with edges as relations from R, denoted as TG=(A,R)

Meta path: 元路径是指定义在不同类型定点之间的一系列关系序列组成的一条路径。

PathSim: 是使用元路径来定义的一种新颖的相似搜索度量方法,用于找到异构网络中相同类型的相似顶点。

s(x,y)=2×|{pxy:pxyP}||{pxx:pxxP}|+|{pyy:pyyP}|

其中pxyxy之间的路径实例,pxxxx之间的路径实例,pyyyy之间的路径实例。

例如有一个简单的表示作者和发表会议的邻接矩阵WAC,矩阵中每个元素表示作者在每个会议发表的数量:

- SIGMOD VLDB ICDE KDD
Mike 2 1 0 0
Jim 50 20 0 0
Mary 2 0 1 0
Bob 2 1 0 0
Ann 0 0 1 1

那么Mike和Jim的相似度就可以计算为:

S(Mike,Jim)=2×(2×50+1×20)(22+12)+(502+202)=0.0826

Commuting Matrix: 给定一个网络G=(V,E),它的network schema为TG,那么对于一个元路径P=(A1A2Al)的commuting matrix M可以表示为M=WA1A2WA2A3WAl1Al,其中WAiAj是在类型Ai和类型Aj之间的邻接矩阵。M(i,j)代表在给定的meta path P下物品xiA1和物品yjAl之间的路径数量。

给定一个对称的元路径P,两个相同类型的物品xixj之间的PathSim可以计算为s(xi,xj)=2MijMii+Mjj

以上面包含Mike和Jim的那个邻接为例,每个author之间的相似度矩阵可以通过先计算commuting matrix,然后除去一个分母项得到。其python实现的代码如下:

import numpy as np

AC = np.array([
     [2,  1, 0, 0],
     [50, 20, 0, 0],
     [2,  0, 1, 0],
     [2,  1, 0, 0],
     [0,  0, 1, 1],
])
AC = AC.astype(np.float)
CA = AC.T
ACA = np.dot(AC, CA)

Mij = ACA.copy()
Mii = np.repeat(ACA.diagonal()[:, None], 5, axis=1)
Mjj = np.repeat(ACA.diagonal()[None, :], 5, axis=0)

S = 2 * Mij / (Mii + Mjj)

# array([[1.        , 0.08261618, 1.        , 0.        ],
#        [0.08261618, 1.        , 0.08261618, 0.        ],
#        [1.        , 0.08261618, 1.        , 0.        ],
#        [0.        , 0.        , 0.        , 1.        ]])

Variation

  • PathConstrained Random Walks (PCRW)
  • HeteSim

Reference