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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

1 李剛;童

本文編號(hào)：2748151