基于最短路徑的隨機(jī)游走算法研究與應(yīng)用.pdf

1、近年來，人們越來越多地關(guān)注數(shù)據(jù)集中數(shù)據(jù)點(diǎn)之間的關(guān)系。不同種類的網(wǎng)絡(luò)相繼涌現(xiàn)。有鏈接和節(jié)點(diǎn)類型都單一的同質(zhì)網(wǎng)絡(luò)如以朋友友誼為基礎(chǔ)建立起來的社交網(wǎng)站;以網(wǎng)絡(luò)鏈接形成的互聯(lián)網(wǎng)。另外還有多種鏈接和節(jié)點(diǎn)類型形成的異質(zhì)網(wǎng)絡(luò)如醫(yī)學(xué)領(lǐng)域病人，疾病與治療方法或者科學(xué)合作網(wǎng)中出版社，科學(xué)家與作品這些節(jié)點(diǎn)形成多種鏈接類型的異質(zhì)網(wǎng)。鏈路挖掘就是利用數(shù)據(jù)集合的鏈接信息進(jìn)行挖掘的技術(shù)。
　　近年來鏈路預(yù)測越來越受到關(guān)注。鏈路預(yù)測旨在評(píng)估復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)間連接的可

2、能性并做出預(yù)測。局部隨機(jī)游走LRW(Local Random Walk)是只考慮有限步的隨機(jī)游走，基于最短路徑的局部隨機(jī)游走方法LRWD(Local Random Walk withDistance)是利用最短路徑步數(shù)作為局部隨機(jī)游走有限步數(shù)。并提出最短路徑分步的概念以分析LRWD方法在不同復(fù)雜網(wǎng)絡(luò)上的性能。我們認(rèn)為隨機(jī)游走中游走者從初始點(diǎn)首次到達(dá)終點(diǎn)的概率在最終兩點(diǎn)連接的可能性指標(biāo)中起著最重要的作用。如此游走者都是按照自己的步數(shù)游走而

3、不是整個(gè)復(fù)雜網(wǎng)絡(luò)按照統(tǒng)一的一個(gè)步數(shù)游走。從整體性質(zhì)到局部性質(zhì)這種變化不僅為復(fù)雜網(wǎng)絡(luò)的研究提供一個(gè)新的視角而且證明了最短路徑在復(fù)雜網(wǎng)絡(luò)中的重要作用。最后作者還提出了最短路徑頻數(shù)分布和最短路徑分布熵的概念，并用它們來度量網(wǎng)絡(luò)動(dòng)態(tài)演化中表現(xiàn)出的聚集現(xiàn)象。
　　作者還將最短路徑和隨機(jī)游走思想應(yīng)用到聚類算法中形成新的k-means算法。新的聚類算法應(yīng)用數(shù)據(jù)點(diǎn)鏈接信息的方式不同于以往其他算法。新k-means算法是將數(shù)據(jù)點(diǎn)之間的距離轉(zhuǎn)化為隨機(jī)