基于結(jié)構(gòu)平衡理論與地位理論的符號(hào)預(yù)測(cè)算法

崔曉麗　薛樂洋　張鵬

摘要： 針對(duì)符號(hào)預(yù)測(cè)算法在預(yù)測(cè)準(zhǔn)確率和算法復(fù)雜度方面難以均衡的問題，有效地融合社會(huì)學(xué)發(fā)展規(guī)律與網(wǎng)絡(luò)局部特征，提出一種基于結(jié)構(gòu)平衡理論與地位理論計(jì)算節(jié)點(diǎn)相似度的符號(hào)預(yù)測(cè)算法。為更好的結(jié)合上述兩種理論對(duì)兩節(jié)點(diǎn)相似度得分的貢獻(xiàn)，引用調(diào)節(jié)因子，將基于兩種理論的相似度得分按照調(diào)節(jié)因子的權(quán)重求和，相似度的得分的正負(fù)即為邊符號(hào)預(yù)測(cè)的結(jié)果。最后將算法在多個(gè)不同數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，與經(jīng)典的CN算法和PSNBS算法在預(yù)測(cè)準(zhǔn)確率與算法復(fù)雜度兩個(gè)方面進(jìn)行對(duì)比分析。結(jié)果顯示該算法在預(yù)測(cè)準(zhǔn)確率方面與經(jīng)典算法非常接近，但在時(shí)間復(fù)雜度方面本文比經(jīng)典算法低一個(gè)數(shù)量級(jí)，明顯優(yōu)于經(jīng)典算法。

關(guān)鍵詞： 結(jié)構(gòu)平衡理論；地位理論；相似度；符號(hào)網(wǎng)絡(luò)；符號(hào)預(yù)測(cè)

中圖分類號(hào)： C94文獻(xiàn)標(biāo)識(shí)碼： A

Signed Prediction Algorithm Based on Structural Balance Theory and Status Theory

CUI Xiaoli1， XUE Leyang1，2， ZHANG Peng 1

Abstract：Aiming at the difficulty of balancing the accuracy and complexity of the sign prediction algorithm， this paper effectively integrates the law of social development and the local characteristics of the network， and proposes a sign prediction algorithm based on structural balance theory and status theory to calculate the similarity of nodes. In order to better combine the contribution of the above two theories to the similarity score of the two nodes， this paper uses the regulator to sum the similarity score based on the two theories according to the weight of the regulator， and the positive or negative of the similarity score is the result predicted by the edge symbol. Finally， the algorithm is tested on several different data sets and compared with the classical CN algorithm and PSNBS algorithm in two aspects of prediction accuracy and algorithm complexity. The proposed algorithm is very close to the classical algorithm in terms of prediction accuracy， but in terms of time complexity， it is an order of magnitude lower than the classical algorithm.It is obviously better than classical algorithm.

Key words： structural balance theory; status theory; similarity; signed network; sign prediction

0 引言

社會(huì)由各種錯(cuò)綜復(fù)雜的系統(tǒng)組成，隨著科學(xué)技術(shù)的進(jìn)步與發(fā)展，將這些復(fù)雜系統(tǒng)抽象成網(wǎng)絡(luò)去研究和分析的思路得到學(xué)術(shù)界的普遍認(rèn)可，例如常見的交通網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和電力網(wǎng)絡(luò)。信息化快速發(fā)展的同時(shí)產(chǎn)生了許多情感交互信息（如點(diǎn)贊、評(píng)價(jià)、評(píng)分等），如何將這種非量化的信息引入到復(fù)雜網(wǎng)絡(luò)中從而提升研究的深度和廣度，符號(hào)網(wǎng)絡(luò)為我們提供一個(gè)很好的研究思路。

符號(hào)網(wǎng)絡(luò)是指網(wǎng)絡(luò)中的邊具有正號(hào)或者負(fù)號(hào)的屬性［1］，其中，正邊表示積極、朋友、支持等正向關(guān)系，負(fù)邊表示消極、敵人、反對(duì)等負(fù)向關(guān)系。例如人與人之間可能是好友或者敵人的社交關(guān)系［2］、各個(gè)國(guó)家之間友好或敵對(duì)的關(guān)系［3］，這些事例都可以被抽象成符號(hào)網(wǎng)絡(luò)。符號(hào)網(wǎng)絡(luò)的相關(guān)研究目前主要集中在符號(hào)網(wǎng)絡(luò)的傳播、符號(hào)預(yù)測(cè)、平衡性以及社團(tuán)劃分4個(gè)方向，其中符號(hào)預(yù)測(cè)是更為基礎(chǔ)性的問題，主要關(guān)注網(wǎng)絡(luò)中邊符號(hào)信息的還原與預(yù)測(cè)，研究符號(hào)預(yù)測(cè)問題能夠?yàn)槠渌?個(gè)問題的研究提供理論基礎(chǔ)。

目前，符號(hào)預(yù)測(cè)工作的相關(guān)研究成果已有很多，主要可以分為兩類：基于矩陣的符號(hào)預(yù)測(cè)算法與基于分類的符號(hào)預(yù)測(cè)算法［4］。基于矩陣的符號(hào)預(yù)測(cè)算法將符號(hào)網(wǎng)絡(luò)映射為矩陣，然后利用矩陣分解、矩陣填充等方式進(jìn)行符號(hào)預(yù)測(cè)。Guha［5］提出的符號(hào)預(yù)測(cè)方法是通過信任傳播模型進(jìn)行預(yù)測(cè)，這是符號(hào)網(wǎng)絡(luò)中符號(hào)預(yù)測(cè)問題最早的研究成果。Agrawal等［6］提出通過矩陣的奇異值分解、特征值分解或者和核函數(shù)分解的方法也可以有效進(jìn)行符號(hào)預(yù)測(cè)。Hsieh等［7］結(jié)合弱結(jié)構(gòu)平衡原理，通過低秩矩陣填充算法進(jìn)行符號(hào)預(yù)測(cè)。基于分類的符號(hào)預(yù)測(cè)算法即將符號(hào)網(wǎng)絡(luò)中的符號(hào)預(yù)測(cè)問題轉(zhuǎn)化為分類問題，然后通過各種分類算法進(jìn)行正負(fù)號(hào)預(yù)測(cè)。Leskovec等［8］提出一種結(jié)合結(jié)構(gòu)平衡理論與地位理論的機(jī)器學(xué)習(xí)算法。Yang等［9］提出基于行為關(guān)系的相互作用模型，該模型通過無監(jiān)督或半監(jiān)督模型進(jìn)行符號(hào)預(yù)測(cè)。Symeonidis等［10］定義了一個(gè)基于節(jié)點(diǎn)相似度的模型，該模型可以有效捕獲局部圖特征，從而進(jìn)行符號(hào)預(yù)測(cè)。佘宏?。?1］提出的基于共同鄰居的符號(hào)網(wǎng)絡(luò)鏈接預(yù)測(cè)算法CN，結(jié)合節(jié)點(diǎn)符號(hào)密度和網(wǎng)絡(luò)拓?fù)涮卣鬟M(jìn)行預(yù)測(cè)，提高了負(fù)邊的預(yù)測(cè)準(zhǔn)確率。張維玉等［12］提出一種結(jié)合結(jié)構(gòu)平衡理論的機(jī)器學(xué)習(xí)算法，該算法首次引入PageTrust度量網(wǎng)絡(luò)中節(jié)點(diǎn)的重要程度。劉苗苗等［13］提出一種基于結(jié)構(gòu)平衡理論和相似度的新算法PSNBS，該算法計(jì)算基于結(jié)構(gòu)平衡理論的Two-step路徑和Three-step路徑的相似度得分，引入影響因子λ調(diào)節(jié)不同路徑得分貢獻(xiàn)度，最后對(duì)相似度得分進(jìn)行分類得出預(yù)測(cè)結(jié)果。

綜上所述，目前被大家廣泛接受較為經(jīng)典的是CN算法和PSNBS算法，這兩個(gè)算法在基于結(jié)構(gòu)平衡理論與路徑相似度預(yù)測(cè)時(shí)能夠取得較高的預(yù)測(cè)準(zhǔn)確率，并且隨著選取結(jié)構(gòu)平衡環(huán)中環(huán)邊數(shù)的增加，其算法準(zhǔn)確率也會(huì)提升，但是環(huán)數(shù)增加會(huì)使得算法復(fù)雜度快速升高。在快速發(fā)展的大數(shù)據(jù)時(shí)代，許多網(wǎng)絡(luò)的邊數(shù)達(dá)到百萬以上，算法復(fù)雜度的升高將會(huì)帶來很高的成本。因此，本文在結(jié)構(gòu)平衡理論的基礎(chǔ)上引入地位理論，期望在維持符號(hào)預(yù)測(cè)準(zhǔn)確率的前提下降低算法復(fù)雜度。

1 算法介紹

1.1 結(jié)構(gòu)平衡理論

1946年Heider［2］提出一種基于社會(huì)心理學(xué)的結(jié)構(gòu)平衡理論，該理論對(duì)符號(hào)網(wǎng)絡(luò)的發(fā)展具有重要意義。該模型將個(gè)體之間的相互關(guān)系分為積極和消極兩種類型，描述并分析個(gè)體之間關(guān)系類型的演化規(guī)律。1956年Cartwright和Harary［14］將結(jié)構(gòu)平衡理論推廣至圖論中，并通過數(shù)學(xué)語言將兩類關(guān)系描述為符號(hào)網(wǎng)絡(luò)，網(wǎng)絡(luò)中用邊的正、負(fù)符號(hào)分別表示積極關(guān)系和消極關(guān)系。2010年Leskovec等［15］將結(jié)構(gòu)平衡理論推廣至符號(hào)網(wǎng)絡(luò)中的符號(hào)預(yù)測(cè)問題。

在無向符號(hào)網(wǎng)絡(luò)中的結(jié)構(gòu)平衡理論主要通過三角形的結(jié)構(gòu)平衡討論，由3個(gè)節(jié)點(diǎn)組成的三角形共有3條邊，其中每條邊有正號(hào)和負(fù)號(hào)兩種可能性，共有4種三角形組合模式［16］。4種組合模式形成4個(gè)直觀認(rèn)識(shí)：1）朋友的朋友是我的朋友；2）朋友的敵人是我的敵人；3）敵人的朋友是我的敵人；4）敵人的敵人是我的朋友。

如圖1所示，圖1中a、b為結(jié)構(gòu)平衡三角形，c、d為不平衡三角形。不平衡三角形不符合社會(huì)發(fā)展規(guī)律，人們總是盡量避免這種情況發(fā)生。因此，實(shí)際生活中結(jié)構(gòu)平衡三角形的數(shù)量遠(yuǎn)大于不平衡的三角形的數(shù)量［17］。

1.2 地位理論

2010年Leskovec和Kleinberg等在文獻(xiàn)［8］中通過大量分析有向網(wǎng)絡(luò)中用戶建立連接的傾向，提出了適用有向網(wǎng)絡(luò)的新理論——地位理論。結(jié)構(gòu)平衡理論可以視為朋友與敵人、支持與反對(duì)等多種關(guān)系的建模，其主要針對(duì)于無向符號(hào)網(wǎng)絡(luò)的符號(hào)預(yù)測(cè)問題。與結(jié)構(gòu)平衡理論不同，地位理論適用于刻畫有向網(wǎng)絡(luò)，相關(guān)研究表明，在有向網(wǎng)絡(luò)符號(hào)預(yù)測(cè)問題中，引入地位理論可以有效提升其預(yù)測(cè)準(zhǔn)確率［8，18-19］。

地位理論可以視為基于個(gè)體身份的判定，地位理論認(rèn)為符號(hào)網(wǎng)絡(luò)中邊的符號(hào)受兩節(jié)點(diǎn)之間邊的方向以及兩節(jié)點(diǎn)的地位影響，其理論如圖2所示。地位理論與結(jié)構(gòu)平衡理論兩者都適用于由3個(gè)節(jié)點(diǎn)構(gòu)成的三角形，圖3中給出了8種地位理論認(rèn)為合理的三角形關(guān)系組成模式。其中虛線表示節(jié)點(diǎn)A與節(jié)點(diǎn)B之間的連邊符號(hào)是缺失的，兩節(jié)點(diǎn)之間的符號(hào)傾向受節(jié)點(diǎn)地位的影響。

1.3 基于符號(hào)網(wǎng)絡(luò)基礎(chǔ)理論與相似度的算法

為了更好地平衡符號(hào)預(yù)測(cè)準(zhǔn)確率與算法復(fù)雜度的關(guān)系，本文結(jié)合社會(huì)學(xué)發(fā)展規(guī)律與網(wǎng)絡(luò)局部特征定義了兩節(jié)點(diǎn)相似度的概念，通過節(jié)點(diǎn)相似度預(yù)測(cè)邊符號(hào)，我們將此稱之為PSNCN算法。首先，綜合考慮兩節(jié)點(diǎn)之間的共同鄰居的數(shù)量以及共同鄰居的度對(duì)于節(jié)點(diǎn)相似度的影響。在度量共同鄰居度對(duì)兩節(jié)點(diǎn)相似度影響時(shí)，假設(shè)共同鄰居的度越小對(duì)兩節(jié)點(diǎn)的相似度貢獻(xiàn)越大；在度量共同鄰居數(shù)量對(duì)兩節(jié)點(diǎn)間相似度的影響時(shí)，假設(shè)共同鄰居越多對(duì)兩節(jié)點(diǎn)相似度貢獻(xiàn)更大。其次，結(jié)合結(jié)構(gòu)平衡理論與地位理論對(duì)網(wǎng)絡(luò)符號(hào)的影響，定義兩節(jié)點(diǎn)之間的相似度。在度量地位理論對(duì)節(jié)點(diǎn)相似度的影響時(shí)，先將網(wǎng)絡(luò)中所有的負(fù)邊轉(zhuǎn)化為逆向的正邊，然后使預(yù)測(cè)邊符號(hào)與長(zhǎng)度為2的路徑所在的三角形盡可能滿足地位理論。最后，為更好地結(jié)合上述兩種理論對(duì)兩節(jié)點(diǎn)相似度得分的貢獻(xiàn)，引入調(diào)節(jié)因子，將基于兩種理論的相似度得分按照調(diào)節(jié)因子的權(quán)重求和，最終相似度的得分的正負(fù)即為邊符號(hào)預(yù)測(cè)的結(jié)果。

設(shè)G=V，E，S為符號(hào)網(wǎng)絡(luò)中的有向無權(quán)圖；其中V=v1，v2，…vn代表網(wǎng)絡(luò)中所有節(jié)點(diǎn)組成的集合，E=e（vi，vj）代表由節(jié)點(diǎn)vi指向vj的有向邊集合。在有向邊集合E中，vi，vj∈V，e（vi，vj）∈0，1，若e（vi，vj）=1則說明節(jié)點(diǎn)對(duì)〈vi，vj〉存在有向邊，否則不存在有向邊。S=s（vi，vj）為有向邊的符號(hào)集合。在符號(hào)集合S中，vi，vj∈V，svi，vj∈0，1，-1，若svi，vj=1，則節(jié)點(diǎn)對(duì)〈vi，vj〉之間的邊符號(hào)為正；若svi，vj=-1，則節(jié)點(diǎn)對(duì)〈vi，vj〉之間的邊符號(hào)為負(fù)；若svi，vj=0，則節(jié)點(diǎn)對(duì)〈vi，vj〉之間的邊無符號(hào)。對(duì)于vi，vj∈V且svi，vj=0，將節(jié)點(diǎn)對(duì)〈vi，vj〉基于符號(hào)網(wǎng)絡(luò)理論的相似度得分定義為CNScore2vi，vj，具體計(jì)算如式（1）所示。

2 結(jié)果與討論

2.1 數(shù)據(jù)集

為了更好地驗(yàn)證PSNCN算法的預(yù)測(cè)準(zhǔn)確率，本文下載（http：//snap.stanford.edu/）Epinions，Slashdot和Wikipedia三個(gè)數(shù)據(jù)集進(jìn)行符號(hào)預(yù)測(cè)。這些數(shù)據(jù)集目前被廣泛應(yīng)用于各類符號(hào)網(wǎng)絡(luò)的符號(hào)預(yù)測(cè)問題中，是研究符號(hào)網(wǎng)絡(luò)的經(jīng)典數(shù)據(jù)集，3個(gè)數(shù)據(jù)集基本信息（見表1）：1）Epinions：是一個(gè)大眾消費(fèi)者點(diǎn)評(píng)網(wǎng)站。該網(wǎng)站會(huì)為用戶之間提供一個(gè)信任機(jī)制，允許用戶創(chuàng)建有向符號(hào)鏈接來表達(dá)對(duì)其他用戶信任或者不信任的態(tài)度。2）Slashdot：是一個(gè)以其特定的用戶社區(qū)而聞名的資訊科技網(wǎng)站。在2002年，Slashdot引入了Slashdot Zoo特性，允許用戶將彼此標(biāo)記為朋友或敵人，由此形成一個(gè)用戶間是朋友或敵人的符號(hào)網(wǎng)絡(luò)。3）Wikipedia：是一個(gè)用多種語言編寫而成的網(wǎng)絡(luò)百科全書，該網(wǎng)絡(luò)的用戶可以申請(qǐng)成為維基百科的管理員，然后由維基百科的其他成員投支持、中立或反對(duì)的票。這就形成了一個(gè)有向的簽名網(wǎng)絡(luò)，其中節(jié)點(diǎn)代表維基百科的成員，邊代表投票。

2.2 數(shù)據(jù)集劃分及評(píng)價(jià)指標(biāo)

采用k-折疊交叉驗(yàn)證法劃分各數(shù)據(jù)集，即將數(shù)據(jù)集按邊隨機(jī)劃分為k份，本實(shí)驗(yàn)中k主要取10，5，3。從E中取一份作為測(cè)試集Ete、剩余k-1份作為訓(xùn)練集Etr，并且滿足Ete∪Etr=E和Ete∩Etr=。將以上實(shí)驗(yàn)重復(fù)k次，其中k份數(shù)據(jù)中的每一份數(shù)據(jù)都僅被選擇一次，最后取k次預(yù)測(cè)準(zhǔn)確率的平均值為算法符號(hào)預(yù)測(cè)準(zhǔn)確率。這種方法的優(yōu)點(diǎn)是可以使符號(hào)網(wǎng)絡(luò)數(shù)據(jù)集中的每一條邊都有一次機(jī)會(huì)被預(yù)測(cè)。為了更好地與各種經(jīng)典算法進(jìn)行對(duì)比分析，采用符號(hào)網(wǎng)絡(luò)中常用的評(píng)價(jià)符號(hào)預(yù)測(cè)準(zhǔn)確率的指標(biāo)accuracy，該指標(biāo)通過混淆矩陣來表示預(yù)測(cè)準(zhǔn)確率，指標(biāo)公式如式（6）所示，混淆矩陣如表2所示。

2.3 PSNCN算法的預(yù)測(cè)準(zhǔn)確率

為了更好地驗(yàn)證評(píng)價(jià)模型效果，針對(duì)3個(gè)數(shù)據(jù)集抽取不同比例的邊作為測(cè)試集進(jìn)行試驗(yàn)，預(yù)測(cè)模型準(zhǔn)確率，同時(shí)為更好地度量不同理論對(duì)于節(jié)點(diǎn)相似度貢獻(xiàn)的不同程度，引入調(diào)節(jié)因子λ，圖6中給出了在λ取不同值的情況下，PSNCN算法針對(duì)不同數(shù)據(jù)集以及不同比例測(cè)試集的預(yù)測(cè)準(zhǔn)確率，實(shí)驗(yàn)中測(cè)試集占符號(hào)網(wǎng)絡(luò)中邊的比例為1/k，預(yù)測(cè)準(zhǔn)確率值是k次獨(dú)立實(shí)驗(yàn)的平均值，k值分別取10，5，3，PSNCN算法預(yù)測(cè)準(zhǔn)確率結(jié)果如圖5所示。

由圖5可以看出，PSNCN算法預(yù)測(cè)準(zhǔn)確率受調(diào)節(jié)因子λ的影響，且在本實(shí)驗(yàn)所選取的3個(gè)大型符號(hào)網(wǎng)絡(luò)數(shù)據(jù)集中，隨著λ的增大，預(yù)測(cè)準(zhǔn)確率的數(shù)值均呈現(xiàn)出先增大后減小的趨勢(shì)，在λ等于0.5附近時(shí)，預(yù)測(cè)準(zhǔn)確率結(jié)果趨向最優(yōu)。該準(zhǔn)確率值的變化可以說明PSNCN算法在符號(hào)預(yù)測(cè)過程中，地位理論和結(jié)構(gòu)平衡理論發(fā)揮了不同的作用。針對(duì)以上數(shù)據(jù)集在符號(hào)預(yù)測(cè)過程中測(cè)試集中邊的數(shù)量占所有邊的比例1/k取值越小，其預(yù)測(cè)準(zhǔn)確率越高，但是預(yù)測(cè)準(zhǔn)確率整體差距很小，數(shù)值較為接近。該變化說明PSNCN算法受已知信息的影響較小，在已知符號(hào)信息較少時(shí)仍保持較高的預(yù)測(cè)準(zhǔn)確率。

2.4 PSNCN算法復(fù)雜度

2.4.1 PSNCN算法的時(shí)間復(fù)雜度分析

第1步：計(jì)算節(jié)點(diǎn)對(duì)〈vi，vj〉的共同鄰居，首先尋找節(jié)點(diǎn)vi的所有鄰居，然后判斷其是否也為節(jié)點(diǎn)vj的鄰居，因此其時(shí)間復(fù)雜度為Odi，其中di為節(jié)點(diǎn)i的度。然后查找測(cè)試集中所有待預(yù)測(cè)邊的共同鄰居，其復(fù)雜度為OE2〈d〉，其中，E為符號(hào)網(wǎng)絡(luò)中邊的總數(shù)量，〈d〉為平均度。

第2步：計(jì)算節(jié)點(diǎn)對(duì)的相似度得分，需對(duì)該節(jié)點(diǎn)對(duì)的所有共同鄰居進(jìn)行計(jì)算。節(jié)點(diǎn)vi為節(jié)點(diǎn)vj的鄰居的概率為di/N，其中，N為符號(hào)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目。因此計(jì)算基于地位理論與結(jié)構(gòu)平衡理論的相似度得分的時(shí)間復(fù)雜度為OE〈d〉/N。

綜上，PSNCN算法第1步的時(shí)間復(fù)雜度更高，PSNCN算法時(shí)間復(fù)雜度為OE〈d〉。

2.4.2 PSNCN算法的空間復(fù)雜度分析

有向符號(hào)網(wǎng)絡(luò)以E*3維鄰接矩陣形式存儲(chǔ)。矩陣的每行表示網(wǎng)絡(luò)的一條邊。前兩列分別為起始節(jié)點(diǎn)及終結(jié)點(diǎn)，第3列表示連邊的符號(hào)。計(jì)算中的中間數(shù)據(jù)均針對(duì)每個(gè)預(yù)測(cè)邊存儲(chǔ)，可以用L行矩陣表示。第1列存儲(chǔ)BScore2信息，第2列存儲(chǔ)RScore2信息，第3列加權(quán)結(jié)果CNScore2信息。另外，需存儲(chǔ)每個(gè)節(jié)點(diǎn)的鄰居集合，對(duì)每個(gè)節(jié)點(diǎn)以鏈表方式存儲(chǔ)其連接點(diǎn)，使用空間為ONd=2E，該空間還使用4N空間存儲(chǔ)每個(gè)節(jié)點(diǎn)的正出度、正入度、負(fù)出度、負(fù)入度。綜上，PSNCN的空間復(fù)雜度為OE+OL+OV〈d〉，即OE。

2.5 與經(jīng)典算法的準(zhǔn)確率和時(shí)間復(fù)雜度對(duì)比

PSNCN算法通過結(jié)合符號(hào)網(wǎng)絡(luò)理論與節(jié)點(diǎn)間路徑信息計(jì)算節(jié)點(diǎn)相似度，從而預(yù)測(cè)符號(hào)網(wǎng)絡(luò)中的邊的未知符號(hào)。為了更好地驗(yàn)證PSNCN算法性能，將該算法的預(yù)測(cè)準(zhǔn)確率及算法復(fù)雜度與符號(hào)預(yù)測(cè)的經(jīng)典算法CN和PSNBS算法進(jìn)行了對(duì)比實(shí)驗(yàn)。對(duì)比實(shí)驗(yàn)中，各算法采用相同的符號(hào)網(wǎng)絡(luò)數(shù)據(jù)集（Epinions、Slashdot、Wikipedia）、相同的測(cè)試集比例、相同的評(píng)價(jià)指標(biāo)accuracy。此外，PSNCN算法根據(jù)2.4章節(jié)結(jié)果，針對(duì)3個(gè)的數(shù)據(jù)集，λ的值分別設(shè)定為0.4，0.5，0.5。各算法的預(yù)測(cè)準(zhǔn)確率統(tǒng)計(jì)結(jié)果如表3所示，算法復(fù)雜度如表4所示。

由表3可以看出，針對(duì)不同數(shù)據(jù)集以及同一數(shù)據(jù)集不同比例測(cè)試集，PSNCN算法與PSNBS算法的預(yù)測(cè)準(zhǔn)確率明顯高于CN算法，PSNCN算法比CN算法預(yù)測(cè)準(zhǔn)確率平均值高0.01以上，這對(duì)于預(yù)測(cè)準(zhǔn)確率已達(dá)到較高的算法是一個(gè)很大的提升。在PSNCN算法與PSNBS算法的預(yù)測(cè)準(zhǔn)確率之間，PSNCN算法的預(yù)測(cè)準(zhǔn)確率略低于PSNBS算法，但其準(zhǔn)確率數(shù)值與PSNBS算法非常接近，特別在大型符號(hào)網(wǎng)絡(luò)Epinions中，在測(cè)試集比例為10%的情況下，PSNCN算法的預(yù)測(cè)準(zhǔn)確率僅比PSNBS算法預(yù)測(cè)準(zhǔn)確率低0.002，在測(cè)試集比例為33.33%時(shí)，兩者算法預(yù)測(cè)準(zhǔn)確率差距最大僅為0.006。

由表4可知，3個(gè)算法的空間復(fù)雜度均為O|E|。在時(shí)間復(fù)雜度方面，CN算法與PSNCN算法的時(shí)間復(fù)雜度為O|E|〈d〉，PSNBS算法的時(shí)間復(fù)雜度為O|E|〈d〉2，PSNBS算法時(shí)間復(fù)雜度明顯高于PSNCN算法。

通過與各算法預(yù)測(cè)準(zhǔn)確率和算法復(fù)雜度對(duì)比分析，PSNCN算法與PSNBS算法的預(yù)測(cè)準(zhǔn)確率能明顯優(yōu)于CN算法，PSNCN算法的預(yù)測(cè)準(zhǔn)確率與PSNBS算法較為接近，但PSNBS算法時(shí)間復(fù)雜度明顯高于PSNCN算法，特別是對(duì)于大型稠密符號(hào)網(wǎng)絡(luò)，網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度〈d〉≈N，則PSNBS算法與PSNCN算法的時(shí)間復(fù)雜度則分別為O|E|N2和O|E|N，PSNBS算法的時(shí)間復(fù)雜度是PSNCN算法時(shí)間復(fù)雜度的N倍，時(shí)間復(fù)雜度的提升將會(huì)造成巨大的時(shí)間成本。綜上所述，PSNCN算法能夠更好地平衡預(yù)測(cè)準(zhǔn)確率和算法復(fù)雜度。

3 結(jié)論

本文提出基于符號(hào)網(wǎng)絡(luò)基礎(chǔ)理論與相似度的符號(hào)預(yù)測(cè)算法PSNCN，該算法綜合考慮結(jié)構(gòu)平衡理論與地位理論以及路徑信息定義兩節(jié)點(diǎn)之間的相似度，改進(jìn)了已有的結(jié)合結(jié)構(gòu)平衡理論與相似度的算法的不足之處。PSNCN算法在多個(gè)大型符號(hào)網(wǎng)絡(luò)數(shù)據(jù)集以及不同比例測(cè)試集上進(jìn)行符號(hào)預(yù)測(cè)，并采用經(jīng)典的準(zhǔn)確率評(píng)價(jià)指標(biāo)accuracy，將實(shí)驗(yàn)結(jié)果與目前經(jīng)典的符號(hào)預(yù)測(cè)算法CN和PSNBS在預(yù)測(cè)準(zhǔn)確率和算法復(fù)雜度兩個(gè)方面進(jìn)行對(duì)比分析。驗(yàn)證了本文算法PSNCN在取得較高的預(yù)測(cè)準(zhǔn)確率的同時(shí)算法復(fù)雜度較低，且隨著測(cè)試集比例的增加，仍取得較高的預(yù)測(cè)準(zhǔn)確率。此外，如何將算法中節(jié)點(diǎn)相似度等相關(guān)信息應(yīng)用到符號(hào)網(wǎng)絡(luò)的社團(tuán)劃分及推薦算法中，從而幫助我們進(jìn)行更精準(zhǔn)的社團(tuán)劃分與推薦是我們下一步需要研究的內(nèi)容。

參考文獻(xiàn)：

［1］程蘇琦，沈華偉，張國(guó)清，等.符號(hào)網(wǎng)絡(luò)研究綜述［J］.軟件學(xué)報(bào)，2014，25（1）：1-15.

CHENG S Q， SHEN H W， ZHANG G Q， et al.Survey of signed network research［J］.Journal of Software，2014，25（1）：1-15.

［2］HEIDER F. Attitudes and cognitive organization［J］. The Journal of Psychology Interdisciplinary and Applied， 1946， 21（1）：107-112.

［3］GHOSN F， PALMER G， BREMER S A. The MID3 data set， 1993-2001： procedures， coding rules， and description［J］. Conflict Management and Peace Science， 2004， 21（2）：133-154.

［4］藍(lán)夢(mèng)微，李翠平，王紹卿，等.符號(hào)社會(huì)網(wǎng)絡(luò)中正負(fù)關(guān)系預(yù)測(cè)算法研究綜述［J］.計(jì)算機(jī)研究與發(fā)展，2015，52 （2）：410-422.

LAN M W， LI C P， WANG S Q， et al. Survey of sign prediction algorithms in signed social networks［J］.Journal of Computer Research and Development，2015，52（2）：410-422.

［5］GUHA R， KUMAR R， RAGHAVAN P， et a1. Propagation of trust and distrust［C］// Proc of the 13th Int Conf onworld wide Web.New York： ACM， 2004： 403-412.

［6］AGRAWAL P， GARG V K，NARAYANAM R. Link label prediction in signed social networks［C］//Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Beijing： AAAI，2013：2591-2597.

［7］HSIEH C J， CHIANG K Y， DHILLON I S. Low rank modeling of signed networks［C］//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York：ACM，2012：507-515.

［8］LESKOVEC J， HUTTENLOCHER D，KLEINBERG J.Signed networks in social media［C］//Proceedings of the SIGCHI International Conference on Human Factors in Computing Systems.New York：ACM，2010：1361-1370.

［9］YANG S H， SMOLA A J，LONG B， et al.Friend or frenemy？prediction signed ties in social networks［C］//Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval.New York：ACM，2012：555-564.

［10］ SYMEONIDIS P， TIAKAS E. Transitive node similarity：Prediction and recommending links in signed social networks［J］. Internet & Web Information Systems，2014，17（4）：743-776.

［11］ 佘宏俊，胡夢(mèng)緣.基于符號(hào)網(wǎng)絡(luò)的邊值預(yù)測(cè)方法研究［J］.武漢理工大學(xué)學(xué)報(bào)（信息與管理工程版），2015，37 （5）：464-468.

SHE H J， HU M Y. Research of link prediction based on signed networks［J］. Journal of Wuhan University of Technology （Information & Management Engineering）， 2015，37（5）：464-468.

［12］ ZHANG W Y， WU B， LIU Y. Integrating multi-feature for link sign prediction in signed networks［J］. Journal of Beijing University of Posts and Telecommunications， 2014， 37（5）： 80-84.

［13］ 劉苗苗，郭景峰，陳晶.相似度與結(jié)構(gòu)平衡論結(jié)合的符號(hào)網(wǎng)絡(luò)邊值預(yù)測(cè)［J］.工程科學(xué)與技術(shù)，2018， 50（4）： 161-169.

LIU M M， GUO J F， CHEN J. Link prediction in signed networks based on similarity and structural balance theory［J］.Advanced Engineering Sciences，2018，50（4）：161-169.

［14］ CA RTWRIGHT D， HARARY F. Structural balance： a generalization of Heiders theory ［J］. Psychological Review，1956，63（5）：27.

［15］ LESKOVEC J， HUTTENLOCHER D， K1EINBERG 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.

［16］ SRINIVASAN A. Local balancing influences global structure in social networks［J］.Proc of the National Academy of Sciences of the United States of America， 2011， 108（5）：1751-1752.

［17］ EASLEY D， KLEINBERG J. Networks， Crowds， and Markets： Reasoning About a Highly connected world［M］. New York：Cambridge University Press，2010：119-152.

［18］ CHIANG K Y， NATARAJAN N， TEWARI A， et al. Exploiting longer cycles for link prediction in signed networks［C］// Proceedings of the 20th ACM Conference on Information and Knowledge Management.New York： ACM， 2011：1157-1162.

［19］ CHIANG K Y， HSIEH C J， NATARAJAN N， et al. Prediction and clustering in signed networks： a local to global perspective［J］. Journal of Machine Learning Research， 2013， 15（1）：1177-1213.

（責(zé)任編輯 耿金花）

收稿日期： 2022-03-09；修回日期：2022-06-07

第一作者： 崔曉麗（1995-），女，山東日照人，碩士研究生，主要研究方向?yàn)榉?hào)網(wǎng)絡(luò)理論及應(yīng)用。

通信作者： 張鵬（1981-），女，北京人，博士，副教授，主要研究方向?yàn)閺?fù)雜系統(tǒng)，復(fù)雜網(wǎng)絡(luò)。