【摘要】：伴隨著科技社會的迅速發(fā)展和網(wǎng)絡(luò)信息技術(shù)的進(jìn)步,復(fù)雜網(wǎng)絡(luò)的鏈接預(yù)測的研究有重要的現(xiàn)實和理論研究意義,已經(jīng)成為近年來的研究熱點,廣泛應(yīng)用到多種領(lǐng)域中,如社會科學(xué)、計算機(jī)科學(xué)、復(fù)雜系統(tǒng)等一些領(lǐng)域。鏈接預(yù)測的含義是通過已知的網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來對缺失的鏈接和未來可能產(chǎn)生的鏈接進(jìn)行預(yù)測。這種預(yù)測既包含了對未知鏈接(網(wǎng)絡(luò)中實際存在但尚未被我們探測到的鏈路)的預(yù)測也包含了對未來鏈接(網(wǎng)絡(luò)中目前不存在,但應(yīng)該存在或者未來很可能存在的鏈路)的預(yù)測。鏈路預(yù)測相關(guān)研究不僅能夠推動網(wǎng)絡(luò)科學(xué)和信息科學(xué)理論上的發(fā)展,而且具有巨大的實際應(yīng)用價值,譬如可以進(jìn)行在線社交推薦、指導(dǎo)蛋白質(zhì)的相互作用實驗、找出交通傳輸網(wǎng)絡(luò)中有特別重要作用的路徑等。在現(xiàn)實世界中,目前大多數(shù)的鏈接預(yù)測算法都是基于無向網(wǎng)絡(luò)的,但是現(xiàn)在許多社會網(wǎng)絡(luò)中的連接都是有方向的。社交網(wǎng)絡(luò)正在不斷融入人們的日常生活,近年來facebook、Twitter、新浪微博等社交網(wǎng)站層出不窮,成為信息分享和傳播的重要途徑。對于類似Twitter的社交網(wǎng)絡(luò),用戶關(guān)系的有向性是普遍存在的,因此預(yù)測連接是否存在的同時,也有必要預(yù)測鏈接的方向。本文針對有向網(wǎng)絡(luò)的特性,融合網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息和關(guān)系的相似性,設(shè)計精準(zhǔn)高效的鏈接預(yù)測算法。本文的主要研究工作和成果如下:(1)提出了一種基于抽樣的有向圖的單源鏈接預(yù)測算法。我們通過設(shè)定適當(dāng)?shù)某闃哟笮?可以將相似度的誤差限制在一個給定的閾值范圍內(nèi)。然后根據(jù)設(shè)定的抽樣大小產(chǎn)生路徑的樣本集。然后基于抽樣路徑來計算給定頂點的相似性得分,對于每條路徑中的每一個子路徑在Katz指標(biāo)上加上相應(yīng)的值,以得到近似的Katz指標(biāo)。由于只要基于抽樣路徑來計算給定頂點的相似性得分,該算法可以大大減少計算時間。通過在實際網(wǎng)絡(luò)上的實驗結(jié)果顯示,我們的算法可以獲得高精度的預(yù)測結(jié)果。(2)提出了一種基于遺傳算法的有向網(wǎng)絡(luò)的鏈接預(yù)測算法。我們擬對頂點的排序方式進(jìn)行編碼,作為遺傳算法的個體表達(dá)形式。我們首先隨機(jī)產(chǎn)生若干個初始個體,每一個個體代表一個排序方案,然后計算該排序方案的適應(yīng)度,用賭輪法選取新一輪的該選個體集合,再使用交叉、變異操作,產(chǎn)生新一代的群體。重復(fù)上述操作,直至收斂到最優(yōu)解。我們擬通過遺傳算法得到頂點的排序分,然后通過比較兩個頂點的排序分來確定它們間鏈接的方向,還可以根據(jù)兩個頂點排序分之間的差異大小估計該鏈接出現(xiàn)的概率。通過在實際網(wǎng)絡(luò)上的實驗結(jié)果顯示,我們的算法可以找出有向網(wǎng)絡(luò)中頂點的最優(yōu)的近似排序來解決頂點之間鏈接的方向預(yù)測,可以獲得高精度的預(yù)測結(jié)果。(3)提出了一種基于生成樹的有向圖頂點排序的算法。我們試圖找到一種排序方法,即對任一頂點定義一個序號,使得對任一有向邊上開始點的序號都要小于終點的序號。為了計算這種序號,我們對該有向圖構(gòu)造相應(yīng)的無向圖,然后對每一頂點觀察其為根頂點的在兩個圖上的生成樹,最后通過用該頂點的兩個的生成樹的差異來衡量頂點的排序值。實驗結(jié)果顯示,我們的算法可以得到最優(yōu)化的頂點排序,取得好的預(yù)測質(zhì)量。
【學(xué)位授予單位】：揚州大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5
【圖文】：

這些個體將按選擇的數(shù)量被復(fù)制。在計算機(jī)輔助實現(xiàn)采用以下方法：根據(jù)個體的排序，按選擇概率ＰＯＯ計算累計概率邋＝邐。算法產(chǎn)生？個隨機(jī)數(shù)ｖ對每一個隨機(jī)數(shù)，判斷其是否落在是，則選擇相應(yīng)的；ｃ，進(jìn)入下一代。這樣，可以得到選擇復(fù)制后的看出適應(yīng)值越大的染色體被選中（復(fù)制）的概率也越大。逡逑）交叉操作逡逑是把兩個父代個體的部分結(jié)構(gòu)加以重組而生成新個體的操作。交叉的個體具有多樣性，擴(kuò)大解的搜索空間，使個體對應(yīng)的解逐步逼定的概率凡選擇一對個體ｘ和ｙ進(jìn)行交叉，設(shè)ｘ＝（ｘｉ辦．．．士），ｉｘ中隨機(jī)選取要交叉的區(qū)域［／，／邋＋邋Ａ邋－１］，然后找出與ｘ，，；ｃ，＋１，．．．，合＾受它們依次為：＾：＾廣？＾＾然后將＆與＾＾交換＊＾＾．】，．．：設(shè)ｘ＝（３，２，ｌ，５，４），尸（４，５，３，１，２），設(shè)要交換的區(qū)域為［３，４］，則凡．與／的陰影部分所示：逡逑Ａ

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 崔秋月;劉娟;董暢暢;;超歐拉和雙有向跡的強(qiáng)積有向圖[J];四川師范大學(xué)學(xué)報(自然科學(xué)版);2018年04期

2 原軍;劉愛霞;;局部內(nèi)(外)半完全有向圖可跡的充分條件[J];應(yīng)用數(shù)學(xué)學(xué)報;2016年02期

3 韓婷婷;李瑞娟;;圓有向圖中的泛弧[J];貴州師范大學(xué)學(xué)報(自然科學(xué)版);2017年01期

4 崔秋月;劉娟;;關(guān)于超歐拉的冪有向圖[J];廊坊師范學(xué)院學(xué)報(自然科學(xué)版);2017年03期

5 董暢暢;劉娟;;超歐拉路可合并有向圖及半完全有向圖（英文）[J];新疆師范大學(xué)學(xué)報(自然科學(xué)版);2017年03期

6 崔建;葉旺;;圓有向圖的(1,2)步競爭圖中存在哈密爾頓圈的條件[J];重慶工商大學(xué)學(xué)報(自然科學(xué)版);2017年06期

7 盧永紅;;循環(huán)有向圖的距離和與平均距離[J];山西師范大學(xué)學(xué)報(自然科學(xué)版);2014年01期

8 張新鴻;李瑞娟;李勝家;;圓有向圖的(i,κ)步競爭圖[J];應(yīng)用數(shù)學(xué)學(xué)報;2013年06期

9 張新鴻;李瑞娟;李勝家;;關(guān)于強(qiáng)哈密爾頓連通有向圖的一個反例[J];山西大學(xué)學(xué)報(自然科學(xué)版);2012年01期

10 高敬振;楊化美;;有向圖極大與超級局部邊連通性的依賴團(tuán)數(shù)的度序列條件[J];山東科學(xué);2012年04期

相關(guān)會議論文 前10條

1 李剛;童

本文編號：2748151