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

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

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

【部分圖文】：

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

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

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

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



本文編號：3366238