基于交互意見和地位理論的符號網(wǎng)絡(luò)鏈接預(yù)測模型

王　鑫　王　英 　左萬利

1(長春工程學(xué)院計(jì)算機(jī)技術(shù)與工程學(xué)院　長春　130012)2(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　長春　130012)3(符號計(jì)算與知識工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué))　長春　130012)4(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))　廣西桂林　541004)(xinwangjlu@gmail.com)

基于交互意見和地位理論的符號網(wǎng)絡(luò)鏈接預(yù)測模型

王鑫1,3,4王英2,3左萬利2,3

1(長春工程學(xué)院計(jì)算機(jī)技術(shù)與工程學(xué)院長春130012)2(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院長春130012)3(符號計(jì)算與知識工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué))長春130012)4(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))廣西桂林541004)(xinwangjlu@gmail.com)

摘要隨著社會網(wǎng)絡(luò)的普遍和流行，社會網(wǎng)絡(luò)為符號網(wǎng)絡(luò)(signed network)的深入研究提出了更多的全新問題，其中鏈接預(yù)測是符號網(wǎng)絡(luò)研究的核心問題之一.交互意見和地位理論能夠較好地解釋符號網(wǎng)絡(luò)中鏈接關(guān)系的構(gòu)建和鏈接的符號屬性，二者作為鏈接構(gòu)建的誘因?yàn)樘岣哝溄宇A(yù)測的質(zhì)量提供了理論基礎(chǔ).因此，通過研究交互意見和地位理論與鏈接關(guān)系的強(qiáng)相關(guān)性，構(gòu)建符號網(wǎng)絡(luò)鏈接預(yù)測模型.首先，利用交互意見增強(qiáng)待分解矩陣的可靠度，彌補(bǔ)由地位理論的對稱性所帶來的局限性；然后，在稀疏學(xué)習(xí)矩陣分解模型基礎(chǔ)上，將交互意見建模為增強(qiáng)可靠度因子，同時將地位理論建模為稀疏學(xué)習(xí)模型的正則化項(xiàng)；最后，構(gòu)建基于交互意見和地位理論的符號網(wǎng)絡(luò)鏈接預(yù)測模型MF-SI.實(shí)驗(yàn)結(jié)果表明相比于其他基本方法，MF-SI模型獲得了較好的預(yù)測質(zhì)量，說明集成交互意見和地位理論能夠較好地實(shí)現(xiàn)符號網(wǎng)絡(luò)鏈接預(yù)測問題.

關(guān)鍵詞符號網(wǎng)絡(luò)；鏈接預(yù)測；稀疏學(xué)習(xí)；交互意見；地位理論

符號網(wǎng)絡(luò)(signed network)是具有正或負(fù)符號屬性標(biāo)記的有向網(wǎng)絡(luò)，其中正向鏈接(positive link)表示積極關(guān)系，負(fù)向鏈接(negative link)表示消極關(guān)系[1].具體而言，符號網(wǎng)絡(luò)中的正向鏈接使用“+”表示，表達(dá)了2個節(jié)點(diǎn)之間具有信任、朋友、支持和喜歡等積極關(guān)系；而負(fù)向鏈接使用“-”表示，表達(dá)了2個節(jié)點(diǎn)之間具有敵對、不信任、討厭和反對等消極關(guān)系.特別是在社交媒體領(lǐng)域，用戶之間借助社交網(wǎng)絡(luò)平臺表達(dá)信任與不信任關(guān)系、構(gòu)建朋友與敵對關(guān)系、對論壇內(nèi)容發(fā)表支持與反對觀點(diǎn)等.符號網(wǎng)絡(luò)中鏈接預(yù)測問題是利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)和用戶行為數(shù)據(jù)預(yù)測尚未建立鏈接的2個節(jié)點(diǎn)之間是否可能建立鏈接關(guān)系以及標(biāo)記鏈接關(guān)系的符號屬性.

符號網(wǎng)絡(luò)在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域研究中具有重要的研究意義和應(yīng)用價值，并引起越來越多研究人員的關(guān)注.因此，提出了高效的鏈接預(yù)測模型用于實(shí)現(xiàn)正向鏈接和負(fù)向鏈接的預(yù)測，并在Epinions數(shù)據(jù)集上構(gòu)建多組實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明所提出的模型能夠準(zhǔn)確地預(yù)測符號網(wǎng)絡(luò)中的鏈接關(guān)系.主要貢獻(xiàn)如下：

1) 提出有效的量化策略分別量化交互意見和地位理論；

2) 將交互意見模擬為增強(qiáng)可靠度因子，模擬地位理論為稀疏學(xué)習(xí)模型的正則化項(xiàng)，利用矩陣分解學(xué)習(xí)模型融合交互意見和地位理論構(gòu)建鏈接預(yù)測模型MF-SI預(yù)測鏈接關(guān)系，進(jìn)而構(gòu)建符號網(wǎng)絡(luò)；

3) 在Epinions數(shù)據(jù)集上評估所提出的模型MF-SI，構(gòu)建多組實(shí)驗(yàn)驗(yàn)證模型的有效性，并詳細(xì)地闡述不同鏈接構(gòu)建誘因以及不同量化策略對鏈接正負(fù)預(yù)測質(zhì)量的影響.

1相關(guān)性研究

最早的符號網(wǎng)絡(luò)研究起源于20世紀(jì)40年代的社會心理學(xué)領(lǐng)域，Heider[2]提出不同類型的社會關(guān)系對個體心理平衡產(chǎn)生不同影響，從心理學(xué)角度研究人在認(rèn)知過程中所產(chǎn)生的正向關(guān)系和負(fù)向關(guān)系之間的相互作用.Cartwright 和Harary[3]在Heider的基礎(chǔ)上系統(tǒng)地將線性的數(shù)學(xué)理論應(yīng)用于Heider平衡理論中，對其形式化描述為正、負(fù)屬性的符號網(wǎng)絡(luò).現(xiàn)有符號網(wǎng)絡(luò)的鏈接預(yù)測問題采用的方法包含2個方面：監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)方法.監(jiān)督學(xué)習(xí)將鏈接預(yù)測問題視為在已知鏈接標(biāo)識的基礎(chǔ)上利用監(jiān)督學(xué)習(xí)算法，如決策樹[4]、遷移學(xué)習(xí)[5]、組合分類器[6]等實(shí)現(xiàn)分類問題；非監(jiān)督學(xué)習(xí)利用網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)鋵傩院徒换バ袨檫M(jìn)行分析預(yù)測，比如節(jié)點(diǎn)相似性[7-8]、鏈接存在的最大似然[9]和矩陣處理[10-11]等.

監(jiān)督學(xué)習(xí)方法首先收集帶有符號屬性的鏈接標(biāo)記數(shù)據(jù)，然后為用戶對構(gòu)建各種類型的特征.針對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征而言，正負(fù)鏈接中節(jié)點(diǎn)的出入度特征[12]和基于平衡理論的三角形特征[13]較為常見.Leskovec等人[12]重點(diǎn)考慮節(jié)點(diǎn)出入度等局部測度特征和待預(yù)測邊所處的結(jié)構(gòu)平衡理論三角形關(guān)系模式特征，并利用邏輯回歸(logistic regression)方法訓(xùn)練模型對邊進(jìn)行分類并獲得了較高預(yù)測準(zhǔn)確度.實(shí)驗(yàn)證明符合結(jié)構(gòu)平衡理論和地位理論的三元組對于待預(yù)測邊的符號屬性預(yù)測起到了重要作用.Chiang等人[14]認(rèn)為平衡理論三角形關(guān)系特征并不具備魯棒性，因?yàn)橛械姆柹鐣W(wǎng)絡(luò)較為稀疏并且大多數(shù)用戶并沒有基于平衡理論三角形關(guān)系特征，進(jìn)而提出引入長度為k的環(huán)特征量化不平衡指標(biāo)，再利用分類算法預(yù)測邊的符號屬性.該方法從全局的角度出發(fā)利用網(wǎng)絡(luò)的不平衡程度進(jìn)行預(yù)測，從而實(shí)現(xiàn)對Leskovec等人局部度量方法的擴(kuò)展.除了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)之外，用戶的屬性信息[15]和情境信息[6]也可作為參考特征，比如興趣、職業(yè)、性別、家鄉(xiāng)等.Patidar等人[15]首先通過訓(xùn)練基于用戶屬性信息的分類器預(yù)測未知鏈接，然后根據(jù)平衡理論判斷是否保持或擴(kuò)大平衡指數(shù)來預(yù)測未知鏈接.Zolfaghar等人[6]利用符號網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和情境信息構(gòu)建熟識度、聲譽(yù)度、相似度和個性化4個因素的特征集合，然后利用組合分類器算法預(yù)測網(wǎng)絡(luò)中鏈接的符號屬性.

非監(jiān)督學(xué)習(xí)方法通常是根據(jù)符號網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)以實(shí)現(xiàn)鏈接關(guān)系的預(yù)測.一般來說，非監(jiān)督學(xué)習(xí)方法依據(jù)不同策略可將鏈接預(yù)測分成2個方面：1)基于相似度的方法.首先定義相似度量化策略用于衡量節(jié)點(diǎn)的相似度，然后根據(jù)相似度推斷鏈接的符號屬性.2)基于矩陣處理的方法.該方法主要包括傳播模型、矩陣分解[16]或矩陣填充方法預(yù)測鏈接的符號屬性.在基于相似度的方法中，Javari等人[7]提出一種基于聚類和協(xié)同過濾的方法用于預(yù)測符號網(wǎng)絡(luò)中正向和負(fù)向鏈接，首先在符號網(wǎng)絡(luò)中引入簇之間的條件相似度概念，并將網(wǎng)絡(luò)聚類成一定數(shù)量的簇，使其每個簇都滿足平衡性，然后應(yīng)用基于用戶的協(xié)同過濾算法實(shí)現(xiàn)鏈接的預(yù)測，有效地解決了符號網(wǎng)絡(luò)的稀疏性問題.Symeonidis等人[8]提出一種基于朋友推薦的算法，首先實(shí)現(xiàn)拉普拉斯矩陣譜聚類算法，然后定義同一簇的節(jié)點(diǎn)相似度和不同簇的節(jié)點(diǎn)相似度的計(jì)算方法，最后借助朋友推薦算法實(shí)現(xiàn)符號網(wǎng)絡(luò)中的鏈接預(yù)測.在矩陣處理方法中，最早的信任傳播模型研究是由Ramanthan等人[17]將負(fù)關(guān)系融入信任傳播模型，利用4種基本的信任傳播模式，實(shí)現(xiàn)在擁有較少的信任或不信任關(guān)系基礎(chǔ)上以較高的準(zhǔn)確度預(yù)測網(wǎng)絡(luò)中2個用戶之間的信任或不信任關(guān)系.矩陣分解是將矩陣分解成多個矩陣的乘積，利用低秩矩陣不斷地逼近原矩陣進(jìn)而補(bǔ)齊原矩陣中的缺失值，達(dá)到預(yù)測符號網(wǎng)絡(luò)鏈接正負(fù)屬性目的.基于矩陣分解或矩陣填充方法，Hsieh等人[10]驗(yàn)證在符號網(wǎng)絡(luò)中弱結(jié)構(gòu)平衡往往會產(chǎn)生全局的低秩模型，然后將鏈接預(yù)測問題轉(zhuǎn)化為低秩矩陣填充問題.

綜上所述，雖然對符號網(wǎng)絡(luò)鏈接預(yù)測模型的研究已有很多，大部分工作都是在2個節(jié)點(diǎn)之間已經(jīng)存在鏈接關(guān)系的假設(shè)前提下預(yù)測鏈接的符號屬性[18].但是，同時完成符號網(wǎng)絡(luò)中任意2個節(jié)點(diǎn)是否建立鏈接關(guān)系以及預(yù)測鏈接關(guān)系的符號屬性，在預(yù)測難度和準(zhǔn)確率方面遇到了極大困難和挑戰(zhàn)，這正是本文的工作重點(diǎn)和貢獻(xiàn).社會學(xué)理論有助于解釋社會現(xiàn)象，從而獲得對社會現(xiàn)象發(fā)生、發(fā)展的規(guī)律性認(rèn)識，而帶有符號屬性的社會網(wǎng)絡(luò)是由多個節(jié)點(diǎn)構(gòu)成的一種社會結(jié)構(gòu)，能夠反映現(xiàn)實(shí)世界中用戶之間的聯(lián)系.因此，將社會學(xué)理論引入符號網(wǎng)絡(luò)鏈接預(yù)測的研究，將會在很大程度上提高鏈接預(yù)測的質(zhì)量[19-20].

2問題形式化描述

用D=[Z,E,R,G]表示Epinions數(shù)據(jù)集中所有數(shù)據(jù)的集合.其中，Z={u1,u2,…,un}表示用戶集合，n為用戶數(shù)量；E∈n×m表示用戶-評論關(guān)聯(lián)矩陣，m為評論數(shù)量，Ei j=1表示用戶ui發(fā)表評論rj，否則Ei j=0；R∈n×m表示用戶對評論的幫助評級矩陣，如果用戶ui評級了評論rj的幫助程度，那么用Ri j表示幫助評級的分值；G∈n×n表示用戶之間符號網(wǎng)絡(luò)矩陣，如果Gi j=1表示用戶ui與用戶uj之間存在正向鏈接關(guān)系，用矩陣P∈n×n表示，而Gi j=-1表示用戶ui與用戶uj之間存在負(fù)向鏈接關(guān)系，用矩陣N∈n×n表示.

針對以上描述，符號網(wǎng)絡(luò)鏈接預(yù)測問題轉(zhuǎn)變?yōu)樵O(shè)計(jì)預(yù)測框架f，利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)和用戶的評級行為數(shù)據(jù)預(yù)測未知的正向和負(fù)向鏈接關(guān)系，即給定已有的符號網(wǎng)絡(luò)關(guān)系矩陣G、用戶-評論矩陣E、用戶對評論的幫助評級矩陣R，目的是學(xué)習(xí)預(yù)測框架f預(yù)測未知的正負(fù)向鏈接關(guān)系矩陣P′和N′，即：

(1)

3數(shù)據(jù)分析以及鏈接構(gòu)建誘因量化

3.1數(shù)據(jù)分析

Epinions.com是著名的商品評價的社交網(wǎng)站，是提供消費(fèi)者對所購買的商品進(jìn)行評論的平臺，公正的評論值得用戶信任，幫助用戶確定購買決策.Epinions數(shù)據(jù)集*http://www.trustlet.org/wiki/Downloaded_Epinions_dataset的處理過程如下：1)獲取由用戶創(chuàng)建的信任和不信任鏈接關(guān)系，以及由用戶行為數(shù)據(jù)構(gòu)成的用戶評價信息.對于鏈接關(guān)系，主要包括施信者(trustor)與受信者(trustee)之間建立的正向鏈接和負(fù)向鏈接，以及鏈接關(guān)系構(gòu)建時間；對于用戶行為數(shù)據(jù)，主要包括用戶對商品的評論以及用戶對評論的幫助評級.2)將用戶的所有評級按照時間偏序排列，過濾掉構(gòu)建鏈接關(guān)系時間之后的所有評級信息.3)由于不活躍或不重要的用戶在一定程度上會影響評估結(jié)果，將少于2個施信者、2個評論及2個評級信息的用戶過濾掉.表1為處理后的Epinions數(shù)據(jù)集統(tǒng)計(jì)結(jié)果.

Table 1　Statistics of Epinions Dataset

3.2鏈接構(gòu)建誘因量化

3.2.1交互意見量化

(2)

(3)

相反，負(fù)向意見傾向ET-(ui,uj)的量化公式如下：

(4)

3.2.2地位理論量化

在Epinions中，由于缺乏權(quán)威的第三方認(rèn)定機(jī)構(gòu)對用戶社會地位的評估，只能借助網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)量化策略衡量用戶在社會網(wǎng)絡(luò)中的地位.在符號網(wǎng)絡(luò)中，正向鏈接入度有助于提升節(jié)點(diǎn)的地位，而負(fù)向鏈接入度降低節(jié)點(diǎn)的地位.由于經(jīng)典PageRank算法未考慮入度鏈接的符號屬性對節(jié)點(diǎn)地位的影響，因此提出引入正負(fù)向鏈接的地位理論的量化策略，用于計(jì)算用戶的社會地位，即PolarityRank和PolarityIndegree.

1)PolarityRank.借鑒PageRank算法的思想，從全局角度衡量節(jié)點(diǎn)在符號網(wǎng)絡(luò)中的重要地位.PolarityRank被定義為

(5)

其中，PR+(ui)和PR-(ui)分別表示正向鏈接和負(fù)向鏈接對用戶ui社會地位變化的貢獻(xiàn)度，其公式為

(6)

其中，參數(shù)α表示阻尼系數(shù)，通常將其設(shè)置為0.85；Out(ui)表示節(jié)點(diǎn)ui的出度數(shù)；In+(ui)和In-(ui)分別表示節(jié)點(diǎn)ui正向入度數(shù)和負(fù)向入度數(shù).

2)PolarityIndegree.借鑒投票機(jī)制，利用正、負(fù)向的入度鏈接數(shù)量，從局部角度衡量節(jié)點(diǎn)在符號網(wǎng)絡(luò)中的重要地位.PolarityIndegree被定義如下：

(7)

其中，PI+(ui)和PI-(ui)分別采用sigmoid函數(shù)形式衡量正、負(fù)向鏈接入度的貢獻(xiàn)程度，定義如下：

(8)

其中，參數(shù)α表示控制入度鏈接的權(quán)重系數(shù).

4鏈接構(gòu)建誘因的動機(jī)觀察

利用Epinions數(shù)據(jù)集，以交互意見和地位理論為理論依據(jù)分析用戶之間建立鏈接的誘因.由于很難準(zhǔn)確識別出建立誘因，僅僅通過最簡單和直接的方式，即觀測社會網(wǎng)絡(luò)中真實(shí)的數(shù)據(jù)，針對不同誘因，利用網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)和用戶行為數(shù)據(jù)展開深入分析，進(jìn)而產(chǎn)生設(shè)計(jì)符號網(wǎng)絡(luò)鏈接預(yù)測框架的動機(jī).

4.1交互意見

為了驗(yàn)證交互意見與關(guān)系符號屬性之間的關(guān)聯(lián)關(guān)系，利用正向和負(fù)向交互意見量化策略嘗試回答2個問題：

1) 施信者的正向意見傾向大于負(fù)向意見傾向是否更可能與受信者建立正向鏈接關(guān)系?

2) 施信者的負(fù)向意見傾向大于正向意見傾向是否更可能與受信者建立負(fù)向鏈接關(guān)系?

為了回答以上2個問題，首先針對每對用戶關(guān)系量化施信者對受信者的正向意見傾向ET+與負(fù)向意見傾向ET-的差值；然后統(tǒng)計(jì)正向關(guān)系和負(fù)向關(guān)系情感差異的密度分布.從圖1可以發(fā)現(xiàn)，大多數(shù)信任關(guān)系(幾乎達(dá)到92%)分布在意見差異值[0, 1]的區(qū)間內(nèi)；相反，不信任關(guān)系的分布情況稍微復(fù)雜，不信任關(guān)系分布最多的2個位置分別在-1和+1，但是，仍然可從分布的結(jié)果中發(fā)現(xiàn)將近69%的不信任關(guān)系分布在意見差異值的[-1, 0]區(qū)間內(nèi).不信任關(guān)系分布復(fù)雜的原因是：在Epinions中，用戶的評級數(shù)據(jù)較為傾斜(skewed)，即大多數(shù)評級都分布在分值4～5之間.這說明絕大部分用戶更加愿意對評論做出較為積極正向的評級，即使建立的關(guān)系是不信任關(guān)系.

Fig. 1　Density distribution of opinion differences.圖1　意見差異密度分布情況

另外，為了進(jìn)一步驗(yàn)證交互意見的數(shù)量與建立鏈接關(guān)系的正負(fù)屬性之間存在的關(guān)聯(lián)關(guān)系，嘗試回答2個問題：

1) 2個用戶之間正向交互意見傾向數(shù)量越多，這2個用戶之間更可能構(gòu)建正向鏈接?

2) 2個用戶之間負(fù)向交互意見傾向數(shù)量越多，這2個用戶之間更可能構(gòu)建負(fù)向鏈接?

為了回答第1個問題，首先形式化定義一些符號，如PIi j表示用戶ui與用戶uj的正向交互數(shù)量；Uk表示用戶ui與用戶uj正向交互數(shù)量不小于K的用戶對〈ui,uj〉集合，Uk={〈ui,uj〉|PIi j≥K}，其中K表示正向交互數(shù)量；PRk表示在Uk中正向關(guān)系對的集合，PRk={〈ui,uj〉|(PIi j≥K)∧Ti j=1}.然后，計(jì)算正向鏈接關(guān)系數(shù)量同正向交互數(shù)量比率PK：

(9)

正向鏈接關(guān)系數(shù)量同正向交互數(shù)量比率PK隨著K變化的比率分布如圖2(a)所示.隨著正向交互數(shù)量K的增加，比率PK往往也隨著增加，表明正向交互數(shù)量與正向鏈接關(guān)系存在較大的相關(guān)性，大部分正向鏈接關(guān)系是基于交互行為的意見傾向而構(gòu)建，正向交互越多的用戶之間更可能構(gòu)建正向鏈接關(guān)系.這樣的分布結(jié)果也正好回答了第1個問題.

Fig. 2　Ratios of the number of links with respect to the number of interactions.圖2　鏈接數(shù)量同交互數(shù)量比率分布情況

為了回答第2個問題，采取相反的方式定義負(fù)向鏈接關(guān)系數(shù)量同負(fù)向交互數(shù)量的比率NK，其計(jì)算公式為

(10)

負(fù)向鏈接關(guān)系數(shù)量同負(fù)向交互數(shù)量比率NK隨著K變化的分布情況如圖2(b)所示.隨著負(fù)向交互數(shù)量K的增加，比率NK往往也隨之增加，其結(jié)果表明負(fù)向交互數(shù)量與負(fù)向鏈接關(guān)系存在較大的相關(guān)性，相似的分布結(jié)果正好回答了第2個問題.

4.2社會地位理論

為了驗(yàn)證地位理論與關(guān)系符號屬性之間的關(guān)聯(lián)關(guān)系，利用PolarityRank策略量化符號網(wǎng)絡(luò)節(jié)點(diǎn)的地位等級信息以嘗試回答2個問題：

1) 在符號網(wǎng)路中，低地位等級用戶是否更可能與高地位等級用戶建立正向鏈接關(guān)系?

2) 在符號網(wǎng)絡(luò)中，高地位等級用戶是否更可能與低地位等級用戶建立負(fù)向鏈接關(guān)系?

Fig. 3　Density estimate of numbers of trust and distrust relations.圖3　信任和不信任關(guān)系數(shù)量的密度評估

為了回答以上2個問題，首先將所有的用戶依據(jù)PolarityRank值降序排列，并將用戶的地位等級劃分為K個等級，在驗(yàn)證中將設(shè)置用戶等級的數(shù)量K=10.然后，針對信任關(guān)系分布統(tǒng)計(jì)構(gòu)建2個樣本，如果1≤i

從圖3(a)可以看出，低地位等級信任高地位等級數(shù)量同高地位等級信任低地位等級數(shù)量相比擁有較大的密度中心，這正好回答了第1個問題：低地位等級用戶更可能與高地位等級用戶建立正向鏈接關(guān)系.同樣，在圖3(b)中，對于不信任關(guān)系數(shù)量，高地位等級不信任低地位等級的數(shù)量的密度中心大于低地位等級不信任高地位等級用戶，這也正好回答了第2個問題：高地位等級用戶更可能與低地位等級用戶建立負(fù)向鏈接關(guān)系.這2個問題正好提供了關(guān)于社會地位理論和鏈接關(guān)系正負(fù)屬性之間存在一定關(guān)聯(lián)的證據(jù).

5鏈接預(yù)測模型及優(yōu)化算法

提出基于低秩矩陣分解方法[21]，以交互意見和地位理論作為模型構(gòu)建的動機(jī)，分別構(gòu)建相應(yīng)誘因的鏈接預(yù)測模型實(shí)現(xiàn)符號網(wǎng)絡(luò)中鏈接關(guān)系的預(yù)測.

5.1低秩矩陣鏈接預(yù)測MF

符號網(wǎng)絡(luò)G以鄰接矩陣形式表示，Gi j=1表示用戶ui與用戶uj之間建立正向鏈接關(guān)系，而Gi j=-1表示用戶ui與用戶uj之間建立負(fù)向鏈接關(guān)系.由于符號網(wǎng)絡(luò)矩陣G具有低秩結(jié)構(gòu)特征[10]并且較為稀疏，因此利用矩陣分解方法尋求低秩逼近的表示方式.將符號網(wǎng)絡(luò)矩陣G分解為低秩矩陣，并通過低秩矩陣的相乘重構(gòu)符號網(wǎng)絡(luò)矩陣G，補(bǔ)齊原矩陣中的缺失值，如式(11)所示：

G≈UHVT,

(11)

G≈UHUT.

(12)

由于符號網(wǎng)絡(luò)矩陣G較為稀疏，通過添加合理的正則化項(xiàng)方式來避免過度擬合(over-fitting).因此，MF模型定義如下：

(13)

5.2基于交互意見的鏈接預(yù)測模型MF-I

為了模擬交互意見用于鏈接預(yù)測，嘗試?yán)媒换ヒ庖妰A向與鏈接關(guān)系符號屬性之間存在的強(qiáng)相關(guān)性構(gòu)建基于交互意見的符號網(wǎng)絡(luò)鏈接預(yù)測模型MF-I.為了強(qiáng)調(diào)交互意見在符號網(wǎng)絡(luò)鏈接預(yù)測過程中的重要性，采取不依賴于已知的符號網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，即僅利用帶有意見傾向的評級行為數(shù)據(jù)構(gòu)建偽符號網(wǎng)絡(luò)矩陣X.因此，本模型假設(shè)已知的符號網(wǎng)絡(luò)并不存在，利用交互數(shù)據(jù)構(gòu)建偽符號網(wǎng)絡(luò)矩陣X替換真實(shí)符號網(wǎng)絡(luò)矩陣G.偽符號網(wǎng)絡(luò)矩陣X中的元素xi j定義如下：

(14)

其中，PIi j表示用戶ui到用戶uj的正向交互數(shù)量，NIi j表示用戶ui到用戶uj的負(fù)向交互數(shù)量.

偽符號網(wǎng)絡(luò)矩陣X依據(jù)正負(fù)向的交互數(shù)量而構(gòu)建，其元素值并不是真實(shí)的符號網(wǎng)絡(luò)數(shù)據(jù)，因此該矩陣并不可靠.根據(jù)交互意見與鏈接關(guān)系符號屬性之間的強(qiáng)相關(guān)性，引入權(quán)重矩陣W增強(qiáng)偽符號網(wǎng)絡(luò)矩陣X的可靠度，當(dāng)矩陣中Wi j權(quán)重越大，說明偽符號網(wǎng)絡(luò)矩陣X中用戶ui與用戶uj構(gòu)建鏈接的可能性越高.在矩陣分解過程中，通過矩陣元素Wi j控制對符號網(wǎng)絡(luò)矩陣元素xi j學(xué)習(xí)過程的貢獻(xiàn).權(quán)重矩陣W的元素定義如下：

(15)

其中，Ii j表示用戶ui與用戶uj產(chǎn)生的正向(或負(fù)向)交互數(shù)量，定義如下：

(16)

在構(gòu)建偽符號網(wǎng)絡(luò)矩陣X的基礎(chǔ)上，通過引入權(quán)重矩陣W用于增強(qiáng)待分解矩陣X的可靠度，進(jìn)而擴(kuò)展基于低秩矩陣分解的鏈接預(yù)測模型，因此，MF-I模型定義如下：

(17)

其中，⊙表示Hadamard乘積，針對維度相同的任意2個矩陣X和Y，(X⊙Y)i j=Xi j×Yi j.

5.3基于交互意見和地位理論的鏈接預(yù)測模型MF-SI

當(dāng)2個用戶之間存在等級差異時，依據(jù)地位理論，2個用戶之間應(yīng)該同時建立正、負(fù)鏈接關(guān)系，即兩者之間具有對稱關(guān)系屬性.但是，通過觀察Epinions數(shù)據(jù)集發(fā)現(xiàn)，僅僅大約1.7%的關(guān)系之間符合對稱關(guān)聯(lián)屬性.因此，當(dāng)構(gòu)建基于地位理論的符號網(wǎng)絡(luò)預(yù)測模型時，不僅僅考慮2個用戶之間的等級差異，還需利用交互意見的顯著方向性特征克服地位理論對稱性的局限，進(jìn)而構(gòu)建基于交互意見和地位理論的鏈接預(yù)測模型MF-SI.針對Leskovec等人[12,22]所提出的基于三元組的地位理論8種關(guān)系組合，用戶ui和用戶uj之間鏈接關(guān)系的符號屬性及鏈接關(guān)系權(quán)重s(i,j)可被形式化建模如下：

(18)

其中，sign(·)表示符號函數(shù)，g(ri,rj)表示2個用戶之間等級差異權(quán)重.根據(jù)經(jīng)驗(yàn)設(shè)置2個用戶之間的等級差異權(quán)重g(ri,rj)為

(19)

地位理論的正則化項(xiàng)[23]可被定義如下：

(20)

在基于低秩矩陣分解的鏈接預(yù)測基礎(chǔ)上，融合交互意見和地位理論構(gòu)建符號網(wǎng)絡(luò)鏈接預(yù)測模型，將交互意見建模為矩陣分解方法的增強(qiáng)可靠度因子，而地位理論建模為矩陣分解方法的正則化項(xiàng)，MF-SI模型定義如下：

(21)

其中，λ表示用于調(diào)諧地位理論貢獻(xiàn)程度系數(shù).

5.4優(yōu)化算法

針對交互意見和地位理論分別構(gòu)建基于交互意見的鏈接預(yù)測模型(MF-I)以及融合交互意見和地位理論的鏈接預(yù)測模型(MF-SI)，其中交互意見是以增強(qiáng)可靠度因子形式來構(gòu)建模型，而地位理論是以稀疏學(xué)習(xí)正則化項(xiàng)形式來構(gòu)建模型.針對式(13)的低秩矩陣分解方法建模符號網(wǎng)絡(luò)鏈接預(yù)測問題，采用Hsieh等人[10]所提出的方法，通過sigmoid變換函數(shù)懲罰分解時的符號不一致問題，以有效地解決算法優(yōu)化問題并提高預(yù)測質(zhì)量.

首先將式(21)的正則化項(xiàng)轉(zhuǎn)化為矩陣形式，具體過程如下：

然后，將式(21)表示為第k次迭代的Lagrangian函數(shù)形式，形式如下：

(22)

通過移除常量，Lk可被重寫為

Lk=-2Tr((WT⊙WT⊙GT)UHUT)+

(UHTUT))UHUT)+2λTr(UTζU).

(23)

Lk關(guān)于U和H的偏導(dǎo)數(shù)定義如下：

(UHUT))UHT+(WT⊙WT⊙(UHUT))UHT+

2(WT⊙WT⊙GT)UH-2(W⊙W⊙G)UHT-

(24)

(25)

對于H和U的偏導(dǎo)數(shù)，目標(biāo)函數(shù)(22)的優(yōu)化解決方法可通過梯度下降法進(jìn)行求解，具體如算法1所示：

算法1. MF-SI模型.

輸入: 符號網(wǎng)絡(luò)G、用戶-評論關(guān)聯(lián)矩陣E、用戶-評論的幫助評級矩陣R；

輸出: 正向鏈接關(guān)系對集合T′和負(fù)向鏈接關(guān)系對集合D′的排序列表.

① 利用矩陣E和矩陣R構(gòu)建交互意見矩陣;

② 依據(jù)式(15)計(jì)算矩陣W;

④ 隨機(jī)初始化U和H;

⑤ while 不收斂 do

⑨ end while

6實(shí)驗(yàn)

通過實(shí)驗(yàn)，驗(yàn)證3個問題：

1) 通過對比不同方法，所提模型是否有效地實(shí)現(xiàn)正向鏈接和負(fù)向鏈接預(yù)測?

2) 交互意見和地位理論作為可靠度因子和正則化項(xiàng)在所提鏈接預(yù)測模型中的作用如何?

3) 通過對比不同量化策略，哪些量化方法對提高模型預(yù)測質(zhì)量更加有效?

6.1實(shí)驗(yàn)設(shè)置和評價策略

實(shí)驗(yàn)設(shè)置：1)將所有的鏈接關(guān)系對表示為集合A，并按照鏈接的創(chuàng)建時間降序排列所有鏈接關(guān)系對，從A中選取時間T前的x%的鏈接關(guān)系對作為已知部分的符號網(wǎng)絡(luò)信息；2)對于每個x，收集正向鏈接、負(fù)向鏈接、用戶-評論關(guān)系信息和用戶-評論幫助(helpfulness)評級信息等相關(guān)內(nèi)容作為已知的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)和用戶交互行為數(shù)據(jù)；3)在實(shí)驗(yàn)數(shù)據(jù)集A中的x分別取值10，30，50，70，100形成已知數(shù)據(jù)集Dx，其余1-x%作為待評估數(shù)據(jù)集.

采用通用評價標(biāo)準(zhǔn)[24]以衡量所提模型的預(yù)測效果.對于每個待評估數(shù)據(jù)集，正向鏈接關(guān)系對集合和負(fù)向鏈接關(guān)系對集合分別用T和D表示，并作為評價標(biāo)準(zhǔn).然而，通過所提模型的預(yù)測結(jié)果依據(jù)模型所得置信度將所有用戶形成的鏈接關(guān)系對按照降序排列，選取前|T|鏈接關(guān)系對作為預(yù)測的正向鏈接集合T′，后|D|鏈接關(guān)系對作為預(yù)測的負(fù)向鏈接集合D′.最終，模型的預(yù)測質(zhì)量(prediction quality,PQ)被形式化表示為

(26)

6.2鏈接預(yù)測模型對比效果

為了回答第6節(jié)開始部分的第1個問題，對4個基本(baseline)方法進(jìn)行比較：

1) MF方法.該方法是將正負(fù)鏈接關(guān)系以矩陣形式表示，并使用矩陣分解方法獲得預(yù)測值.將越高的預(yù)測值看作是正向鏈接，相反，越低的預(yù)測值看作是負(fù)向鏈接.

2) Inter方法.該方法是基于交互意見與符號網(wǎng)絡(luò)鏈接屬性的強(qiáng)相關(guān)性而定義，依據(jù)正向和負(fù)向交互數(shù)量的排列鏈接關(guān)系對.正向交互數(shù)量越多，建立正向鏈接關(guān)系的可能性就越大；負(fù)向交互數(shù)量越多，建立負(fù)向鏈接關(guān)系的可能性就越大.

3) Status方法.該方法是基于地位理論與符號網(wǎng)絡(luò)鏈接屬性的強(qiáng)相關(guān)性而定義，依據(jù)鏈接關(guān)系2個用戶的等級差異值排列鏈接關(guān)系對.正向等級差異越大，建立正向鏈接關(guān)系的可能性就越大；負(fù)向等級差異越大，建立負(fù)向鏈接關(guān)系的可能性就越大.

4) Random方法.該方法是依據(jù)數(shù)據(jù)集中正向和負(fù)向鏈接比例隨機(jī)選取鏈接關(guān)系對.一般來說，在符號屬性預(yù)測中，隨機(jī)方法的結(jié)果就能達(dá)到約50%的準(zhǔn)確率.因此，該方法在文獻(xiàn)[24]中被建議作為基本方法，同隨機(jī)方法相比，更能體現(xiàn)預(yù)測模型提高的效果和意義.

在本組實(shí)驗(yàn)中，由于MF-I模型與MF-SI模型所使用的待分解矩陣不同，因此依據(jù)交互的數(shù)量降序排列并選取同其他模型具有相同鏈接關(guān)系數(shù)量的交互數(shù)據(jù)構(gòu)建偽符號網(wǎng)絡(luò)矩陣.通過交叉驗(yàn)證方法調(diào)諧MF-I和MF-SI模型參數(shù).為了達(dá)到一般性實(shí)驗(yàn)?zāi)康模瑢⑺心Ｐ头纸夂缶仃嘓和U的正則化項(xiàng)參數(shù)設(shè)置為α=β=0.1.MF-SI模型中，設(shè)置參數(shù)l=0.1.實(shí)驗(yàn)對比結(jié)果如圖4所示.

Fig. 4　Performance comparison of different link prediction methods.圖4　不同鏈接預(yù)測方法對比結(jié)果

通過實(shí)驗(yàn)結(jié)果可以看出：

1) MF-I模型和MF-SI模型在預(yù)測質(zhì)量方面一致優(yōu)于其他基本方法，特別是遠(yuǎn)遠(yuǎn)高于MF方法和隨機(jī)方法，說明所提出模型涉及的2個鏈接構(gòu)建誘因?qū)μ岣吣Ｐ皖A(yù)測準(zhǔn)確度發(fā)揮一定貢獻(xiàn).另外，同MF-I模型相比，MF-SI模型具有最好的實(shí)驗(yàn)效果，預(yù)測質(zhì)量平均高于MF-I模型0.025.說明集成交互意見與地位理論的模型要優(yōu)于其他模型.

2) 從MF-I模型和MF模型的對比結(jié)果可以發(fā)現(xiàn)，將交互意見建模為增強(qiáng)可靠度因子能夠提高矩陣分解方法的預(yù)測質(zhì)量.另外，基于交互意見與鏈接符號屬性強(qiáng)關(guān)聯(lián)關(guān)系的Inter方法也具有較好的預(yù)測效果，優(yōu)于Status方法和MF方法，充分說明交互意見在預(yù)測鏈接關(guān)系方面的重要作用.

3) MF-I模型和Status方法，隨著x%的增加，特別是當(dāng)達(dá)到50%以上時，實(shí)驗(yàn)效果不會顯著提高，甚至Status方法會出現(xiàn)下降，其主要原因是隨著已知鏈接關(guān)系數(shù)量的增加，等級差異不大的用戶之間建立鏈接的準(zhǔn)確率會有較為明顯的下降.

對所有的實(shí)驗(yàn)結(jié)果執(zhí)行T-test檢驗(yàn)，其結(jié)果說明所提高的實(shí)驗(yàn)效果是顯著的.總而言之，借助地位理論的正則化項(xiàng)所提出的MF-SI模型，同一些基本方法相比，特別是隨機(jī)方法，實(shí)驗(yàn)結(jié)果都有顯著提高；MF-I模型證明了交互意見在預(yù)測符號網(wǎng)絡(luò)方面具有重要作用；同樣，集成了交互意見和地位理論的MF-SI模型具有更好的效果，并且能夠?qū)崿F(xiàn)準(zhǔn)確地預(yù)測符號網(wǎng)絡(luò)鏈接關(guān)系符號屬性.這也正好回答了第6節(jié)開始部分所提出的第1個問題.

6.3模型的參數(shù)分析

MF-SI模型有2個重要參數(shù)控制其實(shí)驗(yàn)效果，分別是：1)W用于控制交互數(shù)據(jù)對待分解矩陣的可靠度;2)λ用于控制融入結(jié)構(gòu)平衡理論或社會地位理論對模型的貢獻(xiàn)程度.在本組實(shí)驗(yàn)中，嘗試固定一個參數(shù)取值同時調(diào)諧另一個參數(shù)方式，觀測MF-SI模型的效果.

Table 2　Different Measurements of Reliability Matrix W

從表2可以看出：

1) 同g(x)=1-1(1+ln(x+1))效果相比，g(x)=random效果降低較為明顯.表明函數(shù)g(x)不能設(shè)置為隨機(jī)數(shù)，同時也證明了基于交互數(shù)量定義的函數(shù)g(x)在模型中作用較為明顯，能夠提高模型的質(zhì)量.

2) 通過設(shè)置g(x)=1后，相當(dāng)于MF-SI模型去掉了交互意見的影響，同g(x)=1-1(1+ln(x+1))效果相比，g(x)=1的實(shí)驗(yàn)效果分別降低了0.03～0.04.

實(shí)驗(yàn)結(jié)果進(jìn)一步證明集成交互意見的重要性，其能夠有助于解決社會地位理論自身的局限性，進(jìn)而提高預(yù)測質(zhì)量.另外，以合理的方式融合多個社會學(xué)理論到稀疏學(xué)習(xí)模型中是能夠提高預(yù)測質(zhì)量的，這回答了第6節(jié)開始部分的第2個問題.

通過調(diào)諧參數(shù)λ控制地位理論正則化項(xiàng)的貢獻(xiàn)程度，λ分別取{0，0.01，0.1，0.5，1，5，10}.實(shí)驗(yàn)結(jié)果如圖5所示.

Fig. 5　Performance comparison for different parameter λ.圖5　不同參數(shù)λ取值實(shí)驗(yàn)效果對比結(jié)果

通過參數(shù)λ不同取值的比較，可以看出：

1) 對于MF-SI模型，當(dāng)參數(shù)λ=0.1時，MF-SI模型達(dá)到了峰值.

2) 參數(shù)λ=0，相當(dāng)于MF-SI模型去掉了地位理論正則化項(xiàng)部分.

隨著參數(shù)λ從0開始增加，實(shí)驗(yàn)效果也隨之得到了顯著的提高.這樣的結(jié)果說明地位理論的正則化項(xiàng)能夠提高模型的預(yù)測質(zhì)量.

6.4MF-SI等級量化策略對鏈接預(yù)測的影響

權(quán)重矩陣W的不同量化策略已經(jīng)在實(shí)驗(yàn)6.3節(jié)中進(jìn)行有效驗(yàn)證.在本組實(shí)驗(yàn)中，重點(diǎn)衡量MF-SI模型中社會等級系數(shù)，其用于控制2個用戶之間等級差異大小.采用3種社會等級策略量化用戶的社會等級，分別是PageRank,PolarityRank和Polarity-Indegree.依據(jù)量化后的權(quán)重排序所有節(jié)點(diǎn)，再利用式(19)計(jì)算2個節(jié)點(diǎn)的權(quán)重值g(ri,rj).除了以上3種策略之外，與6.3節(jié)實(shí)驗(yàn)相似，設(shè)置g(ri,rj)=1和g(ri,rj)=random.其中，i,j=1,2,…,n；random∈[0,1].表3表示采用不同社會等級量化策略的實(shí)驗(yàn)對比結(jié)果.

Table 3　Different Measurements of Social Statuses

從表3可以得出以下結(jié)論：

1)PolarityRank量化策略明顯優(yōu)于其他2種量化策略PageRank和PolarityIndegree，同時，PolarityIndegree量化策略優(yōu)于PageRank方法，說明當(dāng)量化符號網(wǎng)絡(luò)中節(jié)點(diǎn)的等級時，傳統(tǒng)PageRank方法沒有考慮負(fù)向入度鏈接的作用，從而影響了節(jié)點(diǎn)最終的等級權(quán)重.

2) 同PolarityRank，PolarityIndegree和PageRank量化策略相比，g(ri,rj)=1和g(ri,rj)=random獲得較差的效果，說明社會等級不能是隨機(jī)數(shù).

綜合以上2點(diǎn)，該實(shí)驗(yàn)結(jié)果有效地回答了第6節(jié)開始部分的第3個問題.

7結(jié)束語

符號網(wǎng)絡(luò)鏈接預(yù)測問題近幾年吸引了越來越多的研究人員的關(guān)注，同在已知鏈接關(guān)系基礎(chǔ)上預(yù)測符號屬性問題不同，鏈接預(yù)測既要預(yù)測未知鏈接關(guān)系還要預(yù)測鏈接的符號屬性.因此，符號網(wǎng)絡(luò)中鏈接預(yù)測問題較為困難，并且預(yù)測質(zhì)量也不理想.本文通過探索交互意見和地位理論實(shí)現(xiàn)符號網(wǎng)絡(luò)鏈接關(guān)系預(yù)測，從而形成新穎模型MF-I和MF-SI.實(shí)驗(yàn)結(jié)果表明所提模型同其他基本方法相比具有較好的預(yù)測質(zhì)量.

在今后的工作中，我們會繼續(xù)探索社會學(xué)理論以及其他相關(guān)理論，以更好地解析符號網(wǎng)絡(luò)數(shù)據(jù)；同時，進(jìn)一步探索符號網(wǎng)絡(luò)中相關(guān)應(yīng)用研究，比如節(jié)點(diǎn)排序、社區(qū)發(fā)現(xiàn)、信息傳播及推薦等.

致謝在此，衷心感謝亞利桑那州立大學(xué)DMML實(shí)驗(yàn)室劉歡(Huan Liu)教授、感謝DMML實(shí)驗(yàn)室的所有同行、感謝Yahoo實(shí)驗(yàn)室的湯繼良(Jiliang Tang)博士!

參考文獻(xiàn)

[1]Cheng Suqi, Shen Huawei, Zhang Guoqing, et al. Survey of signed network research[J]. Journal of Software, 2014, 25(1): 1-15 (in Chinese)(程蘇琦, 沈華偉, 張國清, 等. 符號網(wǎng)絡(luò)研究綜述[J]. 軟件學(xué)報, 2014, 25(1): 1-15)

[2]Heider F. Attitudes and cognitive organization[J]. Journal of Psychology, 1946, 21(1): 107-112

[3]Cartwright D, Harary F. Structural balance: A generalization of Heider’s theory[J]. Psychological Review, 1956, 63(5): 277-293

[4]Borzymek P, Sydow M. Trust and Distrust Prediction in Social Network with Combined Graphical and Review-Based Attributes[G] //Agent and Multi-Agent Systems: Technologies and Applications. Berlin: Springer, 2010: 122-131

[5]Ye J, Cheng H, Zhu Z, et al. Predicting positive and negative links in signed social networks by transfer learning[C] //Proc of the 22nd Int Conf on World Wide Web. New York: ACM, 2013: 1477-1488

[6]Zolfaghar K, Aghaie A. Mining trust and distrust relationships in social Web applications[C] //Proc of the 6th Int Conf on Intelligent Computer Communication and Processing. Piscataway, NJ: IEEE, 2010: 73-80

[7]Javari A, Mahdi J. Cluster-based collaborative filtering for sign prediction in social networks with positive and negative links[J]. ACM Trans on Intelligent Systems and Technology, 2014, 5(2): 1-24

[8]Symeonidis P, Eleftherios T. Transitive node similarity: Predicting and recommending links in signed social networks[J]. World Wide Web, 2014, 17(4): 743-776

[9]Lv L Y, Zhou T. Link prediction in complex networks: A survey[J]. Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 1150-1170

[10]Hsieh C J, Chiang K Y, Inderjit S. Low rank modeling of signed networks[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 507-515

[11]Yi C, Gu R T, Ji Y F. Sign inference for dynamic signed networks via dictionary learning[J]. Journal of Applied Mathematics, 2013, 2013(3): 701-710

[12]Leskovec J, Huttenlocher D, Kleinberg J. Predicting positive and negative links in online social networks[C] //Proc of the 19th Int Conf on World Wide Web. New York: ACM, 2010: 641-650

[13]Zheng X, Zeng D, Wang F. Social balance in signed networks[J]. Information Systems Frontiers, 2015, 17(5): 1077-1095

[14]Chiang K Y, Natarajan N, Tewari A, et al. Exploiting longer cycles for link prediction in signed networks[C] //Proc of the 20th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2011: 1157-1162

[15]Patidar A, Agarwal V, Bharadwaj K K. Predicting friends and foes in signed networks using inductive inference and social balance theory[C] //Proc of the 2012 Int Conf on Advances in Social Networks Analysis and Mining. Piscataway, NJ: IEEE, 2012: 384-388

[16]Priyanka A, Garg V K, Narayanam R. Link label prediction in signed social networks[C] //Proc of the 23rd Int Joint Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2013: 2591-2597

[17]Ramanthan G, Kumar R, Raghavan P, et al. Propagation of trust and distrust[C] //Proc of the 13th Int Conf on World Wide Web. New York: ACM, 2004: 403-412

[18]Lan Mengwei, Li Cuiping, Wang Shaoqing, et al. Survey of sign prediction algorithms in signed social networks[J]. Journal of Computer Research and Development, 2015, 52(2): 410-422 (in Chinese)(藍(lán)夢微, 李翠平, 王紹卿, 等. 符號社會網(wǎng)絡(luò)中正負(fù)關(guān)系預(yù)測算法研究綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(2): 410-422)

[19]Wang Y, Wang X, Zuo W L. Research on trust prediction from a sociological perspective[J]. Journal of Computer Science and Technology, 2015, 30(4): 843-858

[20]Wang Ying, Wang Xin, Zuo Wanli. Trust prediction modeling based on social theories[J]. Journal of Software, 2014, 25(12):2893-2904 (in Chinese)(王英, 王鑫, 左萬利. 基于社會學(xué)理論的信任關(guān)系預(yù)測模型研究[J]. 軟件學(xué)報, 2014, 25(12): 2893-2904)

[21]Liu Ye, Zhu Weiheng, Pan Yan, et al. Multiple sources fusion for link prediction via low-rank and sparse matrix decomposition[J]. Journal of Computer Research and Development, 2015, 52(2): 423-436 (in Chinese)(劉冶, 朱蔚恒, 潘炎, 等. 基于低秩和稀疏矩陣分解的多源融合鏈接預(yù)測算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(2): 423-436)

[22]Leskovec J, Huttenlocher D, Kleinberg J. Signed networks in social media[C] //Proc of the SIGCHI Conf on Human Factors in Computing Systems. New York: ACM, 2010: 1361-1370

[23]Wang Y, Wang X, Tang J, et al. Modeling status theory in trust prediction[C] //Proc of the 29th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2015: 1875-1881

[24]Nowell D L, 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

Wang Xin，born in 1981. PhD, lecturer. Member of China Computer Federation. His main research interests include data mining, machine learning, social network and recommendation system.

Wang Ying, born in 1981. PhD, associate professor. Senior member of China Computer Federation. Her main research interests include data mining, machine learning, social computing and search engine.

Zuo Wanli, born in 1957. Professor and PhD supervisor in the College of Computer Science and Technology, Jilin University. Senior member of China Computer Federation. His main research interests include information retrieval, Web mining and machine learning.

Exploring Interactional Opinions and Status Theory for Predicting Links in Signed Network

Wang Xin1,3,4, Wang Ying2,3, and Zuo Wanli2,3

1(SchoolofComputerTechnologyandEngineering,ChangchunInstituteofTechnology,Changchun130012)2(CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012)3(KeyLaboratoryofSymbolicComputationandKnowledgeEngineering(JilinUniversity),MinistryofEducation,Changchun130012)4(GuangxiKeyLaboratoryofTrustedSoftware(GuilinUniversityofElectronicTechnology),Guilin,Guangxi541004)

AbstractWith the wide spread and pervasion of social network, it brings more opportunities and novel problems for deep research on signed network, where link prediction is one of key problems in signed network. Interactional opinions and status theory are contributed to explain the construction and sign property of link relations, and provide theoretical principles for improving prediction quality. Therefore, this paper investigates link prediction problem in signed network from the perspective of interactional opinions and status theory, and constructs link prediction model by studying the strong correlation between two inducements and link relationship. Firstly, it explores interactional opinions to enhance the reliability of the decomposed matrix, and makes up for the limitations of status theory. Then, it models interactional opinions as enhanced reliability factor of matrix, and models status theory as the regularization terms. Finally, we construct the model of link prediction in signed network, namely MF-SI. Experimental results demonstrate that the model of MF-SI owns the best prediction quality compared with other baseline methods, which shows that the method of integrating interactional opinions with status theory implements link prediction in signed network.

Key wordssigned network; link prediction; sparse learning; interactional opinions; status theory

收稿日期：2015-12-12；修回日期：2016-02-03

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61300148)；吉林省科技計(jì)劃青年科研基金項(xiàng)目(20130522112JH)；廣西可信軟件重點(diǎn)實(shí)驗(yàn)室研究課題資助(kx201533)

通信作者：王英(wangying2010@jlu.edu.cn)

中圖法分類號TP181

DOI:計(jì)算機(jī)研究與發(fā)展10.7544?issn1000-1239.2016.20151172 Journal of Computer Research and Development53(4): 776-784， 2016

This work was supported by the National Natural Science Foundation of China (61300148), the Science and Technology Development Program of Jilin Province of China (20130522112JH), and Guangxi Key Laboratory of Trusted Software (kx201533).