頂點(diǎn)帶屬性網(wǎng)絡(luò)的鏈接預(yù)測(cè)研究.pdf

1、在科學(xué)研究的進(jìn)程當(dāng)中，任何學(xué)科都必然會(huì)遇到預(yù)測(cè)問(wèn)題，對(duì)復(fù)雜網(wǎng)絡(luò)的鏈接預(yù)測(cè)是數(shù)據(jù)挖掘領(lǐng)域內(nèi)一個(gè)極其重要的研究方向。在現(xiàn)實(shí)世界中，無(wú)論是自然界中存在的形形色色的復(fù)雜系統(tǒng)，還是我們?yōu)榉治鰡?wèn)題、解決問(wèn)題而創(chuàng)造的模型系統(tǒng)，都可以用復(fù)雜網(wǎng)絡(luò)去描述和刻畫。在這些系統(tǒng)之中，個(gè)體與個(gè)體間往往存在著復(fù)雜聯(lián)系。復(fù)雜網(wǎng)絡(luò)在構(gòu)建過(guò)程中，由于時(shí)間和空間或者實(shí)驗(yàn)條件的限制，難免有錯(cuò)誤或冗余的鏈接出現(xiàn)，還有不少潛在的鏈接并未探測(cè)到。再者，復(fù)雜網(wǎng)絡(luò)往往是隨時(shí)間動(dòng)態(tài)演化的

2、，其鏈接會(huì)不斷地添加或去除。因此，需要根據(jù)已知的網(wǎng)絡(luò)信息對(duì)缺失的鏈接以及未來(lái)的鏈接進(jìn)行預(yù)測(cè)，這就是網(wǎng)絡(luò)鏈接預(yù)測(cè)問(wèn)題。鏈接預(yù)測(cè)有助于我們更好地分析和認(rèn)識(shí)相關(guān)網(wǎng)絡(luò)。
　　早期的鏈接預(yù)測(cè)的途徑，主要是基于馬爾科夫鏈和機(jī)器學(xué)習(xí)等方法。隨著研究的深入，人們認(rèn)識(shí)到，網(wǎng)絡(luò)自身的拓?fù)浣Y(jié)構(gòu)能夠清晰地反應(yīng)出頂點(diǎn)之間的結(jié)構(gòu)相似性，而這種相似性往往揭示了它們之間是否存在鏈接。因此學(xué)者們提出了各種刻畫這種結(jié)構(gòu)相似性的指標(biāo)，例如CN，AA，Katz等，這些指

3、標(biāo)都顯示出了較好預(yù)測(cè)效果。在一些應(yīng)用問(wèn)題中，網(wǎng)絡(luò)的頂點(diǎn)自身帶有極其豐富的屬性信息。這些屬性反映了頂點(diǎn)所代表的對(duì)象的特性和內(nèi)容，這些信息也很大程度上影響著鏈接存在的可能性。如果能夠把結(jié)構(gòu)信息和屬性信息結(jié)合到一起，勢(shì)必能夠極大地提高鏈接預(yù)測(cè)算法的預(yù)測(cè)精度。
　　目前，如何將結(jié)構(gòu)信息和屬性信息有機(jī)地融合在一起，以提高鏈接預(yù)測(cè)質(zhì)量，還是一個(gè)有待探討的問(wèn)題。本文針對(duì)頂點(diǎn)帶屬性網(wǎng)絡(luò)的鏈接預(yù)測(cè)問(wèn)題，從頂點(diǎn)的結(jié)構(gòu)相似性和屬性相似性出發(fā)，研究如何有

4、機(jī)地融合結(jié)構(gòu)信息和屬性信息、設(shè)計(jì)高效的鏈接預(yù)測(cè)算法，以提高預(yù)測(cè)精度。
　　本文的研究工作和主要研究成果有:
　　(1)我們提出了一種基于相似度傳播的鏈接預(yù)測(cè)算法，把頂點(diǎn)的屬性相似度作為一種權(quán)重附加給每一條邊，結(jié)合最短路徑的算法，得到網(wǎng)絡(luò)中所有頂點(diǎn)間信息能力的大小。然后根據(jù)這種傳播能力的大小，按照設(shè)定的傳遞法則，使每一對(duì)頂點(diǎn)間的相似度都在整個(gè)網(wǎng)絡(luò)之間傳播，并在傳播過(guò)程中更新自身的值。在傳播過(guò)程收斂之后，便得到了每一對(duì)頂點(diǎn)之間相

5、似度，來(lái)反映他們之間存在鏈接的可能性。我們?cè)谙嚓P(guān)的數(shù)據(jù)集上進(jìn)行測(cè)試的結(jié)果表明，我們所提出的算法具有較高的預(yù)測(cè)精度。
　　(2)我們提出了基于參數(shù)選擇的鏈接預(yù)測(cè)算法，該算法利用Katz鏈接預(yù)測(cè)算法中需要確定的參數(shù)值，把頂點(diǎn)的屬性信息作為求得該參數(shù)最優(yōu)值的條件來(lái)求得該參數(shù)，使得結(jié)構(gòu)信息和屬性信息有效地結(jié)合。我們?cè)谙嚓P(guān)的數(shù)據(jù)集上進(jìn)行測(cè)試的結(jié)果表明，該算法可以取得高質(zhì)量的預(yù)測(cè)結(jié)果。
　　(3)我們提出了基于空間映射思想的鏈接預(yù)測(cè)算法