node2vec

參考博客：https://zhuanlan.zhihu.com/p/56542707

偽代碼

def node2vec_walk(G, u, walk_length):walk = [u]for l in range(walk_length):V = get_neighbors(G, walk[-1])s = alias_sample(V, pi) # 核心的采樣策略walk.append(s)return walk def node2vec(...):walks = []for r in range(walk_iter):for u in AllNodes:walk = node2vec_walk(G, u, walk_length)walks.append(walk)Word2Vec(walks)SGD()

Alias Sampling

1、首先需要根據node2vec的轉移策略得到預處理的轉移概率。這樣，對于每個當前節點u，我們都可以知道所有鄰居節點的轉移概率列表，并對這個列表進行歸一化得到概率。

2、有了這個概率分布列表，我們就可以根據其進行alias sample，得到本次需要選出的鄰居節點。
3、我們通過處理可以得到alias_table，時間復雜度是$O(n)$。這樣之后每次采樣的時間復雜度就是$O(1)$。

假設有N個鄰居節點，轉移到節點i的概率為$p_i$，則可以將全部概率看作是1*N矩形的面積，這樣，$q_i$ 就可以寫成 $\frac{p_i?N}{{\sum }_{k=1}^N{p}_k}$，如果進行歸一化，那么分母就是1。有一些項乘N之后會>1，有一些會<1，那么再用>1的部分依次去補全<1的部分（最終剛好可以全部都補全）。最終隨機random一個 $r\in [0,1)$和 $K\in [0,N)$，如果$r<q[K]$，那么接受事件i，否則返回alias[i]。(參考：https://zhuanlan.zhihu.com/p/54867139)

總結

以上是生活随笔為你收集整理的node2vec简单总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。