基于符號(hào)網(wǎng)絡(luò)的邊值預(yù)測(cè)方法研究

佘宏俊，胡夢(mèng)緣

(1.東北財(cái)經(jīng)大學(xué) 數(shù)學(xué)與數(shù)量經(jīng)濟(jì)學(xué)院, 遼寧 大連 116025；2.中南財(cái)經(jīng)政法大學(xué) 工商管理學(xué)院，湖北 武漢 430073)

?

基于符號(hào)網(wǎng)絡(luò)的邊值預(yù)測(cè)方法研究

佘宏俊1，胡夢(mèng)緣2

(1.東北財(cái)經(jīng)大學(xué) 數(shù)學(xué)與數(shù)量經(jīng)濟(jì)學(xué)院, 遼寧 大連 116025；2.中南財(cái)經(jīng)政法大學(xué) 工商管理學(xué)院，湖北 武漢 430073)

針對(duì)社會(huì)網(wǎng)絡(luò)中存在的正負(fù)二元邊值關(guān)系，基于共同鄰居指標(biāo)法在識(shí)別社會(huì)網(wǎng)絡(luò)符號(hào)邊值問(wèn)題中的優(yōu)勢(shì)，提出了一種符號(hào)網(wǎng)絡(luò)下的邊值預(yù)測(cè)方法(ICN-Predict)。該符號(hào)網(wǎng)絡(luò)邊值預(yù)測(cè)方法有效結(jié)合了節(jié)點(diǎn)符號(hào)密度屬性和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征，避免了共同鄰居法預(yù)測(cè)選值敏感性問(wèn)題。通過(guò)實(shí)驗(yàn)仿真發(fā)現(xiàn)，ICN-Predict預(yù)測(cè)方法擴(kuò)大了符號(hào)網(wǎng)絡(luò)邊值預(yù)測(cè)的適用面，提高了邊值預(yù)測(cè)精度，同時(shí)表明進(jìn)一步提高預(yù)測(cè)精度的關(guān)鍵在于提高負(fù)值邊的預(yù)測(cè)準(zhǔn)確率。

符號(hào)網(wǎng)絡(luò)；共同鄰居；邊值預(yù)測(cè)

近年來(lái)，網(wǎng)絡(luò)圖分析在諸多領(lǐng)域有著廣泛的應(yīng)用，例如化學(xué)領(lǐng)域中物質(zhì)的分子結(jié)構(gòu)、互聯(lián)網(wǎng)范疇的虛擬社區(qū)關(guān)系及生物信息學(xué)等，這些領(lǐng)域中的大量數(shù)據(jù)都可以抽象建模為圖結(jié)構(gòu)并用于進(jìn)一步研究，基于網(wǎng)絡(luò)圖的鏈接關(guān)系預(yù)測(cè)已成為數(shù)據(jù)挖掘領(lǐng)域新的研究熱點(diǎn)。

應(yīng)用馬爾科夫鏈進(jìn)行網(wǎng)絡(luò)鏈接預(yù)測(cè)[1]、采用回歸模型[2]及蟻群算法[3]對(duì)網(wǎng)絡(luò)進(jìn)行分析是計(jì)算機(jī)領(lǐng)域?qū)ι鐣?huì)網(wǎng)絡(luò)進(jìn)行研究的一類重要方法。針對(duì)網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)，文獻(xiàn)[4]提出了相似性的相關(guān)定義，分析了社會(huì)網(wǎng)絡(luò)中許多主要指標(biāo)鏈路預(yù)測(cè)的效果?；诰W(wǎng)絡(luò)結(jié)構(gòu)的極大似然估計(jì)則是另一類進(jìn)行鏈路預(yù)測(cè)的方法，其中由CLAUSET等[5]提出的一種基于網(wǎng)絡(luò)層次結(jié)構(gòu)的極大似然鏈路預(yù)測(cè)方法在小規(guī)模層次結(jié)構(gòu)分明的網(wǎng)絡(luò)中效率較高。同時(shí)，上述這些鏈接預(yù)測(cè)方法在不同領(lǐng)域、學(xué)科都有著廣泛的實(shí)際應(yīng)用。在生物學(xué)中，蛋白質(zhì)相互作用的網(wǎng)絡(luò)結(jié)構(gòu)和新陳代謝網(wǎng)絡(luò)相關(guān)預(yù)測(cè)在文獻(xiàn)[6]中有所介紹，指出約有80%的蛋白質(zhì)關(guān)系尚未被發(fā)現(xiàn)，利用網(wǎng)絡(luò)邊值預(yù)測(cè)可以解決該問(wèn)題。而在社會(huì)關(guān)系網(wǎng)絡(luò)研究中往往會(huì)遇到數(shù)據(jù)缺失的情形，鏈接預(yù)測(cè)亦可用于準(zhǔn)確預(yù)測(cè)缺失的社會(huì)關(guān)系。該方法可用于虛擬社交網(wǎng)絡(luò)方面[7]，即通過(guò)已知部分節(jié)點(diǎn)類型的社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)信息去預(yù)測(cè)未知標(biāo)簽節(jié)點(diǎn)的類型，好友推薦模式是社會(huì)網(wǎng)絡(luò)預(yù)測(cè)理論的典型應(yīng)用。

國(guó)內(nèi)學(xué)者徐恪等[8]從測(cè)量的角度總結(jié)了在線社會(huì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、用戶行為和網(wǎng)絡(luò)演化方面，對(duì)常見(jiàn)的測(cè)量方法和典型的網(wǎng)絡(luò)拓?fù)鋮?shù)進(jìn)行了綜述。王剛等[9]提出了社會(huì)網(wǎng)絡(luò)中交易節(jié)點(diǎn)的選取及其信任關(guān)系計(jì)算方法，通過(guò)設(shè)計(jì)一個(gè)競(jìng)標(biāo)服務(wù)策略來(lái)調(diào)動(dòng)節(jié)點(diǎn)提供資源服務(wù)的積極性。張昱等[10]針對(duì)社會(huì)網(wǎng)絡(luò)中有權(quán)圖的鏈接預(yù)測(cè)問(wèn)題，提出了一個(gè)基于時(shí)間信息的鏈接預(yù)測(cè)方法，通過(guò)博客數(shù)據(jù)集驗(yàn)證了該方法相對(duì)于傳統(tǒng)方法效果更好。

符號(hào)網(wǎng)絡(luò)是社會(huì)網(wǎng)絡(luò)中邊值為正負(fù)兩種關(guān)系的二元復(fù)雜網(wǎng)絡(luò)。目前對(duì)該網(wǎng)絡(luò)邊值預(yù)測(cè)問(wèn)題的研究較少，其預(yù)測(cè)重點(diǎn)在于邊值的符號(hào)關(guān)系，傳統(tǒng)邊值符號(hào)預(yù)測(cè)多基于節(jié)點(diǎn)自身的屬性特征或網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。但是，對(duì)于互聯(lián)網(wǎng)上的社交網(wǎng)絡(luò)數(shù)據(jù)，很多用戶信息都是虛假的或是保密的，導(dǎo)致節(jié)點(diǎn)信息有誤，網(wǎng)絡(luò)結(jié)構(gòu)分離，難以獲得節(jié)點(diǎn)屬性及拓?fù)浣Y(jié)構(gòu)的真實(shí)情況。同時(shí)，判斷各種信息中哪些是對(duì)當(dāng)前社會(huì)網(wǎng)絡(luò)預(yù)測(cè)有用的，哪些信息是無(wú)用的也是一個(gè)重要問(wèn)題。因此，單獨(dú)采用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)或節(jié)點(diǎn)屬性相似度對(duì)符號(hào)網(wǎng)絡(luò)進(jìn)行邊值預(yù)測(cè)都存在一定的偏誤。筆者基于已有研究成果，提出一種基于共同鄰居的符號(hào)網(wǎng)絡(luò)改進(jìn)邊值預(yù)測(cè)方法(improved common neighbor-predict，ICN-Predict)。該方法較好地結(jié)合了節(jié)點(diǎn)屬性的相似性指標(biāo)和網(wǎng)絡(luò)結(jié)構(gòu)的相似性指標(biāo)，綜合兩個(gè)屬性特征對(duì)符號(hào)網(wǎng)絡(luò)邊值進(jìn)行預(yù)測(cè)。實(shí)驗(yàn)證明，與已有邊值預(yù)測(cè)算法相比，ICN-Predict方法有較高的預(yù)測(cè)精度。

1 基本理論

符號(hào)社會(huì)網(wǎng)絡(luò)中的邊值預(yù)測(cè)(link sign prediction)是指通過(guò)符號(hào)社會(huì)網(wǎng)絡(luò)內(nèi)已知的節(jié)點(diǎn)和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)關(guān)系等信息去預(yù)測(cè)尚未產(chǎn)生連接的兩個(gè)節(jié)點(diǎn)之間的正負(fù)關(guān)系。這種預(yù)測(cè)是對(duì)網(wǎng)絡(luò)中邊的未知符號(hào)關(guān)系進(jìn)行預(yù)測(cè)。符號(hào)社會(huì)網(wǎng)絡(luò)的邊值預(yù)測(cè)方法的主要思想來(lái)源于社會(huì)平衡理論和相似性度量算法。

1.1 社會(huì)平衡理論

所討論符號(hào)網(wǎng)絡(luò)的模型是采用CARTWRIGHT和HARARY在1956年提出的社會(huì)學(xué)結(jié)構(gòu)平衡理論。在社會(huì)平衡理論中，對(duì)于一個(gè)給定的三方關(guān)系u，v，w如圖1所示，從人際交往的直觀意義上解釋上述符號(hào)網(wǎng)絡(luò)：

(1)如果w是u的朋友，v是w的朋友，則v也是u的朋友。

(2)如果w是u的朋友，v是w的敵人，則v也是u的敵人。

(3)如果w是u的敵人，v是w的朋友，則v是u的敵人。

(4)如果w是u的敵人，v是w的敵人，則v是u的朋友。

圖1 符號(hào)網(wǎng)絡(luò)三方平衡關(guān)系

而圖1(b)中4種關(guān)系不符合社會(huì)學(xué)人際關(guān)系實(shí)際意義，暫時(shí)不做討論。

根據(jù)上述社會(huì)平衡理論，若已知其中任意兩點(diǎn)之間的邊值關(guān)系，則可對(duì)其第三方節(jié)點(diǎn)邊值之間的關(guān)系進(jìn)行預(yù)測(cè)，當(dāng)已知u，w節(jié)點(diǎn)之間的邊值s(u,w)和v，w節(jié)點(diǎn)之間的邊值s(v,w)，則可給出一個(gè)預(yù)測(cè)第三方節(jié)點(diǎn)關(guān)系邊值s(u,v)的定義，如式(1)所示：

s(u,v)=s(u,w)s(v,w)

(1)

由于在計(jì)算s(u,v)邊值符號(hào)過(guò)程中并沒(méi)有加入網(wǎng)絡(luò)圖的有向性標(biāo)識(shí)，因此基于社會(huì)平衡理論的邊值預(yù)測(cè)僅適用于包含無(wú)向關(guān)系的符號(hào)網(wǎng)絡(luò)。

1.2 相似性度量指標(biāo)

符號(hào)網(wǎng)絡(luò)邊值預(yù)測(cè)擬采用基于共同劃分的相似性指標(biāo)作為預(yù)測(cè)評(píng)價(jià)的依據(jù)。目前學(xué)術(shù)界已提出很多相似性度量指標(biāo)，包括CN(common neighbor)指標(biāo)法，Jaccard指標(biāo)法，Adamic/Adar指標(biāo)法和Preferential Attachment指標(biāo)法等，在上述諸多方法中，CN指標(biāo)法是其中預(yù)測(cè)過(guò)程簡(jiǎn)單且預(yù)測(cè)精度較高的一種。CN指標(biāo)法[11]將Score(x,y)定義為節(jié)點(diǎn)x，y之間共同鄰居的個(gè)數(shù)，即：Score(x,y)=|Γ(x)∩Γ(y)|。該定義表明兩個(gè)節(jié)點(diǎn)之間擁有的共同鄰居節(jié)點(diǎn)越多，則這兩個(gè)節(jié)點(diǎn)間的關(guān)聯(lián)可能性越大。并且CN指標(biāo)法能夠與社會(huì)平衡理論較好地結(jié)合，因此選擇該指標(biāo)作為相似度的度量標(biāo)準(zhǔn)。

2 基于共同鄰居的符號(hào)網(wǎng)絡(luò)預(yù)測(cè)方法

2.1 基于共同鄰居(CN-Predict)的預(yù)測(cè)方法

如上所述，CN指標(biāo)法是通過(guò)Score(x,y)相似度計(jì)算，建立節(jié)點(diǎn)之間的相似關(guān)系網(wǎng)。定義Score(x,y)為相似性指標(biāo)，Γ(x)為節(jié)點(diǎn)x的鄰居節(jié)點(diǎn)集合，s(x,y)為節(jié)點(diǎn)x與y之間的邊值符號(hào)。如果要預(yù)測(cè)節(jié)點(diǎn)u對(duì)v的邊值符號(hào)關(guān)系，則首先要找出u的鄰居節(jié)點(diǎn)集合Γ(u)及v的鄰居節(jié)點(diǎn)集合Γ(v)，然后根據(jù)Γ(u)∩Γ(v)中的節(jié)點(diǎn)集合與u，v的邊值符號(hào)情況，預(yù)估u對(duì)v的符號(hào)關(guān)系。

若兩個(gè)節(jié)點(diǎn)x,y之間共有的鄰居節(jié)點(diǎn)C，定義基于平衡理論的相似度BScore(x,y)為：

(2)

其中，Balance(xi,yi,ci)表示根據(jù)社會(huì)平衡關(guān)系理論預(yù)測(cè)出的xi，yi,ci三方正關(guān)系，即Balance(xi,yi,ci)=s(xi,ci)s(yi,ci)。設(shè)定相似度的閾值為λ，當(dāng)BScore(x,y)≥λ時(shí)，認(rèn)為節(jié)點(diǎn)x，y之間為正關(guān)系，即s(x,y)=1；當(dāng)BScore(x,y)<λ時(shí)，認(rèn)為節(jié)點(diǎn)x，y之間為負(fù)關(guān)系，即s(x,y)=-1。

在預(yù)測(cè)符號(hào)網(wǎng)絡(luò)邊值時(shí)，若只考慮鄰居節(jié)點(diǎn)的結(jié)構(gòu)特征，則會(huì)在某些情況下不能得到一個(gè)合理的預(yù)測(cè)值，有必要保留部分節(jié)點(diǎn)屬性信息來(lái)進(jìn)行預(yù)測(cè)，用于提高預(yù)測(cè)的準(zhǔn)確性。

2.2 改進(jìn)的邊值預(yù)測(cè)方法

為了完善CN預(yù)測(cè)方法中沒(méi)有共同鄰居及某些情況下預(yù)測(cè)的合理性，采用基于節(jié)點(diǎn)度數(shù)的預(yù)測(cè)方法進(jìn)行改進(jìn)。節(jié)點(diǎn)x的度數(shù)和Deg(x)=d+(x)+d-(x)代表了該節(jié)點(diǎn)的人際關(guān)系情況，在比較兩個(gè)節(jié)點(diǎn)之間連接邊的可能性時(shí)，可以用節(jié)點(diǎn)之間對(duì)集合T中節(jié)點(diǎn)的節(jié)點(diǎn)度數(shù)和相似性度量來(lái)表示它們之間的差異性。將這個(gè)差異定義為節(jié)點(diǎn)之間的相似性差異，那么基于節(jié)點(diǎn)度數(shù)的相似度可以定義為：

(3)

式(3)表明，|Deg(x)+Deg(y)|越小，則表示x與y之間的節(jié)點(diǎn)類型差異越大。

為避免由于DScore(x,y)對(duì)BScore(x,y)的值產(chǎn)生較大影響，而導(dǎo)致最終結(jié)果的誤差比較大，可通過(guò)適當(dāng)?shù)姆绞郊尤隓Score(x,y)的影響因素。現(xiàn)考慮以下3種情形，其中T=Γ(x)∩Γ(y)表示x與y節(jié)點(diǎn)之間的共同鄰居集合，TScore表示綜合相似度評(píng)分。

(1)當(dāng)Γ(x)∩Γ(y)=?時(shí)，此時(shí)節(jié)點(diǎn)x和y沒(méi)有共同鄰居，可以認(rèn)為節(jié)點(diǎn)x與y之間沒(méi)有任何相關(guān)性，即BScore=0，TScore=DScore。

(2)當(dāng)DScore(x,y)=0，Γ(x)∩Γ(y)≠?時(shí)，表示兩個(gè)節(jié)點(diǎn)x和y分別屬于不同的類型，共同鄰居關(guān)系決定兩節(jié)點(diǎn)之間的相關(guān)關(guān)系, 即TScore=BScore。

(3)當(dāng)DScore(x,y)≠0，Γ(x)∩Γ(y)≠?時(shí)，該情況下節(jié)點(diǎn)x和y的共同鄰居，以及它們自身的節(jié)點(diǎn)屬性值共同決定TScore的值。

綜上所述，基于CN的改進(jìn)預(yù)測(cè)方法為：

算法：ICN-Predict(srcnode, dstnode, truesign)

輸入：srcnode：待測(cè)邊的源節(jié)點(diǎn) dstnode：待測(cè)邊的目標(biāo)節(jié)點(diǎn) truesign：待測(cè)邊的實(shí)際符號(hào)值

輸出：true/false ：預(yù)測(cè)真值

foreachvi∈N(srcnode),vi∈N(dstnode) do

computeDeg(srcnode) andDeg(dstnode); //計(jì)算節(jié)點(diǎn)度數(shù)和

end foreach

if abs(Deg(srcnode))+abs(Deg(dstnode))≠0

computeDScore(srcnode, dstnode);//計(jì)算DScore

GetCmnNbh( srcnode, dstnode, CNbhV);//獲得共同鄰居集合CNbhV

foreachvi∈CNbhV do

S1=GetEdgeSign(srcnode,vi); //獲得邊值符號(hào)

S2=GetEdgeSign(vi, dstnode);

if(S1×S2=1) then

Balance++;

end foreach

BScore=Balance/CNbhV.Len; //計(jì)算BScore

if(CNbhV.Len=0 orBScore<α)then

do predict onDScore; //基于節(jié)點(diǎn)度數(shù)的預(yù)測(cè)

else

do predict onBScore;//基于共同鄰居的預(yù)測(cè)

令符號(hào)網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)為n，邊的個(gè)數(shù)為m，ICN-Predict算法中計(jì)算掃描符號(hào)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)對(duì)產(chǎn)生的結(jié)果，因此含有n個(gè)節(jié)點(diǎn)，m條邊的符號(hào)網(wǎng)絡(luò)對(duì)于鄰接表存儲(chǔ)形式而言，其總的時(shí)間復(fù)雜度為O(n+m)。

2.3 預(yù)測(cè)精度標(biāo)準(zhǔn)

預(yù)測(cè)精度即預(yù)測(cè)模型擬合的好壞程度，筆者采用AUC指標(biāo)作為預(yù)測(cè)精度的標(biāo)準(zhǔn)，每次隨機(jī)從測(cè)試集中選取一條邊與隨機(jī)選擇的并不存在的邊進(jìn)行比較，獨(dú)立地進(jìn)行比較n次，令n′表示測(cè)試過(guò)程中正值邊類型預(yù)測(cè)正確的個(gè)數(shù)且權(quán)重為1，n″表示測(cè)試過(guò)程中負(fù)值邊類型預(yù)測(cè)正確的個(gè)數(shù)且權(quán)重為0.5，將最終統(tǒng)計(jì)的預(yù)測(cè)正確率作為模型評(píng)價(jià)標(biāo)準(zhǔn)，則將AUC定義為：

(4)

3 實(shí)驗(yàn)測(cè)試

3.1 實(shí)驗(yàn)過(guò)程

符號(hào)網(wǎng)絡(luò)的邊值預(yù)測(cè)實(shí)驗(yàn)以隨機(jī)生成的符號(hào)網(wǎng)絡(luò)數(shù)據(jù)集G(30,700,0)(30個(gè)節(jié)點(diǎn)，700條邊，隨機(jī)符號(hào)網(wǎng)絡(luò)圖)，Gama數(shù)據(jù)集和Sam_aff數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)來(lái)源，實(shí)驗(yàn)仿真系統(tǒng)在Windows環(huán)境下開(kāi)發(fā)，采用C++語(yǔ)言，使用的是VS 2010開(kāi)發(fā)工具。分別采用上述4種方法對(duì)Gama數(shù)據(jù)集和Sam_aff數(shù)據(jù)集分別進(jìn)行預(yù)測(cè)分析統(tǒng)計(jì)。Gama數(shù)據(jù)集包含了16個(gè)Gahuku-Gama種族之間的社會(huì)網(wǎng)絡(luò)關(guān)系，其中正邊和負(fù)邊分別代表種族之間的同盟和敵對(duì)關(guān)系。Sam_aff數(shù)據(jù)集記錄了Sampson修道院中18個(gè)僧侶之間的人際關(guān)系情況，其邊值取值范圍在-3和3之間，分別代表不同的人際關(guān)系程度。為了簡(jiǎn)化討論，將Sam_aff數(shù)據(jù)集中的邊值元素統(tǒng)一處理為<+1,-1>的二值，公共數(shù)據(jù)集統(tǒng)計(jì)參數(shù)如表1所示。

表1 公共數(shù)據(jù)集統(tǒng)計(jì)參數(shù)

該實(shí)驗(yàn)從實(shí)驗(yàn)數(shù)據(jù)集的邊集中依次選擇待預(yù)測(cè)邊并刪除該邊，然后對(duì)該缺失邊使用上述4種預(yù)測(cè)方法對(duì)未知的邊值符號(hào)進(jìn)行預(yù)測(cè)，并將預(yù)測(cè)邊值結(jié)果與真實(shí)邊值進(jìn)行比較，記錄在結(jié)果集中，最后對(duì)符號(hào)網(wǎng)絡(luò)數(shù)據(jù)集中的所有邊值預(yù)測(cè)結(jié)果進(jìn)行統(tǒng)計(jì)分析得到實(shí)驗(yàn)最終結(jié)果。

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

實(shí)驗(yàn)結(jié)果如表2、表3和表4所示。第1列代表4種預(yù)測(cè)方法；第2列至第5列分別表示真實(shí)邊值和預(yù)測(cè)邊值符號(hào)的實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)，例如“+/+”代表真實(shí)邊值為正，預(yù)測(cè)邊值結(jié)果也為正的實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)；最后一列表示AUC值的計(jì)算結(jié)果。

表2 RandomGraph(30,700)預(yù)測(cè)實(shí)驗(yàn)結(jié)果

表3 Gama(16，116)預(yù)測(cè)實(shí)驗(yàn)結(jié)果

表2為隨機(jī)符號(hào)網(wǎng)絡(luò)數(shù)據(jù)集的預(yù)測(cè)統(tǒng)計(jì)結(jié)果，從表2中可以看出基于節(jié)點(diǎn)度數(shù)的預(yù)測(cè)(Deg-Predict)，基于共同鄰居的預(yù)測(cè)(CN-Predict)及改進(jìn)的基于共同鄰居預(yù)測(cè)方法(ICN-Predict)與隨機(jī)預(yù)測(cè)(Rnd-Predict)的預(yù)測(cè)精度52.7%相比分別下降了1.0%，10.3%，4.0%，證明這4種方法無(wú)法對(duì)隨機(jī)符號(hào)網(wǎng)絡(luò)進(jìn)行預(yù)測(cè)分析。隨機(jī)符號(hào)網(wǎng)絡(luò)是由隨機(jī)函數(shù)產(chǎn)生的網(wǎng)絡(luò)圖，其結(jié)構(gòu)本身沒(méi)有任何社會(huì)關(guān)系基礎(chǔ)，隨機(jī)產(chǎn)生的符號(hào)邊也沒(méi)有預(yù)測(cè)規(guī)律可循，因而均無(wú)法對(duì)隨機(jī)生成符號(hào)網(wǎng)絡(luò)的邊值進(jìn)行預(yù)測(cè)。

表4 Sam_aff(18，158)預(yù)測(cè)實(shí)驗(yàn)結(jié)果

Gama數(shù)據(jù)下的實(shí)驗(yàn)預(yù)測(cè)結(jié)果如表3所示，可以發(fā)現(xiàn)，對(duì)Gama數(shù)據(jù)集中116個(gè)邊值符號(hào)進(jìn)行預(yù)測(cè)后，ICN-Predict方法的預(yù)測(cè)精度最高，達(dá)到了86.2%，Rnd-Predict的預(yù)測(cè)精度最低，僅為50.0%，其他兩種方法中Deg-Predict的預(yù)測(cè)精度為62.9%，CN-Predict方法的預(yù)測(cè)精度為81.0%。Gama數(shù)據(jù)來(lái)源于社會(huì)人際關(guān)系的實(shí)地調(diào)查，實(shí)驗(yàn)結(jié)果表明，基于社會(huì)平衡理論的預(yù)測(cè)方法都能表現(xiàn)出良好的預(yù)測(cè)效果，其中ICN-Predict方法預(yù)測(cè)效果最佳。

Sam_aff數(shù)據(jù)集的預(yù)測(cè)結(jié)果如表4所示，由于Sam_aff數(shù)據(jù)集在數(shù)據(jù)分析之前進(jìn)行了歸一化預(yù)處理，因此相對(duì)于Gama數(shù)據(jù)集而言，其整體預(yù)測(cè)效果有所下降。其中，Rnd-Predict方法依然維持在50%左右的準(zhǔn)確率，而Deg-Predict方法和CN-Predict方法的預(yù)測(cè)精度分別為64.6%和74.1%，ICN-Predict方法仍然保持了最優(yōu)的預(yù)測(cè)精度，達(dá)到79.7%。該結(jié)果表明ICN-Predict方法在不同數(shù)據(jù)集下都能保持較優(yōu)的預(yù)測(cè)精度，具有一定的穩(wěn)健性。

基于Gama和Sam_aff數(shù)據(jù)集預(yù)測(cè)實(shí)驗(yàn)結(jié)果顯示，4種基于社會(huì)平衡理論的共同鄰居預(yù)測(cè)方法能夠?qū)ι鐣?huì)中普遍存在的符號(hào)網(wǎng)絡(luò)人際關(guān)系進(jìn)行較好的預(yù)測(cè)，而改進(jìn)后的共同鄰居預(yù)測(cè)方法(ICN-Predict)能夠在一定程度上提高對(duì)不同數(shù)據(jù)集的預(yù)測(cè)精度。同時(shí)從表3和表4的預(yù)測(cè)結(jié)果還可以發(fā)現(xiàn)，基于共同鄰居的預(yù)測(cè)方法對(duì)正值邊的預(yù)測(cè)準(zhǔn)確度遠(yuǎn)遠(yuǎn)高于負(fù)值邊的預(yù)測(cè)準(zhǔn)確度。

4 結(jié)論

基于社會(huì)網(wǎng)絡(luò)的鏈接預(yù)測(cè)已成為當(dāng)今熱門和前沿的研究領(lǐng)域，針對(duì)符號(hào)網(wǎng)絡(luò)的邊值預(yù)測(cè)，提出了一種基于共同鄰居的改進(jìn)預(yù)測(cè)方法(ICN-Predict)。改進(jìn)后的預(yù)測(cè)方法進(jìn)一步考慮了無(wú)鄰居和某些不合理的預(yù)測(cè)條件，在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)預(yù)測(cè)方法的基礎(chǔ)上，補(bǔ)充加入了基于節(jié)點(diǎn)符號(hào)密度的預(yù)測(cè)方法，從而提高了符號(hào)網(wǎng)絡(luò)邊值預(yù)測(cè)方法的適應(yīng)性。通過(guò)模擬實(shí)驗(yàn)比較驗(yàn)證了4種基于社會(huì)平衡理論的共同鄰居預(yù)測(cè)方法，實(shí)驗(yàn)結(jié)果表明，ICN-Predict方法能有效地提高符號(hào)網(wǎng)絡(luò)邊值的預(yù)測(cè)精度，同時(shí)表明了進(jìn)一步提高預(yù)測(cè)精度的關(guān)鍵在于提高負(fù)值邊的預(yù)測(cè)準(zhǔn)確率。但是該方法尚不能較好地對(duì)負(fù)值邊存在缺失的情況進(jìn)行預(yù)測(cè)分析，有必要尋找其他的相關(guān)理論支持。如何對(duì)動(dòng)態(tài)變化的社會(huì)網(wǎng)絡(luò)進(jìn)行實(shí)時(shí)有效的結(jié)構(gòu)分析，也是今后的一項(xiàng)重要研究工作。

[1] SARUKKAI R R. Link prediction and path analysis using markov chains[J]. Computer Networks, 2000,33(1):377-386.

[2] POPESCUL A, UNGAR L H. Statistical relational learning for link prediction[C]∥IJCAI Workshop on Learning Statistical Models from Relational Data.[S.l.]:[s.n.],2003:101-103.

[3] SHERKAT E, RAHGOZAR M, ASADPOUR M. Structural link prediction based on ant colony approach in social networks[J]. Physica A: Statistical Mechanics and its Applications, 2015(419):80-94.

[4] LIBEN N D, KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007,58(7):1019-1031.

[5] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008,453(7191):98-101.

[6] YU H, BRAUN P, YILDIRIM M A, et al. High-quality binary protein interaction map of the yeast interactome network[J]. Science, 2008,322(5898):104-110.

[7] GALLAGHER B, TONG H, ELIASSI-RAD T, et al. Using ghost edges for classification in sparsely labeled networks[C]∥Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.[S.l.]:ACM, 2008:256-264.

[8] 徐恪,張賽,陳昊,等.在線社會(huì)網(wǎng)絡(luò)的測(cè)量與分析[J].計(jì)算機(jī)學(xué)報(bào),2014,37(1):164-188.

[9] 王剛,桂小林.社會(huì)網(wǎng)絡(luò)中交易節(jié)點(diǎn)的選取及其信任關(guān)系計(jì)算方法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(2):368-383.

[10] 張昱,張恩德,李封,等.基于時(shí)間信息的社會(huì)網(wǎng)絡(luò)鏈接預(yù)測(cè)研究[J].計(jì)算機(jī)與數(shù)字工程,2012,40(11):50-51.

[11] NEWMAN M E J. Clustering and preferential attachment in growing networks[J]. Physical Review E, 2001,64(2):25102-25109.

SHE Hongjun:Doctorial Candidate; School of Mathematics, Dongbei University of Finance and Economics, Dalian 116025, China.

[編輯：王志全]

Link Prediction Based on Signed Network

SHEHongjun,HUMengyuan

The social network contains positive and negative edge relations. Based on the common neighbor index method in the recognition of social network signed edge, a kind of signed network link prediction method (ICN-Predict) was proposed. This method combines the signed density property of the node and the network topology characteristic effectively in order to avoid the problem of selecting sensitivity values in common neighbor method. From the experimental results, ICN-Predict method expands the application of the signed network prediction and improves the prediction accuracy. Meanwhile, it shows that the key point of high accuracy is the predictive ability of negative edge sign.

signed network; common neighbor; link prediction

2015-02-21.

佘宏俊(1985-)，男，湖北武漢人，東北財(cái)經(jīng)大學(xué)數(shù)學(xué)與數(shù)量經(jīng)濟(jì)學(xué)院博士研究生.

國(guó)家自然科學(xué)基金資助項(xiàng)目(71171035).

2095-3852(2015)05-0602-05

A

TP393

10.3963/j.issn.2095-3852.2015.05.017