轉(zhuǎn)載https://blog.csdn.net/u012151283/article/details/87081272?spm=1001.2014.3001.5501
前面介紹過基于DFS鄰域的DeepWalk和基于BFS鄰域的LINE。
node2vec是一種綜合考慮DFS鄰域和BFS鄰域的graph embedding方法。簡單來說，可以看作是eepwalk的一種擴(kuò)展又谋，可以看作是結(jié)合了DFS和BFS隨機(jī)游走的deepwalk。
nodo2vec 算法原理
優(yōu)化目標(biāo)
采樣策略
node2vec依然采用隨機(jī)游走的方式獲取頂點(diǎn)的近鄰序列纬黎，不同的是node2vec采用的是一種有偏的隨機(jī)游走寥茫。
給定當(dāng)前頂點(diǎn)v vv，訪問下一個(gè)頂點(diǎn)x的概率為
采樣完頂點(diǎn)序列后沮明，剩下的步驟就和deepwalk一樣了，用word2vec去學(xué)習(xí)頂點(diǎn)的embedding向量窍奋。
值得注意的是node2vecWalk中不再是隨機(jī)抽取鄰接點(diǎn)荐健，而是按概率抽取，node2vec采用了Alias算法進(jìn)行頂點(diǎn)采樣琳袄。
Alias Method:時(shí)間復(fù)雜度O(1)的離散采樣方法
node2vec核心代碼
node2vecWalk
通過上面的偽代碼可以看到江场，node2vec和deepwalk非常類似，主要區(qū)別在于頂點(diǎn)序列的采樣策略不同窖逗，所以這里我們主要關(guān)注node2vecWalk的實(shí)現(xiàn)址否。
由于采樣時(shí)需要考慮前面2步訪問過的頂點(diǎn)，所以當(dāng)訪問序列中只有1個(gè)頂點(diǎn)時(shí)碎紊，直接使用當(dāng)前頂點(diǎn)和鄰居頂點(diǎn)之間的邊權(quán)作為采樣依據(jù)佑附。
當(dāng)序列多余2個(gè)頂點(diǎn)時(shí)，使用文章提到的有偏采樣
def node2vec_walk(self, walk_length, start_node):
G = self.G
alias_nodes = self.alias_nodes
alias_edges = self.alias_edges
walk = [start_node]
while len(walk) < walk_length:
cur = walk[-1]
cur_nbrs = list(G.neighbors(cur))
if len(cur_nbrs) > 0:
if len(walk) == 1:
walk.append(cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])])
else:
prev = walk[-2]
edge = (prev, cur)
next_node = cur_nbrs[alias_sample(alias_edges[edge][0],alias_edges[edge][1])]
walk.append(next_node)
else:
break
return walk
構(gòu)造采樣表
preprocess_transition_probs分別生成alias_nodes和alias_edges仗考，alias_nodes存儲(chǔ)著在每個(gè)頂點(diǎn)時(shí)決定下一次訪問其鄰接點(diǎn)時(shí)需要的alias表（不考慮當(dāng)前頂點(diǎn)之前訪問的頂點(diǎn)）音同。alias_edges存儲(chǔ)著在前一個(gè)訪問頂點(diǎn)為t tt，當(dāng)前頂點(diǎn)為v vv時(shí)決定下一次訪問哪個(gè)鄰接點(diǎn)時(shí)需要的alias表秃嗜。
def get_alias_edge(self, t, v):
G = self.G
p = self.p
q = self.q
unnormalized_probs = []
for x in G.neighbors(v):
weight = G[v][x].get('weight', 1.0)# w_vx
if x == t:# d_tx == 0
unnormalized_probs.append(weight/p)
elif G.has_edge(x, t):# d_tx == 1
unnormalized_probs.append(weight)
else:# d_tx == 2
unnormalized_probs.append(weight/q)
norm_const = sum(unnormalized_probs)
normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]
return create_alias_table(normalized_probs)
def preprocess_transition_probs(self):
G = self.G
alias_nodes = {}
for node in G.nodes():
unnormalized_probs = [G[node][nbr].get('weight', 1.0) for nbr in G.neighbors(node)]
norm_const = sum(unnormalized_probs)
normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]
alias_nodes[node] = create_alias_table(normalized_probs)
alias_edges = {}
for edge in G.edges():
alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])
self.alias_nodes = alias_nodes
self.alias_edges = alias_edges
return
