random wlak：就是在網(wǎng)絡(luò)上不斷重復(fù)地隨機(jī)選擇游走路徑，最終形成一條貫穿網(wǎng)絡(luò)的路徑。從某個(gè)特定的端點(diǎn)開始，游走的每一步都從與當(dāng)前節(jié)點(diǎn)相連的邊中隨機(jī)選擇一條，沿著選定的邊移動(dòng)到下一個(gè)頂點(diǎn)，不斷重復(fù)這個(gè)過程。截?cái)嚯S機(jī)游走(truncated random walk)實(shí)際上就是長度固定的隨機(jī)游走，如下圖中的綠色路徑即為一條random walk
random walk
random wlak的兩個(gè)優(yōu)點(diǎn)：
- Parallelize: Several random walkers can simultaneously explore different parts of the same graph.
- Adaptable: Accommodate small changes in the graph structure without the need for global recomputation.
頂點(diǎn)出現(xiàn)在short random walk中的頻率分布和word出現(xiàn)在句子中的頻率分布有著類似的冪律分布，因此將nlp中的模型重用于社交網(wǎng)絡(luò)圖。
冪律分布
于是我們可以做如下類比
將單詞對(duì)應(yīng)成網(wǎng)絡(luò)中的節(jié)點(diǎn)vi ，句子序列對(duì)應(yīng)成網(wǎng)絡(luò)的隨機(jī)游走(v0, v1, …, vi)，那么對(duì)于一個(gè)隨機(jī)游走 ，要優(yōu)化的目標(biāo)就是Pr，也就是當(dāng)知道(v0, v1, …, vi-1)游走路徑后，游走的下一個(gè)節(jié)點(diǎn)是vi的概率是多少；
但是頂點(diǎn)本身是不可計(jì)算的，所以引入映射函數(shù)，將頂點(diǎn)映射成向量（這其實(shí)就是我們要求的），轉(zhuǎn)化成向量后就可以對(duì)頂點(diǎn)vi進(jìn)行計(jì)算了，這個(gè)參數(shù)就是我們要學(xué)習(xí)的 Graph Embedding
此時(shí)優(yōu)化函數(shù)就為
然后借用詞向量中的模型來計(jì)算這個(gè)概率即（理解：在一個(gè)隨機(jī)游走中，當(dāng)給定一個(gè)頂點(diǎn)vi時(shí)，出現(xiàn)在它的w窗口范圍內(nèi)頂點(diǎn)的概率）
往下直接用skip-gram模型來訓(xùn)練：輸入是一個(gè)V維的向量，其中只有一個(gè)是1，其余都是0(one-hot encoder), 所以隱藏層輸出只需要copy 參數(shù)矩陣W的第k行即可，最大的問題在于從隱藏層到輸出的softmax層的計(jì)算量很大(分母要把所有單詞加起來)，因此用 Hierarchical Softmax
