1 隨機(jī)游走定義

所謂隨機(jī)游走(random walk)，就是在網(wǎng)絡(luò)上不斷重復(fù)地隨機(jī)選擇游走路徑，最終形成一條貫穿網(wǎng)絡(luò)的路徑。

從一個(gè)頂點(diǎn)出發(fā)，然后按照一定的概率隨機(jī)移動(dòng)到一個(gè)鄰居節(jié)點(diǎn)，并將該節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)，如此循環(huán)執(zhí)行若干步，得到一條游走路徑。

下圖所示綠色部分即為一條隨機(jī)游走。

2?使用隨機(jī)游走的好處

2.1?并行化

隨機(jī)游走是局部的，對(duì)于一個(gè)大的網(wǎng)絡(luò)來(lái)說(shuō)，可以同時(shí)在不同的頂點(diǎn)開(kāi)始進(jìn)行一定長(zhǎng)度的隨機(jī)游走，多個(gè)隨機(jī)游走同時(shí)進(jìn)行，可以減少采樣的時(shí)間。

2.2 局部適應(yīng)性

可以適應(yīng)網(wǎng)絡(luò)局部的變化。網(wǎng)絡(luò)的演化通常是局部的點(diǎn)和邊的變化，這樣的變化只會(huì)對(duì)部分隨機(jī)游走路徑產(chǎn)生影響，因此在網(wǎng)絡(luò)的演化過(guò)程中不需要每一次都重新計(jì)算整個(gè)網(wǎng)絡(luò)的隨機(jī)游走。

?

3? python 實(shí)現(xiàn)隨機(jī)游走

networkx包的內(nèi)容可見(jiàn)python庫(kù)整理：networkx 包_劉文巾的博客-CSDN博客

先看一下我們要用到的圖

import networkx as nx import matplotlib.pyplot as plt G=nx.barbell_graph(5,4) nx.draw_networkx(G) plt.show()

然后我們實(shí)現(xiàn)隨機(jī)游走

import random #導(dǎo)入庫(kù)def random_walk(G,path_length,alpha,start=None):''' 實(shí)現(xiàn)一個(gè)截取隨機(jī)游走 G是我們要研究的圖 path_length：隨機(jī)游走的長(zhǎng)度 alpha：每次游走從start點(diǎn)開(kāi)始的概率 start：隨機(jī)游走的起始點(diǎn)'''if start==None:path=random.sample(list(G.nodes),1)#如果沒(méi)有設(shè)置起始點(diǎn)，那么我們就在圖中隨機(jī)選擇一個(gè)else:path=[start]while(len(path)<path_length): #如果沒(méi)有到達(dá)我們需要的隨機(jī)游走長(zhǎng)度cur_node=path[-1]#下一輪隨機(jī)游走的起點(diǎn)if(len(list(G.adj[cur_node]))>0):#如果這個(gè)“起點(diǎn)”還有相鄰點(diǎn)的話：if(random.random()>=alpha):path.extend(random.sample(list(G.adj[cur_node]),1))else:path.append(path[0]) #一定概率是跳轉(zhuǎn)到“起點(diǎn)”的鄰居，一定概率是跳到真正的起點(diǎn)else:breakreturn(path)random_walk(G,10,0.1) #[3, 3, 4, 5, 6, 5, 4, 1, 3, 2]

?

總結(jié)

以上是生活随笔為你收集整理的GNN笔记： random walk的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。