基于改進(jìn)蟻群優(yōu)化算法與子圖演化,提出了一種新型非監(jiān)督社交網(wǎng)絡(luò)鏈路預(yù)測(cè)（SE-ACO）方法。該方法首先在社交網(wǎng)絡(luò)圖中確定特殊子圖;然后研究子圖演化以預(yù)測(cè)圖中的新鏈接,并用蟻群優(yōu)化算法定位特殊子圖;最后針對(duì)所提方法使用不同網(wǎng)絡(luò)拓?fù)洵h(huán)境與數(shù)據(jù)集進(jìn)行檢驗(yàn)。結(jié)果表明,與其他無(wú)監(jiān)督社交網(wǎng)絡(luò)預(yù)測(cè)算法相比,所提SE-ACO方法在多數(shù)數(shù)據(jù)集上的評(píng)估結(jié)果較好,且運(yùn)行時(shí)間較短,這表明圖形結(jié)構(gòu)在鏈路預(yù)測(cè)算法中起重要作用。 

【文章來(lái)源】：通信學(xué)報(bào). 2020,41(12)北大核心EICSCD

【文章頁(yè)數(shù)】：15 頁(yè)

【部分圖文】：

公開(kāi)標(biāo)準(zhǔn)數(shù)據(jù)集中基于ROC曲線(xiàn)下面積的幾種算法的比較結(jié)果

單個(gè)關(guān)系無(wú)向網(wǎng)絡(luò)中某節(jié)點(diǎn)和某社群間可能的相關(guān)性如圖1所示。圖1中第一層顯示了節(jié)點(diǎn)和社群的最簡(jiǎn)單關(guān)系，該層中單個(gè)關(guān)系無(wú)向網(wǎng)絡(luò)中僅存在一個(gè)鏈接，如時(shí)刻t的快照所示。時(shí)刻t的快照表示一種網(wǎng)絡(luò)結(jié)構(gòu)，鏈路預(yù)測(cè)算法用該結(jié)構(gòu)預(yù)測(cè)下個(gè)快照中的新鏈接。如前所述，每2個(gè)實(shí)體間至少應(yīng)有一個(gè)鏈接，這樣才能預(yù)測(cè)下個(gè)快照中的鏈接。圖1中的2個(gè)實(shí)體分別為左側(cè)的源節(jié)點(diǎn)和右側(cè)的目標(biāo)社群。第一層中未保留鏈接來(lái)預(yù)測(cè)網(wǎng)絡(luò)中的下一快照。第二層的目標(biāo)社群由2個(gè)節(jié)點(diǎn)組成，該層中時(shí)刻t的快照表示源節(jié)點(diǎn)與社群間的關(guān)聯(lián)，時(shí)刻t+1的快照表示可創(chuàng)建的可能鏈接（虛線(xiàn)）。由于所有鏈接和節(jié)點(diǎn)的權(quán)重相同，因此圖1中未描繪其他可能的同構(gòu)交互。第二層中有4種不同的關(guān)系，因此存在4種不同的可能鏈接。第四層是本文關(guān)注點(diǎn)的重點(diǎn)，其群體結(jié)構(gòu)為三角關(guān)系，左右兩部分分別有2個(gè)可能的鏈接。本文將講述如何根據(jù)第四層的子圖結(jié)構(gòu)來(lái)預(yù)測(cè)鏈接。而第三層中為最常見(jiàn)的社交網(wǎng)絡(luò)結(jié)構(gòu)，在此不做贅述。圖1所示四大層次并不是如今算力所能解決的，還可以考慮更多節(jié)點(diǎn)、更復(fù)雜的群體結(jié)構(gòu)，但由于找出這些的群體成本更高，因此本文未考慮更復(fù)雜的層次，僅示例社交網(wǎng)絡(luò)中兩實(shí)體間更復(fù)雜的交互層次交互關(guān)系，如圖2所示。圖1中的第四層定義了本文所述方法，具有一個(gè)節(jié)點(diǎn)和一個(gè)三角關(guān)系，且三角關(guān)系中至少存在一條公共邊。第四層有2個(gè)子圖(a)和(b)。由于子圖(b)的結(jié)構(gòu)屬性多于子圖(a)，而結(jié)構(gòu)屬性越多，預(yù)測(cè)出正確鏈接的機(jī)會(huì)就越大，故子圖(b)價(jià)值更大。為證明這一觀點(diǎn)，本文對(duì)比了根據(jù)子圖(a)與子圖(b)所預(yù)測(cè)的鏈接的準(zhǔn)確性。首先從社交網(wǎng)絡(luò)樣本中提取出子圖(a)和子圖(b)，然后考察了作為潛在鏈接的所有潛在鏈接（即圖1中的虛線(xiàn)），最后根據(jù)精度度量對(duì)比了這2個(gè)子圖所預(yù)測(cè)出的鏈接質(zhì)量。對(duì)比結(jié)果顯示本文觀點(diǎn)是正確的，即如果使用更多的結(jié)構(gòu)屬性，可以更正確地預(yù)測(cè)鏈接。Huang[31]的實(shí)驗(yàn)也證實(shí)了該結(jié)論，具體遍歷與循環(huán)數(shù)計(jì)算方式參考文獻(xiàn)[31]。因此，根據(jù)黃璐等[32]提出的概率模型，子圖(b)中僅有一條邊不存在的概率要大于子圖(a)中2個(gè)鏈接都不存在的概率。本文對(duì)圖1的其他層也進(jìn)行了同樣的實(shí)驗(yàn)，并將其結(jié)果與第四層結(jié)果進(jìn)行了對(duì)比，發(fā)現(xiàn)第四層中的子圖結(jié)構(gòu)更有利于社交網(wǎng)絡(luò)情景中的鏈路預(yù)測(cè)，故本文用第四層的子圖結(jié)構(gòu)來(lái)進(jìn)行社交網(wǎng)絡(luò)鏈路預(yù)測(cè)。

圖1中的第四層定義了本文所述方法，具有一個(gè)節(jié)點(diǎn)和一個(gè)三角關(guān)系，且三角關(guān)系中至少存在一條公共邊。第四層有2個(gè)子圖(a)和(b)。由于子圖(b)的結(jié)構(gòu)屬性多于子圖(a)，而結(jié)構(gòu)屬性越多，預(yù)測(cè)出正確鏈接的機(jī)會(huì)就越大，故子圖(b)價(jià)值更大。為證明這一觀點(diǎn)，本文對(duì)比了根據(jù)子圖(a)與子圖(b)所預(yù)測(cè)的鏈接的準(zhǔn)確性。首先從社交網(wǎng)絡(luò)樣本中提取出子圖(a)和子圖(b)，然后考察了作為潛在鏈接的所有潛在鏈接（即圖1中的虛線(xiàn)），最后根據(jù)精度度量對(duì)比了這2個(gè)子圖所預(yù)測(cè)出的鏈接質(zhì)量。對(duì)比結(jié)果顯示本文觀點(diǎn)是正確的，即如果使用更多的結(jié)構(gòu)屬性，可以更正確地預(yù)測(cè)鏈接。Huang[31]的實(shí)驗(yàn)也證實(shí)了該結(jié)論，具體遍歷與循環(huán)數(shù)計(jì)算方式參考文獻(xiàn)[31]。因此，根據(jù)黃璐等[32]提出的概率模型，子圖(b)中僅有一條邊不存在的概率要大于子圖(a)中2個(gè)鏈接都不存在的概率。本文對(duì)圖1的其他層也進(jìn)行了同樣的實(shí)驗(yàn)，并將其結(jié)果與第四層結(jié)果進(jìn)行了對(duì)比，發(fā)現(xiàn)第四層中的子圖結(jié)構(gòu)更有利于社交網(wǎng)絡(luò)情景中的鏈路預(yù)測(cè)，故本文用第四層的子圖結(jié)構(gòu)來(lái)進(jìn)行社交網(wǎng)絡(luò)鏈路預(yù)測(cè)。算法1描述了SE-ACO算法的具體過(guò)程，其目的是由社交網(wǎng)絡(luò)在時(shí)刻t的快照找出圖1中子圖(a)與子圖(b)，然后預(yù)測(cè)這些子圖中在時(shí)刻t+1的快照的潛在鏈接（即圖1中的虛線(xiàn)鏈接）。接下來(lái)，根據(jù)蟻群優(yōu)化算法找出的社交網(wǎng)絡(luò)中的三角關(guān)系。找到三角關(guān)系后，本文試圖根據(jù)這些三角關(guān)系找出圖1中的子圖(a)與子圖(b)。由于某些鏈接在多個(gè)子圖結(jié)構(gòu)中是共用的，故其評(píng)分會(huì)更高。最后，本文按評(píng)分降序排列得出預(yù)測(cè)鏈接的列表。

【參考文獻(xiàn)】：
期刊論文
[1]基于資源傳輸匹配度的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)方法[J]. 劉樹(shù)新,李星,陳鴻昶,王凱.  通信學(xué)報(bào). 2020(06)
[2]一種基于資源傳輸路徑拓?fù)溆行缘逆溌奉A(yù)測(cè)方法[J]. 王凱,李星,蘭巨龍,衛(wèi)紅權(quán),劉樹(shù)新.  電子與信息學(xué)報(bào). 2020(03)
[3]圖神經(jīng)網(wǎng)絡(luò)[J]. 白鉑,劉玉婷,馬馳騁,王光輝,閆桂英,閆凱,張明,周志恒.  中國(guó)科學(xué):數(shù)學(xué). 2020(03)
[4]基于層次化混合特征圖的鏈路預(yù)測(cè)方法[J]. 李冬,申德榮,寇月,林夢(mèng)兒,聶鐵錚,于戈.  中國(guó)科學(xué):信息科學(xué). 2020(02)
[5]基于圖神經(jīng)網(wǎng)絡(luò)的動(dòng)態(tài)網(wǎng)絡(luò)異常檢測(cè)算法[J]. 郭嘉琰,李榮華,張巖,王國(guó)仁.  軟件學(xué)報(bào). 2020(03)
[6]基于圖聚類(lèi)與蟻群算法的社交網(wǎng)絡(luò)聚類(lèi)算法[J]. 葉小鶯,萬(wàn)梅,唐蓉,謝云,陳桂宏,李強(qiáng).  計(jì)算機(jī)應(yīng)用研究. 2020(06)
[7]基于加權(quán)網(wǎng)絡(luò)鏈路預(yù)測(cè)的新興技術(shù)主題識(shí)別研究[J]. 黃璐,朱一鶴,張嶷.  情報(bào)學(xué)報(bào). 2019(04)
[8]基于信息融合的概率矩陣分解鏈路預(yù)測(cè)方法[J]. 王智強(qiáng),梁吉業(yè),李茹.  計(jì)算機(jī)研究與發(fā)展. 2019(02)
[9]基于深度卷積神經(jīng)網(wǎng)絡(luò)的多節(jié)點(diǎn)間鏈路預(yù)測(cè)方法[J]. 舒堅(jiān),張學(xué)佩,劉琳嵐,楊志勇.  電子學(xué)報(bào). 2018(12)
[10]基于邊重要度的矩陣分解鏈路預(yù)測(cè)算法[J]. 郭麗媛,王智強(qiáng),梁吉業(yè).  模式識(shí)別與人工智能. 2018(02)



本文編號(hào)：3366238