符號網(wǎng)絡(luò)的局部標(biāo)注特征與預(yù)測方法

蘇曉萍，宋玉蓉

（1. 南京工業(yè)職業(yè)技術(shù)學(xué)院 計算機與軟件學(xué)院，江蘇 南京 210046; 2. 南京郵電大學(xué) 自動化學(xué)院，江蘇 南京210003）

符號網(wǎng)絡(luò)是指邊具有正或負(fù)符號屬性的網(wǎng)絡(luò)，符號為正表示網(wǎng)絡(luò)中兩節(jié)點間具有相互信任的、積極的朋友關(guān)系，負(fù)邊則表示不信任的、消極的敵對關(guān)系。具有符號屬性的網(wǎng)絡(luò)普遍存在[1]，研究鏈路的符號屬性有利于理解網(wǎng)絡(luò)的基本結(jié)構(gòu)特征，理解信任和不信任的傳播方式。另外，社會符號網(wǎng)絡(luò)的邊符號屬性能夠直接反映節(jié)點間的態(tài)度，因此在推薦系統(tǒng)[2]、輿情分析與觀點形成[3]、網(wǎng)絡(luò)欺凌與社會排斥[4]等問題中均能通過符號分析獲得應(yīng)用。符號網(wǎng)絡(luò)的研究始于Heider[5]基于社會心理學(xué)對人類關(guān)系的研究，而隨著復(fù)雜網(wǎng)絡(luò)研究興起，符號網(wǎng)絡(luò)的結(jié)構(gòu)特征與演化規(guī)律受到更多研究者的關(guān)注[6-7]，如何通過部分觀測到的網(wǎng)絡(luò)符號預(yù)測未知的邊符號成為符號網(wǎng)絡(luò)中非常重要的研究方向。

符號預(yù)測方法大致可以分為兩類：1)考慮網(wǎng)絡(luò)局部特征的方法；2)考慮網(wǎng)絡(luò)全局特征的方法。考慮網(wǎng)絡(luò)局部特征的方法主要利用節(jié)點的鄰域特征，如：節(jié)點出邊、入邊的符號以及相鄰三元組各邊標(biāo)注符號特征進行符號預(yù)測。這類方法主要基于網(wǎng)絡(luò)局部特征以及社會學(xué)相關(guān)理論實現(xiàn)邊符號的預(yù)測，所有基于弱結(jié)構(gòu)平衡[8]和地位理論[9]的預(yù)測方法均要求兩節(jié)點間具有共同鄰居時算法才有效，但統(tǒng)計結(jié)果發(fā)現(xiàn)，現(xiàn)實的符號網(wǎng)絡(luò)中有很大比例的節(jié)點不能構(gòu)成三元組。Guha等[10]最早基于網(wǎng)絡(luò)模型研究符號預(yù)測問題，他們將信任網(wǎng)絡(luò)表示為矩陣并運用不同的矩陣運算代表信任關(guān)系在網(wǎng)絡(luò)上的不同傳播方式，實現(xiàn)了信任關(guān)系的預(yù)測。Leskovec等[11]采用機器學(xué)習(xí)的方法對符號預(yù)測問題進行了研究，他們利用節(jié)點的出度、入度、節(jié)點的嵌入性以及基于地位理論的所有16種待預(yù)測邊所處的三角形的關(guān)系模式作為特征采用邏輯回歸模型訓(xùn)練分類器，得到了較高的預(yù)測精度。文獻[12]則通過網(wǎng)絡(luò)局部特征和地位理論為特征采用SVM算法進行二值分類實現(xiàn)符號預(yù)測。相對于Leskovec考慮長度為3的有序環(huán)構(gòu)建的網(wǎng)絡(luò)特征，Chiang等[13]利用Katz指標(biāo)提出一個不平衡測度指標(biāo)并通過長度為 κ的環(huán)的平衡程度構(gòu)建特征集，然后使用邏輯回歸模型進行符號預(yù)測，當(dāng)環(huán)的長度從3增加到5時，預(yù)測精度有所提高，但是當(dāng) κ ＞5后對預(yù)測精確度的影響不大。文獻[14]指出：能夠反映符號網(wǎng)絡(luò)不平衡程度的測度都可以用于符號預(yù)測。文獻[15]通過分析兩節(jié)點間不同的連接形式，提出符號預(yù)測的方法，使得在沒有共同鄰居的情形下的預(yù)測精度有所提高；符合符號網(wǎng)絡(luò)局部傾向于結(jié)構(gòu)平衡或弱結(jié)構(gòu)平衡的特征反過來會促使符號網(wǎng)絡(luò)的全局特征出現(xiàn)，因此有很多利用網(wǎng)絡(luò)全局結(jié)構(gòu)進行符號預(yù)測的方法。文獻[16]就從譜分析的角度出發(fā)進行符號預(yù)測，并指出許多基于譜分析的方法可以從簡單的二值網(wǎng)絡(luò)擴展到符號網(wǎng)絡(luò)。他們將拉普拉斯矩陣的定義擴充到符號網(wǎng)絡(luò)，通過拉普拉斯矩陣的核函數(shù)進行網(wǎng)絡(luò)符號的預(yù)測。Hsieh[17]等發(fā)現(xiàn)滿足弱結(jié)構(gòu)平衡理論的符號網(wǎng)絡(luò)其鄰接矩陣具有低秩特征，于是將符號預(yù)測問題轉(zhuǎn)化為矩陣填充問題，用低秩填充法有效地進行了符號預(yù)測。他們還將符號預(yù)測近似為低秩矩陣分解問題進行了符號預(yù)測。文獻[18]也研究了矩陣分解在符號預(yù)測中的應(yīng)用并解決了數(shù)據(jù)不平衡對預(yù)測精度的影響。文獻[19]提出了一種區(qū)別于Hsieh以逐點誤差衡量原矩陣與結(jié)果矩陣誤差的方法，他們將成對誤差應(yīng)用到矩陣分解的損失函數(shù)中，給出的算法MF-LiSP取得了較高精確度。通過以上介紹發(fā)現(xiàn)，符號網(wǎng)絡(luò)的局部結(jié)構(gòu)特征與全局特征聯(lián)系緊密，符號預(yù)測方法僅使用局部特征或全局特征都不夠全面，在預(yù)測算法中如何同時利用局部和全局特征是一個值得研究的問題。

受以上研究的啟發(fā)，從真實網(wǎng)絡(luò)數(shù)據(jù)的統(tǒng)計分析出發(fā)，結(jié)合節(jié)點局部標(biāo)注特征和網(wǎng)絡(luò)全局結(jié)構(gòu)特征設(shè)計了一種新的基于低秩矩陣分解的符號預(yù)測模型，解決了符號網(wǎng)由于數(shù)據(jù)稀疏和網(wǎng)絡(luò)局部特征利用不足帶來的預(yù)測精度不高的問題。

1 相關(guān)理論

1.1 基本定義

定 義 符 號 網(wǎng) 絡(luò) G 為 G =(V,E,S)， 其 中V={1,2,3,···,n} 為 節(jié) 點 集 合 ， E ={1,2,3,···,m}為 邊 集 合 ，S={?1,0,1}表 示邊符號， i, j∈ V,e ( i,j)∈ E , s ( i,j)∈ S，設(shè) O 為被觀測到的邊集，則 O ?E 。 符號網(wǎng)絡(luò)G 對應(yīng)鄰接矩陣 A ，其中：

符號網(wǎng)絡(luò)G可能為有向圖也可能為無向圖，當(dāng)G為有向圖時A為非對稱矩陣，若G為無向圖則A為對稱矩陣。

1.2 結(jié)構(gòu)平衡與弱結(jié)構(gòu)平衡理論

結(jié)構(gòu)平衡理論把人與人之間的關(guān)系分為積極和消極兩種，被形式化地描述為符號網(wǎng)絡(luò)，邊的正、負(fù)符號分別表示積極關(guān)系和消極關(guān)系。此時符號網(wǎng)絡(luò)中3個節(jié)點間的關(guān)系共形成4種三角形模體，如圖1所示。從社會心理學(xué)角度看，以下結(jié)論成立：朋友的朋友是朋友；朋友的敵人是敵人。據(jù)此判定圖1(a)、(b)是平衡的，而圖1(c)、(d)是不平衡的。不平衡的結(jié)構(gòu)具有向平衡結(jié)構(gòu)轉(zhuǎn)換的趨勢。在三角形模體中判斷局部平衡性時可以通過三條邊符號之積來實現(xiàn)：三符號積為正則平衡，否則不平衡。Cartwright和Harary[20]將Heider[2]的社會學(xué)結(jié)論形式化地描述為圖結(jié)構(gòu)并證明符號網(wǎng)絡(luò)平衡的充分必要條件是：網(wǎng)絡(luò)中的節(jié)點能夠被劃分為兩個子集，每個子集內(nèi)的所有邊均為正，子集間的邊均為負(fù)。

平衡網(wǎng)絡(luò)的判別條件比較嚴(yán)苛，現(xiàn)實中很難找到平衡網(wǎng)絡(luò)的情形，因此Davis[8]放寬結(jié)構(gòu)平衡的約束提出了弱結(jié)構(gòu)平衡理論，弱結(jié)構(gòu)平衡理論規(guī)定：只要三角形模體中不存在兩正一負(fù)的關(guān)系就構(gòu)成弱平衡，在該條件下，圖1(a)、(b)、(d)代表的情形均可看作平衡的結(jié)構(gòu)。當(dāng)網(wǎng)絡(luò)滿足弱平衡結(jié)構(gòu)時，節(jié)點可以被分成 κ個子集，且子集內(nèi)節(jié)點間的邊全為正，子集間節(jié)點的邊全為負(fù)。這類符號網(wǎng)也被稱為 κ-平衡網(wǎng)。

1.3 矩陣的秩與結(jié)構(gòu)平衡

根據(jù)弱結(jié)構(gòu)平衡的定義，當(dāng)符號網(wǎng)絡(luò)滿足 κ-平衡條件時，網(wǎng)絡(luò)節(jié)點可以被分成 κ個子集，當(dāng)對網(wǎng)絡(luò)節(jié)點按編號排序，鄰接矩陣將是塊對角矩陣。

圖2(a)給出了一個滿足弱平衡網(wǎng)的示例，圖中8個節(jié)點被分成3個子集，圖2(b)為圖2(a)對應(yīng)的鄰接矩陣A，若補齊圖2(a)中缺失的邊，使其成為完全圖，該圖對應(yīng)的鄰接矩陣為塊對角矩陣X，塊內(nèi)很明顯矩陣的秩 R ank(X)=3小于矩陣的行列數(shù)8。根據(jù)以上分析可知符號網(wǎng)絡(luò)添加相應(yīng)具有固定符號的邊將使符號網(wǎng)絡(luò)向完全 κ-平衡網(wǎng)靠近。

因此可以把符號預(yù)測問題看作矩陣填充問題：已知被部分觀測到的矩陣 A ，采用矩陣填充的方法找到矩陣 X 。此時符號預(yù)測問題可被看作優(yōu)化問題：填充矩陣中零值使得目標(biāo)矩陣 X 的秩最小。該問題可形式化描述為

式(1)的目標(biāo)函數(shù)是 X 矩陣的秩，即其奇異值構(gòu)成向量的稀疏性，通常上述優(yōu)化問題是NP難的，而函數(shù) R ank(X)在矩陣譜范數(shù)單位球上的凸包絡(luò)是矩陣的核范數(shù)(即矩陣所有奇異值的和)，因此可以用立時，矩陣X可以以1 ?n?3的概率被恢復(fù)。但是對于符號網(wǎng)絡(luò)來說，均勻抽樣不容易做到，因為通過4.1節(jié)數(shù)據(jù)描述可以看到符號網(wǎng)絡(luò)80%的邊為正，同時矩陣填充的運算速度較慢，因此矩陣填充也經(jīng)常用低秩矩陣分解來近似。

圖2 弱平衡結(jié)構(gòu)與矩陣的低秩特性Fig. 2 Weakly balanced network and low-rank structure

2 符號預(yù)測

當(dāng)符號預(yù)測被近似為低秩矩陣分解問題時，鄰接矩陣 A可被分解為兩個 κ行 n列的矩陣PT和Q，優(yōu)化目標(biāo)是使 PTQ與A之間的誤差最小，原矩陣可以被r?ij=(PTQ)ij值填充， r?ij就是預(yù)測到的用戶i對用戶j的評價。矩陣分解模型可被形式化地描述為

式(2)中l(wèi)為損失函數(shù)用于評價預(yù)測值與原矩陣間的誤差，后兩項為正則化項，用來防止過擬合損失函數(shù)，可根據(jù)具體問題進行選擇。雖然上式是非凸的，但是實踐證明該方法在很多矩陣填充問題中均取得了很好的預(yù)測效果。

基本矩陣分解模型充分利用了鄰接矩陣的全局低秩特性，但是，在被符號網(wǎng)絡(luò)所代表的社會關(guān)系網(wǎng)中，不同節(jié)點的標(biāo)注行為常常具有偏置現(xiàn)象：網(wǎng)絡(luò)“噴子”也被稱為“Troll”的節(jié)點，該類節(jié)點為引起別人的注意會故意攻擊其他人，“Troll”節(jié)點會發(fā)出比其余節(jié)點更多的負(fù)邊；與此相對應(yīng)的，有些節(jié)點會收到低于平均水平的評價，它們可能受到“網(wǎng)絡(luò)欺凌”，這一現(xiàn)象的社會心理學(xué)根源是“認(rèn)知失調(diào)”，人們通常為保持與他人態(tài)度的一致而調(diào)整自己的行為因此而攻擊收到過負(fù)面評價的人。從真實符號網(wǎng)絡(luò)的統(tǒng)計特征發(fā)現(xiàn)，這兩類節(jié)點在符號網(wǎng)中確實存在，雖然數(shù)量不多但其作用巨大。在符號預(yù)測問題中僅考慮平均后的全局特征并不能完全反映網(wǎng)絡(luò)結(jié)構(gòu)特征，節(jié)點的局部標(biāo)注特征需要在預(yù)測模型中得以體現(xiàn)?，F(xiàn)定義待預(yù)測邊的局部標(biāo)注特征為

式中：μ為符號網(wǎng)絡(luò)的平均標(biāo)注傾向，當(dāng) μ為負(fù)時說明網(wǎng)絡(luò)用戶更傾向于給其他用戶以負(fù)面評價；μ為正時，則表示網(wǎng)絡(luò)用戶有給其他鄰居以正面評價的傾向。設(shè)待預(yù)測邊 e( i,j)兩 端的節(jié)點為i和j， U iout表示節(jié)點i發(fā)出的邊符號的均值， U iout的值能夠反映節(jié)點i對相鄰節(jié)點的局部標(biāo)注特征：若節(jié)點發(fā)出的負(fù)邊數(shù)大于正邊數(shù)，表示節(jié)點i給鄰居以負(fù)面評價的可能性大， e (i,j)被預(yù)測為負(fù)的可能性就增加。同理， U jin為 j收 到的邊符號的均值，當(dāng) U jin為負(fù)時表示節(jié)點 j收到了更多的負(fù)面評價，因此 e( i,j)被預(yù)測為負(fù)的可能性就增加。圖3給出了符號網(wǎng)絡(luò)標(biāo)注的局部偏置示例，設(shè) μ =0.2，即符號網(wǎng)絡(luò)全局有正面評價的傾向，經(jīng)計算可得：U iout=[(?1)+(?1)+1]/4= ?1/4，U jin=?1/4 ， 于是 bij=?3/10 ， 此時邊 e( i,j)的符號預(yù)測結(jié)果將向負(fù)偏斜。

圖3 標(biāo)注行為的偏置現(xiàn)象Fig. 3 Bias behavior of signed edges

bij的值能夠很好地反映待預(yù)測邊兩端節(jié)點的局部標(biāo)注行為和行為偏好，將標(biāo)注偏好反映在預(yù)測的目標(biāo)函數(shù)，得到較基本模型更為精細的預(yù)測模型：

根據(jù)式(4)可知：節(jié)點i對節(jié)點j的符號可被預(yù)測為 r?ij=bij+(PTQ)ij，而式(2)表示的基本矩陣分解模型得到的符號預(yù)測結(jié)果為 r?ij=(PTQ)ij。因此，以式(4)為目標(biāo)函數(shù)的優(yōu)化方法，不但考慮了符號網(wǎng)的全局低秩特性還考慮了待預(yù)測邊兩端節(jié)點的局部標(biāo)注特征，與基本模型相似，添加了關(guān)于局部特征項的正則化項防止過擬合。

損失函數(shù)l可以有多種選擇，本文選擇Square_loss為損失函數(shù)，于是優(yōu)化目標(biāo)函數(shù)可寫成：

對式(5)給出的優(yōu)化問題可以采用隨機梯度下降法進行求解，通過求梯度以確定優(yōu)化函數(shù)下降方向：同理也可求得目標(biāo)函數(shù)對Uiout、 U jin的偏導(dǎo)數(shù)，由于沿梯度方向相反的方向下降最快，于是得到如下迭代公式：

通過反復(fù)迭代并不斷優(yōu)化參數(shù)，使觀測矩陣A與分解后矩陣 B +PTQ間的誤差小于設(shè)定的誤差值即最終收斂。其中 α為學(xué)習(xí)速度，α越大下降就越快。隨機梯度下降的時間復(fù)雜度為 O (tmκ)，t為迭代并收斂次數(shù)，m為節(jié)點個數(shù)，κ為秩數(shù)。由于符號網(wǎng)絡(luò)滿足低秩特性，通常 κ值很小，且收斂較快，因此采用隨機梯度下降法求解最小化問題速度較快。

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集描述

實驗中的3個真實大型社會網(wǎng)絡(luò)數(shù)據(jù)來自于斯坦福大學(xué)的SNAP2項目，Epinions給出了用戶間“who-trust-whom”的關(guān)系，Slashdot是一個技術(shù)相關(guān)的新聞網(wǎng)站，允許用戶根據(jù)自身觀點標(biāo)記其他用戶為friend/foe，Wikipedia是維基百科申請管理員身份的投票關(guān)系網(wǎng)，若一個用戶被大多數(shù)其他用戶同意則當(dāng)選為某一學(xué)科的管理員負(fù)責(zé)百科詞條的維護，若該用戶未受到大多數(shù)其他用戶的贊成票則選舉失敗。表1給出了3個網(wǎng)絡(luò)的統(tǒng)計特征。

表1的統(tǒng)計結(jié)果顯示：3個符號網(wǎng)絡(luò)中正邊占比均在75%以上，而負(fù)邊占比較少，互惠邊(reciprocal edges)是指兩用戶間持有相同態(tài)度，這樣的互惠邊在網(wǎng)絡(luò)中占有一定比例，且互惠邊中正邊居多，這與人們社會心理有關(guān)，當(dāng)一個人討厭另一個人反應(yīng)的是不予理睬，“愛的反義詞不是恨而是冷漠”。而一個人對另一個人的示好通常顯示出“鏡子效應(yīng)”。統(tǒng)計結(jié)果還發(fā)現(xiàn)：發(fā)出50%以上負(fù)邊的節(jié)點只占網(wǎng)絡(luò)節(jié)點極少部分，且大部分的負(fù)邊都是由一些特定節(jié)點發(fā)出的，這些節(jié)點充滿反社會特征，并通過攻擊別人博取別人的關(guān)注，這些節(jié)點發(fā)出的新邊為負(fù)的可能性極大，而收到50%以上負(fù)邊的節(jié)點也的確存在，即“網(wǎng)絡(luò)欺凌”是事實，存在“人云亦云”的現(xiàn)象。統(tǒng)計結(jié)果還顯示，符號網(wǎng)絡(luò)中有一定比例的節(jié)點無法構(gòu)成三元組，此時基于結(jié)構(gòu)平衡理論的預(yù)測算法將失效。

表1 數(shù)據(jù)集統(tǒng)計特征Table 1 Statistics of datasets

3.2 預(yù)測效果與分析

為證明所提帶有偏置的矩陣分解模型MF-Bias(matrix factorization with bias)對符號預(yù)測問題的有效性，將它與以下基準(zhǔn)預(yù)測算法進行比較。

3) LR (logistic regression)[11]：將符號預(yù)測問題看作二值分類問題，采用邏輯回歸模型訓(xùn)練分類器，得到了較高的預(yù)測精度。

4) MF(matrix factorization)[17]：由 Hsieh 等提出的基本矩陣分解模型。

3.2.1 評價指標(biāo)

1)均方根誤差(RMSE)

它是衡量模型誤差率的常用方法，反映了觀測值與真值偏差的平方和觀測次數(shù)n比值的平方根，計算公式為

式中： pi為 第i個 觀測值，ai為 第i個真實值，RMSE值越小預(yù)測誤差越小。圖4(a)、(b)、(c)給出了3個符號網(wǎng)絡(luò)在不同抽樣比率下的RMSE值。

圖4 3個符號網(wǎng)絡(luò)的預(yù)測結(jié)果Fig. 4 Three signed networks predicted results

2)精確性(Accuracy)

用于評價預(yù)測算法對符號預(yù)測的準(zhǔn)確程度，精確性計算公式為

式中： T P表示對符號為正的邊的預(yù)測正確的數(shù)目，TN 表 示符號為負(fù)的預(yù)測正確的數(shù)目， P +N則是需要預(yù)測的邊的總數(shù)。Accuracy的值越大表示預(yù)測成功的概率越高。圖4(d)、(e)、(f)給出了3個符號網(wǎng)絡(luò)在不同抽樣比率下的精確性實驗結(jié)果。

3.2.2 實驗參數(shù)設(shè)置

給定部分觀察的符號網(wǎng)絡(luò)，符號推斷的目標(biāo)就是通過符號網(wǎng)中已知邊符號推斷出未知邊的符號。本文構(gòu)建的符號網(wǎng)絡(luò)模型為有向網(wǎng)絡(luò)，需要說明的是，所提算法也適用于無向符號網(wǎng)絡(luò)。實驗采用隨機抽樣的方法將數(shù)據(jù)集分為訓(xùn)練集(training data set)和測試集(testing data set)。訓(xùn)練集被看作部分觀測的符號網(wǎng)絡(luò)，利用測試集訓(xùn)練模型，然后對測試集中邊符號進行預(yù)測；測試集分別為整個符號網(wǎng)絡(luò)的15%，30%， · ··，90%。對于MF和MF-Bias算法，首先需要對矩陣 P、 Q進行初始化，這里我們令其為全1矩陣，有時也將 P 、 Q 的初始值設(shè)為隨機矩陣。另外，模型還需要確定3個參數(shù)，即 κ、 α 和 λ，其中 κ 為符號網(wǎng)絡(luò)的秩，取 κ= 5 ；λ為懲罰因子，取λ = 0.12；α 是 學(xué)習(xí)速度，初始值取 α=0.2，且每次迭代后使 α 值 衰減(α*=0.9)，目的是使算法盡快收斂，最大迭代次數(shù)為30次。得到的預(yù)測結(jié)果是符號網(wǎng)上兩節(jié)點間以正或負(fù)的符號相連的傾向，這一預(yù)測值并不是離散的±1而是連續(xù)的值，因此得到預(yù)測結(jié)果后需要對預(yù)測結(jié)果進行劃分，劃分方法有直接劃分、全局劃分、局部劃分、從眾劃分[14]，本文采用直接劃分，即預(yù)測結(jié)果≥0則預(yù)測符號為正，否則為負(fù)。以下通過均方根誤差(RMSE)和預(yù)測精確性(Accuracy)評價各算法的預(yù)測效果。

3.2.3 實驗結(jié)果及討論

圖4的實驗結(jié)果顯示：隨著抽樣數(shù)據(jù)的增加，預(yù)測誤差(RMSE)減小，預(yù)測精確度增加。基于低秩矩陣分解的方法(包括MF、MF-Bias)獲得了比其他算法更好的預(yù)測效果，這說明在符號網(wǎng)絡(luò)中節(jié)點標(biāo)注的偏置現(xiàn)象確實存在，同時，由于MF-Bias充分考慮了節(jié)點的局部偏置特性，得到了相較于基本矩陣分解算法好的預(yù)測精度，例如：在數(shù)據(jù)集Epinions上當(dāng)訓(xùn)練集為90%時，預(yù)測精確度為95.04%，相較于基本矩陣分解方法提高了0.6%，LR方法提高了2.3%，在其他兩個數(shù)據(jù)集上也得到了與圖4(a)相似的結(jié)果(見圖4(b)～(c))，RMSE誤差分析結(jié)果(見圖4(d)～(f))與預(yù)測精確度得到相似的結(jié)論：本文所提MF-Bias模型獲得了最小預(yù)測誤差。實驗表明：帶有偏置的矩陣分解方法能夠很好地對抗數(shù)據(jù)稀疏帶來的問題并提高預(yù)測效果。盡管兩種啟發(fā)式算法(ID和OD)的預(yù)測精度都低于矩陣分解模型和邏輯回歸模型，但是它們的特點是計算復(fù)雜度低，因為它們僅僅使用待預(yù)測邊兩端節(jié)點的局部信息且能在一定程度上反映數(shù)據(jù)的結(jié)構(gòu)特性。不同數(shù)據(jù)集ID和OD的效果截然不同，在Slashdot上OD好于ID，在Wiki上ID好于OD，可見僅考慮出度或入度作為預(yù)測依據(jù)不夠合理，用戶在不同數(shù)據(jù)集上的行為特征值得進一步思考。

3.3 秩與預(yù)測精度

根據(jù)1.3節(jié)可知，符號網(wǎng)絡(luò)鄰接矩陣的秩與弱平衡結(jié)構(gòu)間存在必然聯(lián)系：當(dāng)符號網(wǎng)絡(luò)滿足 κ-平衡條件時，網(wǎng)絡(luò)節(jié)點可以被分成 κ 個 子集，鄰接矩陣具有低秩性且矩陣的秩恰好等于 κ，而矩陣分解的本質(zhì)是做降維操作，將會把鄰接矩陣分解為2個 κ行 n列的矩陣，那么到底將鄰接矩陣分解為多少行合適呢？本文分別令 κ=1、2、4、5、6、7、8、16、32，對兩種矩陣分解算法在3個數(shù)據(jù)集進行精確度測試，所有實驗均取測試集為90%，其余各參數(shù)與3.2節(jié)相同。實驗結(jié)果如圖5所示，實驗結(jié)果顯示：相較于κ= 1 ，κ=2時預(yù)測精度有大幅提高，這支持了1.4節(jié)所述結(jié)構(gòu)平衡理論的正確性，κ值從2～5預(yù)測精度有較大幅度提高，大部分?jǐn)?shù)據(jù)集在 κ=7時預(yù)測精度達到最優(yōu)(Slashdot數(shù)據(jù)集在 κ=5時精確度最優(yōu))，κ≥7后預(yù)測精度變化不大。實驗結(jié)果與Chiang等在文獻[13]中得到的結(jié)論一致，也證明符號網(wǎng)絡(luò)鄰接矩陣的低秩特性明顯。實驗還發(fā)現(xiàn)：比起基本矩陣分解算法，帶偏置的矩陣分解算法對 κ值更加魯棒，即隨著 κ的變化符號預(yù)測的精確度變化不大，這是因為在帶偏置的矩陣分解模型中節(jié)點及其鄰居的特征與低秩特性共同決定模型的精確度，因此獲得了較高的精確度，這也證明節(jié)點的局部特性對預(yù)測效果有影響。

4 結(jié)束語

真實的復(fù)雜系統(tǒng)中對立關(guān)系普遍存在，利用符號網(wǎng)絡(luò)對這些復(fù)雜系統(tǒng)建模能夠很好地表達節(jié)點間的對立關(guān)系，符號屬性對分析、理解復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、功能、動力學(xué)行為具有十分重要的理論意義。要利用符號屬性，首要的問題就是對未知邊符號的正確預(yù)測。本文對已有的符號網(wǎng)絡(luò)預(yù)測方法進行了分類和總結(jié)。為了同時利用節(jié)點的局部特征和全局特征進行符號預(yù)測，在基于利用網(wǎng)絡(luò)全局特征的低秩矩陣分解方法的基礎(chǔ)上改寫優(yōu)化目標(biāo)函數(shù)使之能夠描述待預(yù)測邊兩端節(jié)點的出度和入度局部特征，給出了帶有偏置的低秩矩陣分解方法。實驗結(jié)果證實：添加節(jié)點局部特征后的低秩矩陣分解方法能夠得到較其他基準(zhǔn)算法好的預(yù)測效果，且互惠信息能夠進一步提高預(yù)測精度。

未來符號預(yù)測的研究方向會向兩個不同方向發(fā)展：1)進一步利用豐富的元數(shù)據(jù)信息，因為元數(shù)據(jù)蘊含了用戶間的熟識度、聲譽、語義與態(tài)度等重要信息，元數(shù)據(jù)可以在缺少結(jié)構(gòu)信息時保證預(yù)測精度，當(dāng)然付出的代價是模型復(fù)雜度升高，運算速度降低；2)降低模型復(fù)雜度以適應(yīng)于數(shù)量巨大的在線符號網(wǎng)絡(luò)挖掘，此時基于網(wǎng)絡(luò)局部信息的符號預(yù)測方法具有優(yōu)勢，因為這類算法易于被并行化，從而提高運算速度，當(dāng)然負(fù)面影響會帶來一定預(yù)測效果的下降。如何充分利用局部信息的研究還顯得不足，如節(jié)點間除了出度和入度還有哪些連接特點能用結(jié)構(gòu)平衡理論或地位理論來解釋。當(dāng)節(jié)點間的嵌入性很低時結(jié)構(gòu)平衡等社會學(xué)理論將失效，怎樣保證預(yù)測的精確度？

另外，還需進一步豐富符號網(wǎng)絡(luò)結(jié)構(gòu)的理論研究，目前用于符號預(yù)測的理論只有結(jié)構(gòu)平衡理論和地位理論，近年并未有較大突破。也就是說，對符號網(wǎng)絡(luò)結(jié)構(gòu)演化、動力學(xué)行為的分析仍然不能解釋符號網(wǎng)絡(luò)結(jié)構(gòu)的形成，從而制約了符號預(yù)測方法的進一步發(fā)展，根據(jù)3.3節(jié)的研究發(fā)現(xiàn)本文所提算法對矩陣的秩魯棒，及在秩取5和7時預(yù)測效果最好，這一結(jié)果的深層社會學(xué)理論含義及其與符號網(wǎng)絡(luò)形成機制間的聯(lián)系將另文討論。這也是下一步將要研究的內(nèi)容。

符號網(wǎng)絡(luò)作為近年來從基本復(fù)雜網(wǎng)絡(luò)衍生出的新網(wǎng)絡(luò)模型和符號預(yù)測問題作為新模型上的新問題，人們對它們的理解還遠遠不夠，符號網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、動力學(xué)行為以及在個性化推薦、態(tài)度預(yù)測、用戶特征分析與聚類等方面的應(yīng)用將會受到更多的研究和關(guān)注。