佘宏俊，胡夢緣

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

?

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

佘宏俊1，胡夢緣2

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

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

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

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

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

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

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

1 基本理論

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

1.1 社會平衡理論

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

(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)絡三方平衡關系

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

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

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

(1)

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

1.2 相似性度量指標

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

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

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

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

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

(2)

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

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

2.2 改進的邊值預測方法

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

(3)

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

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

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

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

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

綜上所述，基于CN的改進預測方法為：

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

輸入：srcnode：待測邊的源節(jié)點 dstnode：待測邊的目標節(jié)點 truesign：待測邊的實際符號值

輸出：true/false ：預測真值

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

computeDeg(srcnode) andDeg(dstnode); //計算節(jié)點度數(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é)點度數(shù)的預測

else

do predict onBScore;//基于共同鄰居的預測

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

2.3 預測精度標準

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

(4)

3 實驗測試

3.1 實驗過程

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

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

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

3.2 實驗結果分析

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

表2 RandomGraph(30,700)預測實驗結果

表3 Gama(16，116)預測實驗結果

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

表4 Sam_aff(18，158)預測實驗結果

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

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

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

4 結論

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

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

[10] 張昱,張恩德,李封,等.基于時間信息的社會網(wǎng)絡鏈接預測研究[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)大學數(shù)學與數(shù)量經(jīng)濟學院博士研究生.

國家自然科學基金資助項目(71171035).

2095-3852(2015)05-0602-05

A

TP393

10.3963/j.issn.2095-3852.2015.05.017