Problem Formalization

Notation

• ---> graph
• ---> substructure of
• ---> node
• ---> 連接 跟 的邊
• ---> 的關聯矩陣
• ---> 關聯矩陣的第 row
• ---> 關聯矩陣的第 row 第 column
• ---> node 或 edge 的類別
• ---> node 或 edge 的類別的集合

First-order proximity

是指計算 與 之間邊的權重，也就是

• 像是上圖中的範例， 與 之間邊的權重為 1.2，所以
• 與其他節點的權重的表達方式：

Second-order proximity

簡單來說就是計算 's neighbors 跟 's neighbors 的相似度

所以 的計算方式為：

import numpy as np

vec1 = np.array([0, 1.2, 0.8, 0])
vec2 = np.array([1.2, 0, 1, 0])

cos_sim = vec1.dot(vec2) / (np.linalg.norm(vec1) * np.linalg.norm(vec2))

print(cos_sim)

>>> 0.3551104121142175

Higher-order proximity

如果是更高維度 的 proximity，就是去計算 跟 在 order 的相似度，用公式表示：

不過在更高維度的 proximity 上，使用的方法就不一定是計算 edge 的權重，也可以使用其他的 metric，例如：Katz index, rooted PageRank, Adamic-Adar index 等等。