轉(zhuǎn)載https://blog.csdn.net/u012151283/article/details/87081272?spm=1001.2014.3001.5501

前面介紹過基于DFS鄰域的DeepWalk和基于BFS鄰域的LINE。

image.png

node2vec是一種綜合考慮DFS鄰域和BFS鄰域的graph embedding方法。簡單來說，可以看作是eepwalk的一種擴展，可以看作是結(jié)合了DFS和BFS隨機游走的deepwalk。

nodo2vec 算法原理

優(yōu)化目標

image.png

采樣策略

node2vec依然采用隨機游走的方式獲取頂點的近鄰序列，不同的是node2vec采用的是一種有偏的隨機游走。

給定當前頂點v vv，訪問下一個頂點x的概率為

image.png

image.png

image.png

采樣完頂點序列后，剩下的步驟就和deepwalk一樣了，用word2vec去學(xué)習(xí)頂點的embedding向量。
值得注意的是node2vecWalk中不再是隨機抽取鄰接點，而是按概率抽取，node2vec采用了Alias算法進行頂點采樣。
Alias Method:時間復(fù)雜度O(1)的離散采樣方法

node2vec核心代碼

node2vecWalk

通過上面的偽代碼可以看到，node2vec和deepwalk非常類似，主要區(qū)別在于頂點序列的采樣策略不同，所以這里我們主要關(guān)注node2vecWalk的實現(xiàn)。

由于采樣時需要考慮前面2步訪問過的頂點，所以當訪問序列中只有1個頂點時，直接使用當前頂點和鄰居頂點之間的邊權(quán)作為采樣依據(jù)。
當序列多余2個頂點時，使用文章提到的有偏采樣

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存儲著在每個頂點時決定下一次訪問其鄰接點時需要的alias表（不考慮當前頂點之前訪問的頂點）。alias_edges存儲著在前一個訪問頂點為t tt，當前頂點為v vv時決定下一次訪問哪個鄰接點時需要的alias表。

image.png

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