佘宏俊，胡夢緣

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

?

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

佘宏俊1，胡夢緣2

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

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

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

近年來，網(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ù)測已成為數(shù)據(jù)挖掘領(lǐng)域新的研究熱點(diǎn)。

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

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

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

1 基本理論

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

1.1 社會平衡理論

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

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

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

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

(1)

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

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

符號網(wǎng)絡(luò)邊值預(yù)測擬采用基于共同劃分的相似性指標(biāo)作為預(yù)測評價的依據(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ù)測過程簡單且預(yù)測精度較高的一種。CN指標(biāo)法[11]將Score(x,y)定義為節(jié)點(diǎn)x，y之間共同鄰居的個數(shù)，即：Score(x,y)=|Γ(x)∩Γ(y)|。該定義表明兩個節(jié)點(diǎn)之間擁有的共同鄰居節(jié)點(diǎn)越多，則這兩個節(jié)點(diǎn)間的關(guān)聯(lián)可能性越大。并且CN指標(biāo)法能夠與社會平衡理論較好地結(jié)合，因此選擇該指標(biāo)作為相似度的度量標(biāo)準(zhǔn)。

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

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

如上所述，CN指標(biāo)法是通過Score(x,y)相似度計算，建立節(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之間的邊值符號。如果要預(yù)測節(jié)點(diǎn)u對v的邊值符號關(guān)系，則首先要找出u的鄰居節(jié)點(diǎn)集合Γ(u)及v的鄰居節(jié)點(diǎn)集合Γ(v)，然后根據(jù)Γ(u)∩Γ(v)中的節(jié)點(diǎn)集合與u，v的邊值符號情況，預(yù)估u對v的符號關(guān)系。

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

(2)

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

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

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

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

(3)

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

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

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

(2)當(dāng)DScore(x,y)=0，Γ(x)∩Γ(y)≠?時，表示兩個節(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)≠?時，該情況下節(jié)點(diǎn)x和y的共同鄰居，以及它們自身的節(jié)點(diǎn)屬性值共同決定TScore的值。

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

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

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

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

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

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

end foreach

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

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

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

foreachvi∈CNbhV do

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

S2=GetEdgeSign(vi, dstnode);

if(S1×S2=1) then

Balance++;

end foreach

BScore=Balance/CNbhV.Len; //計算BScore

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

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

else

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

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

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

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

(4)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

基于社會網(wǎng)絡(luò)的鏈接預(yù)測已成為當(dāng)今熱門和前沿的研究領(lǐng)域，針對符號網(wǎng)絡(luò)的邊值預(yù)測，提出了一種基于共同鄰居的改進(jìn)預(yù)測方法(ICN-Predict)。改進(jìn)后的預(yù)測方法進(jìn)一步考慮了無鄰居和某些不合理的預(yù)測條件，在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)預(yù)測方法的基礎(chǔ)上，補(bǔ)充加入了基于節(jié)點(diǎn)符號密度的預(yù)測方法，從而提高了符號網(wǎng)絡(luò)邊值預(yù)測方法的適應(yīng)性。通過模擬實(shí)驗(yàn)比較驗(yàn)證了4種基于社會平衡理論的共同鄰居預(yù)測方法，實(shí)驗(yàn)結(jié)果表明，ICN-Predict方法能有效地提高符號網(wǎng)絡(luò)邊值的預(yù)測精度，同時表明了進(jìn)一步提高預(yù)測精度的關(guān)鍵在于提高負(fù)值邊的預(yù)測準(zhǔn)確率。但是該方法尚不能較好地對負(fù)值邊存在缺失的情況進(jìn)行預(yù)測分析，有必要尋找其他的相關(guān)理論支持。如何對動態(tài)變化的社會網(wǎng)絡(luò)進(jìn)行實(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] 徐恪,張賽,陳昊,等.在線社會網(wǎng)絡(luò)的測量與分析[J].計算機(jī)學(xué)報,2014,37(1):164-188.

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

[10] 張昱,張恩德,李封,等.基于時間信息的社會網(wǎng)絡(luò)鏈接預(yù)測研究[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-)，男，湖北武漢人，東北財經(jīng)大學(xué)數(shù)學(xué)與數(shù)量經(jīng)濟(jì)學(xué)院博士研究生.

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

2095-3852(2015)05-0602-05

A

TP393

10.3963/j.issn.2095-3852.2015.05.017