（1）隨機(jī)游走算法在文本摘要、關(guān)鍵詞提取、圖像分割等方面有著重要的應(yīng)用． 隨機(jī)游走( Ｒandom Walk)是一種狀態(tài)轉(zhuǎn)移的過程，在圖模型中，隨機(jī)游走即從一個指定的頂點(diǎn) u，隨機(jī)的移動到一個相鄰的頂點(diǎn) v 的過程． 隨機(jī)游走的隨機(jī)過程{ s0，s1，s2，…，sn} 稱為馬爾可夫( Markov) 鏈，從一個狀態(tài) si轉(zhuǎn)移到另一個狀態(tài) sj服從轉(zhuǎn)移概率 P( u，v) = P( st + 1= v | st= u) ，即一個狀態(tài)時刻 t 在 u 頂點(diǎn)，在時刻 t + 1 轉(zhuǎn)移到 v 頂點(diǎn)． 對于任意頂點(diǎn) u，轉(zhuǎn)移到相鄰頂點(diǎn)的概率之和為1，即∑vP( u，v) = 1．
（2）對于帶權(quán)重的圖 G，設(shè)頂點(diǎn) u 到頂點(diǎn) v 的權(quán)重為 w( u，v) ，頂點(diǎn) u 的度為 d( u) = ∑xw( u，x) ，其中 x 為頂點(diǎn) u 的所有鄰接頂點(diǎn)． 則頂點(diǎn) u 轉(zhuǎn)移到頂點(diǎn) v 的概率轉(zhuǎn)移 P( u，v) 為
將圖的隨機(jī)游走擴(kuò)展到帶權(quán)重的超圖 H( V，E，W) ，那么隨機(jī)游走可通過如下過程實(shí)現(xiàn): 對于起始頂點(diǎn) u，其中 u∈e，隨機(jī)選取超邊 e 的一個鄰接超邊 e'，然后在超邊 e'中隨機(jī)的選取一個頂點(diǎn) v，其中 v∈e'． 因此定義從頂點(diǎn) u 轉(zhuǎn)移到頂點(diǎn) v的概率轉(zhuǎn)移 P( u，v) 為
