基于網(wǎng)絡(luò)社區(qū)劃分的鏈路預(yù)測(cè)算法改進(jìn)與研究

李明東，辛政華，姜 飛,崔 琳，張守震，張海寧

(宿州學(xué)院 信息工程學(xué)院，安徽 宿州 234000)

鏈路預(yù)測(cè)在鏈路挖掘領(lǐng)域處于重要地位，目前在研究鏈路預(yù)測(cè)算法中需要更多考慮鄰接矩陣分解法來進(jìn)行預(yù)知.

根據(jù)網(wǎng)絡(luò)設(shè)置類型，可以通過加權(quán)方法進(jìn)行預(yù)測(cè)[1].利用當(dāng)前信息網(wǎng)絡(luò)下的社區(qū)結(jié)構(gòu)信息設(shè)計(jì)鏈路預(yù)測(cè)算法時(shí)，只是把社區(qū)結(jié)構(gòu)信息和結(jié)構(gòu)相似性算法進(jìn)行整合，沒有考慮到網(wǎng)絡(luò)的實(shí)際環(huán)境，因而無法挖掘網(wǎng)絡(luò)社區(qū)其他層面的信息架構(gòu)，通過新的信息架構(gòu)更新設(shè)計(jì)鏈路預(yù)測(cè)算法，是許多學(xué)者要解決的主要問題[2].

1 網(wǎng)絡(luò)社區(qū)劃分對(duì)應(yīng)的鏈路預(yù)測(cè)算法及優(yōu)化

基于網(wǎng)絡(luò)結(jié)構(gòu)之上的相似性預(yù)測(cè)方法包括網(wǎng)絡(luò)局部相似性信息和網(wǎng)絡(luò)全局相似性信息兩種，但是都沒有利用好社區(qū)原有的結(jié)構(gòu)信息.通過前期研究可知，由網(wǎng)絡(luò)的拓?fù)湫畔⑼诰蚓W(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，且依據(jù)此結(jié)構(gòu)信息提出了一種基于多分辨率社區(qū)劃分的鏈路預(yù)測(cè)算法.

網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)信息的鏈路預(yù)測(cè)算法，主要是通過對(duì)社區(qū)結(jié)構(gòu)進(jìn)行信息辨別，進(jìn)而解決面向社區(qū)的鏈路預(yù)測(cè)問題.將社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)按照差異化分辨率進(jìn)行劃分，從中提取網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的架構(gòu)信息，與之協(xié)同的鏈路預(yù)測(cè)算法主要包含以下步驟[3]：①對(duì)不同分辨率參數(shù)下的架構(gòu)信息進(jìn)行深挖；②設(shè)計(jì)相關(guān)模型用于計(jì)算分辨率不同的節(jié)點(diǎn)被劃分至相同社區(qū)的個(gè)數(shù)；③通過計(jì)算不同情形下的概率連接，推斷出概率高的連接出現(xiàn)缺失的可能性也最大.

1.1 網(wǎng)絡(luò)社區(qū)劃分

一般情形下網(wǎng)絡(luò)社區(qū)劃分要經(jīng)過以下循環(huán)來實(shí)現(xiàn).假設(shè)有一個(gè)無向加權(quán)結(jié)構(gòu)網(wǎng)絡(luò)G=(V,G)具有N個(gè)節(jié)點(diǎn).

第一步，將社區(qū)劃分進(jìn)行初始化.給不同的社區(qū)分配不同節(jié)點(diǎn)，從而可以得到相同個(gè)數(shù)的社區(qū)數(shù)和節(jié)點(diǎn)數(shù).

第二步，轉(zhuǎn)移節(jié)點(diǎn)所在的社區(qū).將i節(jié)點(diǎn)所在的社區(qū)位置帶到j(luò)節(jié)點(diǎn)的社區(qū)位置，將處在兩種社區(qū)下的模塊密度函數(shù)進(jìn)行計(jì)算獲取相應(yīng)增益.當(dāng)增益大于零時(shí)，表示節(jié)點(diǎn)i轉(zhuǎn)移成功，即新的社區(qū)劃分產(chǎn)生；反之，當(dāng)增益小于零時(shí)，代表節(jié)點(diǎn)i沒有變動(dòng)原有位置，仍在原來的社區(qū)內(nèi).如此反復(fù)循環(huán)上述兩個(gè)步驟，直到所有節(jié)點(diǎn)被全部遍歷，當(dāng)節(jié)點(diǎn)已經(jīng)轉(zhuǎn)移到別的社區(qū)，而且也不再產(chǎn)生新的增益時(shí)，算法運(yùn)行結(jié)束[4].

模塊度密度函數(shù)公式如(1)所示.

(1)

第三步，將原網(wǎng)絡(luò)進(jìn)行重建得到新的網(wǎng)絡(luò)，第二步轉(zhuǎn)移后的社區(qū)作為新網(wǎng)絡(luò)的節(jié)點(diǎn).和之前的網(wǎng)絡(luò)社區(qū)不同，新節(jié)點(diǎn)之間的連接邊存在權(quán)值，而且每個(gè)節(jié)點(diǎn)可能存在環(huán)邊，網(wǎng)絡(luò)社區(qū)劃分過程如圖1所示.

圖1 網(wǎng)絡(luò)社區(qū)劃分示意圖

1.2 鏈路預(yù)測(cè)算法的優(yōu)化

改進(jìn)的鏈路預(yù)測(cè)算法主要解決預(yù)測(cè)節(jié)點(diǎn)對(duì)之間存在邊的概率問題.假設(shè)一個(gè)無向加權(quán)網(wǎng)絡(luò)G=(V,E)具有N個(gè)節(jié)點(diǎn)，V表示節(jié)點(diǎn)集合，E表示邊集合，鏈路預(yù)測(cè)算法將預(yù)測(cè)出兩個(gè)節(jié)點(diǎn)之間存在邊的概率.本文預(yù)測(cè)算法將會(huì)通過網(wǎng)絡(luò)社區(qū)劃分的知識(shí)對(duì)鏈路預(yù)測(cè)算法進(jìn)行改進(jìn)，使鏈路預(yù)測(cè)算法的預(yù)測(cè)效果更好.改進(jìn)后的算法通過節(jié)點(diǎn)之間的相似性與最大似然估計(jì)兩種方法進(jìn)行預(yù)測(cè)[5].具體過程是：通過在給定的數(shù)據(jù)集G中，采取相似性計(jì)算方式，比較兩個(gè)節(jié)點(diǎn)對(duì)應(yīng)的相似度矩陣，如果兩個(gè)節(jié)點(diǎn)之間的相似度越大，則這兩個(gè)節(jié)點(diǎn)產(chǎn)生鏈接的可能性就越大.

最大似然估計(jì)方法的實(shí)現(xiàn)過程是：若網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)之間的連接有缺失，就認(rèn)為網(wǎng)絡(luò)整體的最大似然值會(huì)增大.網(wǎng)絡(luò)的似然值就是通過閉合環(huán)路的數(shù)量來定義，預(yù)測(cè)網(wǎng)絡(luò)中存在缺失邊的概率就等同于連上該邊后網(wǎng)絡(luò)的最大似然值.

2 網(wǎng)絡(luò)社區(qū)中特征對(duì)鏈路預(yù)測(cè)算法的影響

2.1 網(wǎng)絡(luò)社區(qū)中的社區(qū)相關(guān)性

網(wǎng)絡(luò)社區(qū)的相關(guān)性對(duì)節(jié)點(diǎn)對(duì)的鏈接預(yù)測(cè)有重要意義，然而網(wǎng)絡(luò)社區(qū)相關(guān)性指標(biāo)值和社區(qū)內(nèi)部結(jié)構(gòu)的組成關(guān)聯(lián)性不太明顯，其主要作用體現(xiàn)在網(wǎng)絡(luò)社區(qū)相關(guān)性指標(biāo)值能夠反映社區(qū)之間的各種有效性關(guān)系.網(wǎng)絡(luò)的任何一個(gè)社區(qū)可以當(dāng)作多個(gè)不同節(jié)點(diǎn)的集合[6]，根據(jù)鏈路預(yù)測(cè)機(jī)制與復(fù)雜網(wǎng)絡(luò)分析的互補(bǔ)性可知，通過鏈路預(yù)測(cè)算法來求得網(wǎng)絡(luò)社區(qū)的相關(guān)性，將得到的特征當(dāng)作新的度量，反過來解決鏈路預(yù)測(cè)問題.

社區(qū)節(jié)點(diǎn)之間的相似性作為網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的其中一個(gè)特征，從而將節(jié)點(diǎn)相似性轉(zhuǎn)化成社區(qū)相似性.通過鏈路預(yù)測(cè)算法得到社區(qū)結(jié)構(gòu)后，求解相關(guān)性，得到各個(gè)社區(qū)之間的相關(guān)程度.

2.2 規(guī)則推理構(gòu)建預(yù)測(cè)模型

通過規(guī)則推理構(gòu)建預(yù)測(cè)模型需要3個(gè)過程：①提取網(wǎng)絡(luò)信息中的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，利用COMM-ST方法提取相關(guān)信息；②計(jì)算出社區(qū)與社區(qū)之間的相關(guān)性;③利用規(guī)則推理的方法，估計(jì)出社區(qū)之間存在缺失鏈接的概率[7],整個(gè)預(yù)測(cè)模型構(gòu)建流程如圖2所示.

圖2 預(yù)測(cè)模型構(gòu)建流程圖

通過在算法中增加一個(gè)假設(shè)，即一個(gè)新節(jié)點(diǎn)接入后，與該節(jié)點(diǎn)相連接的節(jié)點(diǎn)和缺失鏈接的概率成正比例關(guān)系.通過規(guī)則推理對(duì)預(yù)測(cè)模型進(jìn)行估計(jì)，獲得缺失鏈接存在的概率，設(shè)置一種假設(shè)，進(jìn)一步實(shí)現(xiàn)估計(jì).假設(shè)在網(wǎng)絡(luò)里引入1個(gè)新的節(jié)點(diǎn)，則節(jié)點(diǎn)缺失鏈接存在的概率之和與其他相鄰節(jié)點(diǎn)的度成正相關(guān).通過社區(qū)結(jié)構(gòu)信息得到的社區(qū)相關(guān)性矩陣之間存在較大的誤差，從而導(dǎo)致算法失效.此外，由于訓(xùn)練集的比例不同，對(duì)于分布程度相似的網(wǎng)絡(luò)，該算法的預(yù)測(cè)結(jié)果優(yōu)于分布不一致的網(wǎng)絡(luò).如果網(wǎng)絡(luò)的度分布不一致，網(wǎng)絡(luò)結(jié)構(gòu)就產(chǎn)生不穩(wěn)定，這種情況會(huì)影響對(duì)網(wǎng)絡(luò)社區(qū)的劃分.

3 實(shí)驗(yàn)與結(jié)果分析

3.1 鏈路預(yù)測(cè)算法的數(shù)據(jù)集

網(wǎng)絡(luò)數(shù)據(jù)集是用來評(píng)估鏈路預(yù)測(cè)算法性能的標(biāo)準(zhǔn)數(shù)據(jù)集，可以用來判斷鏈路預(yù)測(cè)算法性能.實(shí)驗(yàn)中，給出點(diǎn)的個(gè)數(shù)分別為N=500和N=1000的網(wǎng)絡(luò)，用4個(gè)不同的參數(shù)進(jìn)行測(cè)試.其中N代表節(jié)點(diǎn)的數(shù)量，G代表度的分部數(shù)[8]，K代表社區(qū)規(guī)模的分部數(shù)，Y代表混合參數(shù)，表示多個(gè)社區(qū)之間鏈接數(shù)與總邊數(shù)的比值，數(shù)據(jù)分布情況如表1所列.

表1 網(wǎng)絡(luò)社區(qū)數(shù)據(jù)集分布情況

3.2 實(shí)驗(yàn)分析

LFR 網(wǎng)絡(luò)數(shù)據(jù)集是被用于評(píng)估社區(qū)檢測(cè)算法性能的標(biāo)準(zhǔn)數(shù)據(jù)集，這里用它來評(píng)估提出算法的預(yù)測(cè)性能.測(cè)試選用了FOOD、FOOTBALL、JAZZ 3個(gè)網(wǎng)絡(luò).假設(shè)FOOD網(wǎng)絡(luò)有136個(gè)節(jié)點(diǎn)，連接邊表示動(dòng)物之間的捕食關(guān)系；FOOTBALL網(wǎng)絡(luò)有120個(gè)節(jié)點(diǎn)，連接邊表示對(duì)手之間是朋友的關(guān)系；JAZZ網(wǎng)絡(luò)表示有220個(gè)節(jié)點(diǎn)，連接邊表示成員之間認(rèn)識(shí)的關(guān)系[9].測(cè)試具體情況如表2所列.

表2 網(wǎng)絡(luò)分配表

由于網(wǎng)絡(luò)的數(shù)據(jù)本身具有局限性，故采用先斷邊再重新連邊的方式來驗(yàn)證算法效果.把網(wǎng)絡(luò)中的不同社區(qū)看作是節(jié)點(diǎn)的融合，通過鏈路預(yù)測(cè)技術(shù)提取相關(guān)性特征，并將該特征當(dāng)作度量指標(biāo)，進(jìn)而得到精準(zhǔn)的鏈路預(yù)測(cè)和網(wǎng)絡(luò)社區(qū)的實(shí)際結(jié)構(gòu).用不同的鏈路預(yù)測(cè)算法去預(yù)測(cè)刪除連邊的網(wǎng)絡(luò)圖，都會(huì)產(chǎn)生一個(gè)相似值，實(shí)驗(yàn)結(jié)果如圖3所示.

圖3 多情景下的算法驗(yàn)證效果圖

通過圖3中(a)、(b)、(c)3個(gè)圖可以得出，當(dāng)時(shí)間間隔設(shè)置為2分鐘時(shí)，各自的預(yù)測(cè)比率均逐步增加，且CN算法的預(yù)測(cè)性能要比CAR 和LCII 算法低.(b)圖和(c)圖中，通過修改預(yù)測(cè)比率的初始值，對(duì)比相同時(shí)間的預(yù)測(cè)效果，可以看出3種算法的預(yù)測(cè)效果接近相同.同樣，CN算法和其他2種數(shù)據(jù)集的預(yù)測(cè)精度曲線是隨著訓(xùn)練集的增加而逐漸變大.此外，CN、CAR和LCII算法的預(yù)測(cè)結(jié)果很相似，直觀地表現(xiàn)出3種算法對(duì)應(yīng)的預(yù)測(cè)精度曲線接近重合.

改進(jìn)后的算法比經(jīng)典算法穩(wěn)定，可以得到更多關(guān)于候選節(jié)點(diǎn)的信息，在一定程度上，預(yù)測(cè)的命中率得到提高，使預(yù)測(cè)結(jié)果更加精準(zhǔn).

4 總結(jié)

本文針對(duì)基于網(wǎng)絡(luò)社區(qū)劃分的鏈路預(yù)測(cè)算法進(jìn)行改進(jìn)探究，能夠有效解決網(wǎng)絡(luò)中存在缺失鏈接的問題.將網(wǎng)絡(luò)先劃分成不同的社區(qū)結(jié)構(gòu)，以此來獲得社區(qū)的內(nèi)部架構(gòu)情況，然后將獲得的信息運(yùn)用鏈路預(yù)測(cè)算法進(jìn)行預(yù)測(cè).改進(jìn)后的算法不僅可以解決一些社區(qū)結(jié)構(gòu)不穩(wěn)定的網(wǎng)絡(luò)，也能解決社區(qū)信息不準(zhǔn)確的問題.該算法可以將不同的社區(qū)進(jìn)行緊密聯(lián)系，提高社區(qū)之間的相關(guān)性，提高預(yù)測(cè)的命中率.