張長倫 趙意北京建筑大學(xué)

?

社交網(wǎng)絡(luò)中基于用戶隱私信息的鏈路預(yù)測

張長倫 趙意
北京建筑大學(xué)

摘要：社交網(wǎng)絡(luò)中的鏈路預(yù)測算法往往僅使用用戶節(jié)點度的信息，然而社交網(wǎng)絡(luò)是真實社會關(guān)系的影射，個人用戶本身存在許多隱私信息，并且這些隱私信息對鏈路預(yù)測有很大影響。本文在研究有向社交網(wǎng)絡(luò)中的鏈路預(yù)測算法的基礎(chǔ)上，提出一種綜合考慮節(jié)點度的信息以及用戶節(jié)點的隱私信息的鏈路預(yù)測方法,提高了預(yù)測的準(zhǔn)確度。

1　引言

社交網(wǎng)絡(luò)是指個體成員之間因為互動而形成的相對穩(wěn)定的關(guān)系體系，關(guān)注的是人們之間的互動和聯(lián)系[1]。社交網(wǎng)絡(luò)的建立方便了用戶之間的思想交流和信息共享。知名的社交網(wǎng)站如國外的Facebook、Twitter等，國內(nèi)的新浪微博、騰訊微博等。這些社交網(wǎng)絡(luò)不僅可以為人們的休閑和娛樂提供平臺，而且還可以增強人們之間的相互溝通與理解。

在社交網(wǎng)絡(luò)中，每個用戶節(jié)點相當(dāng)于一個信息頻道，可以自由發(fā)布自身信息，也可根據(jù)自身興趣關(guān)注一些感興趣的相關(guān)人物，建立起自己的社會關(guān)系。但是由于社交網(wǎng)絡(luò)往往擁有數(shù)以億計的用戶節(jié)點，當(dāng)用戶在建立自己的社會關(guān)系時，會面臨著數(shù)據(jù)過載問題，因此幫助用戶在大量的人群節(jié)點中發(fā)現(xiàn)其感興趣的人群是非常重要的，而社交網(wǎng)絡(luò)中的鏈路預(yù)測就是一個有效的工具。社交網(wǎng)絡(luò)中的鏈路預(yù)測就是根據(jù)社交網(wǎng)絡(luò)及其網(wǎng)絡(luò)用戶發(fā)布的信息，預(yù)測目標(biāo)用戶感興趣的潛在相關(guān)用戶，然后將預(yù)測的相關(guān)用戶推薦給目標(biāo)用戶。

對于社交網(wǎng)絡(luò)中存在的海量信息，其中有很多都是用戶的隱私信息，對于這些隱私信息的研究，不僅可以提高網(wǎng)絡(luò)中鏈路預(yù)測的精確度，而且還可以對用戶的個人隱私信息提出一些保護(hù)措施。文獻(xiàn)[2-4]介紹了社交網(wǎng)絡(luò)中存在的隱私信息，并通過一些方式對這些隱私信息進(jìn)行處理，運用處理后的信息提出一些用戶個人信息保護(hù)措施以保證用戶信息安全。雖然很多文獻(xiàn)都對社交網(wǎng)絡(luò)中存在著大量的用戶個人隱私信息進(jìn)行了研究，但對于社交網(wǎng)絡(luò)中的鏈路預(yù)測來說運用這些隱私信息的還相對較少。因此，本文考慮使用社交網(wǎng)絡(luò)中用戶個人的隱私信息，并對這些信息進(jìn)行處理，提出一種新的社交網(wǎng)絡(luò)的鏈路預(yù)測方法，提高鏈路預(yù)測的精確度。

2　相關(guān)工作

目前，研究網(wǎng)絡(luò)中的鏈路預(yù)測的方法有很多，文獻(xiàn)[5]綜述了從不同角度考慮網(wǎng)絡(luò)的特性而提出各種不同的鏈路預(yù)測方法，在具體研究網(wǎng)絡(luò)中的鏈路預(yù)測時，不僅要考慮網(wǎng)絡(luò)中節(jié)點的各種屬性，而且還要考慮網(wǎng)絡(luò)結(jié)構(gòu)特征，網(wǎng)絡(luò)的結(jié)構(gòu)特征一般考慮兩個方向：一是基于網(wǎng)絡(luò)的局部特征，考慮網(wǎng)絡(luò)節(jié)點的局部結(jié)構(gòu)；二是基于網(wǎng)絡(luò)的全局特征，考慮網(wǎng)絡(luò)的全局結(jié)構(gòu)。雖然網(wǎng)絡(luò)中鏈路預(yù)測的方法有很多，但大部分都是在無向網(wǎng)絡(luò)中研究的，而在現(xiàn)實的社會生活中，很多網(wǎng)絡(luò)是有向的，例如食物鏈網(wǎng)絡(luò)、雇傭關(guān)系網(wǎng)絡(luò)、微博網(wǎng)絡(luò)等，它們之間的鏈接是不對稱的，只能從一個節(jié)點指向另一個節(jié)點，對于這類有向網(wǎng)絡(luò)的鏈路預(yù)測用原來的無向網(wǎng)絡(luò)中的研究方法是不可行的。

在有向社交網(wǎng)絡(luò)的鏈路預(yù)測中，學(xué)者們對其進(jìn)行了大量的研究。文獻(xiàn)[6]介紹一些有向網(wǎng)絡(luò)中的鏈路預(yù)測方法及指標(biāo)，并比較那些知名的鏈路預(yù)測指標(biāo)及這些指標(biāo)在有向網(wǎng)絡(luò)中的適應(yīng)性，且根據(jù)現(xiàn)有的技術(shù)提出最小子圖模型的鏈路預(yù)測指標(biāo)，實驗表明該模型有較高的精確度。但對于一些社交網(wǎng)絡(luò)僅僅考慮其方向性是遠(yuǎn)遠(yuǎn)不夠的，因為網(wǎng)絡(luò)中存在很多信息，而根據(jù)信息流的傳遞進(jìn)行鏈路預(yù)測的算法也有很多，信息流的傳播使網(wǎng)絡(luò)的某些用戶有了連接，因此在有向社交網(wǎng)絡(luò)的鏈路預(yù)測算法方面考慮信息相似性也是非常有必要的。文獻(xiàn)[7]通過對網(wǎng)絡(luò)中信息流的分析，信息流會隨著時間的變化而衰減，對不考慮時間對信息流影響的基于隨機游走的PropFlow算法進(jìn)行改進(jìn)，添加信息流衰減因子，提出隨時間變化的基于隨機游走的T_Flow算法，并將這兩個算法在實際網(wǎng)絡(luò)中對比，T_Flow算法預(yù)測精確度有所提高。文獻(xiàn)[8]利用網(wǎng)絡(luò)中存在的節(jié)點信息及結(jié)構(gòu)信息，提出評價節(jié)點權(quán)威性的BenefitRank機制，并結(jié)合弱連接理論給出估計加權(quán)網(wǎng)絡(luò)節(jié)點之間未來關(guān)系相似的措施。

然而，現(xiàn)有的社交網(wǎng)絡(luò)的鏈路預(yù)測算法在對預(yù)測節(jié)點的得分計算時，大多僅僅考慮網(wǎng)絡(luò)中節(jié)點度的信息，但對于社交網(wǎng)絡(luò)，它是個人真實社會關(guān)系的完美映射，網(wǎng)絡(luò)中用戶個人還存在著大量的隱私信息，如果考慮用戶之間的隱私信息，則得到的預(yù)測結(jié)果更符合實際。本文在研究社交網(wǎng)絡(luò)中的鏈路預(yù)測問題時，考慮用戶個人存在的大量隱私信息，利用這些隱私信息并結(jié)合網(wǎng)絡(luò)中節(jié)點本身的節(jié)點度信息計算用戶之間的連邊得分，根據(jù)計算的得分對社交網(wǎng)絡(luò)進(jìn)行鏈路預(yù)測，從而提高鏈路預(yù)測準(zhǔn)確度。

3　模型

3.1繼承節(jié)點集

使用文獻(xiàn)[9]的繼承節(jié)點的尋找方法，首先找到目標(biāo)節(jié)點的相似節(jié)點集，然后根據(jù)相似節(jié)點集尋找繼承節(jié)點集。

3.1.1相似節(jié)點集

a).目標(biāo)節(jié)點直接指向的節(jié)點：

b).目標(biāo)節(jié)點直接指向的節(jié)點的一跳范圍內(nèi)所指向的節(jié)點：

c).有共同興趣的節(jié)點（即與目標(biāo)節(jié)點同時指向的節(jié)點）：

相似節(jié)點集：

如圖3-1設(shè)定目標(biāo)節(jié)點為u1，則

圖3.1　有向網(wǎng)絡(luò)

3.1.2繼承節(jié)點集

通過相似節(jié)點所指向的節(jié)點確定為目標(biāo)節(jié)點的繼承節(jié)點，定義為

如圖3-2設(shè)定u1為目標(biāo)節(jié)點，則

圖3.2　相似節(jié)點集及繼承節(jié)點集

3.2隱私信息相似性及度信息比重計算

在社交網(wǎng)絡(luò)中，首先我們將用戶的隱私信息提取出來，然后將這些信息轉(zhuǎn)換成用戶的屬性信息（背景信息、社交信息、文本信息、交互信息），并根據(jù)一定的規(guī)則將這些信息用一系列的單詞標(biāo)簽表示，根據(jù)單詞標(biāo)簽的相關(guān)程度判斷是否可以將此單詞標(biāo)簽歸為一類。

假設(shè)選取u為目標(biāo)節(jié)點，i為繼承節(jié)點集中的某一繼承節(jié)點，根據(jù)節(jié)點本身的屬性特征提取其隱私信息生成單詞標(biāo)簽，則用戶u的隱私單詞標(biāo)簽為，用戶i的隱私單詞標(biāo)簽為，同時分別提取用戶u, i周圍相似節(jié)點的隱私信息，然后從中找出與用戶u, i相同的隱私信息，并計算出這些隱私信息在相似用戶中的信息比重ω，形成向量，然后得出隱私信息的相似度。即用戶u, i的隱私信息相似度為

然后結(jié)合節(jié)點度的信息，借鑒ZTZH模型[10]中連邊連接的計算方式（即網(wǎng)絡(luò)連邊權(quán)重的多少以概率p取決于被連接節(jié)點i的度和以概率1- p取決于被連接節(jié)點i的適應(yīng)度iη，即

其中，｛l｝代表新節(jié)點n所要連接的節(jié)點的集合。）改進(jìn)兩節(jié)點連邊的得分得計算方法。兩節(jié)點連邊得分的計算以概率p取決于節(jié)點i的度的信息和以概率1- p取決于節(jié)點u, i的隱私信息，即

其中，i為繼承節(jié)點，ki為節(jié)點i的相似節(jié)點數(shù)，ω為隱私信息比重，p為參數(shù)。而繼承節(jié)點i的度信息比重計算方法為：找出節(jié)點i的所有相似節(jié)點并計數(shù)ki，同時找出節(jié)點u的所有繼承節(jié)點的所有相似節(jié)點并計數(shù)，則度信息比重為

圖3.3　隱私信息相似性計算

例如，在圖3-3中選取u1作為目標(biāo)節(jié)點，u3為繼承節(jié)點，分別提取兩節(jié)點的隱私信息并將其生成隱私單詞標(biāo)簽。然后將兩節(jié)點的每個單詞標(biāo)簽作對比，根據(jù)每個單詞標(biāo)簽在其周圍相似節(jié)點中所占的比重ω生成隱私信息比重，并計算兩節(jié)點隱私信息總體的相似性，即

并計算繼承節(jié)點u3的度以及繼承節(jié)點集的所有相似節(jié)點的度，則節(jié)點之間的得分為

3.3計算得分

根據(jù)用戶節(jié)點的隱私信息計算出兩節(jié)點的信息相似性，同時計算繼承節(jié)點度的信息，得到預(yù)測節(jié)點連邊的得分計算方法。然后計算出兩節(jié)點連邊的得分，并將這些得分進(jìn)行排序，根據(jù)分?jǐn)?shù)高低判斷兩節(jié)點是否連接。即得分計算方式如下

4　仿真分析

本文采用騰訊微博數(shù)據(jù)（2012KDD競賽數(shù)據(jù)）對提出的預(yù)測模型進(jìn)行仿真分析。為仿真方便，本文對原始數(shù)據(jù)進(jìn)行了預(yù)處理，隨機選取了8437個節(jié)點。

4.1評價指標(biāo)

本文模型的仿真結(jié)果采用常用的三種評價指標(biāo)進(jìn)行評價，即準(zhǔn)確率、召回率、F1度量來衡量該模型的優(yōu)劣。

4.2仿真結(jié)果及分析

針對考慮基于節(jié)點度信息的預(yù)測方法、基于用戶節(jié)點隱私信息的預(yù)測方法以及綜合考慮基于節(jié)點度信息和用戶節(jié)點隱私信息的預(yù)測方法3種不同的預(yù)測算法進(jìn)行仿真，仿真結(jié)果如表4-1所示：

表4-1　兩節(jié)點連邊預(yù)測結(jié)果

從表4-1中可以看出，基于節(jié)點度信息和用戶節(jié)點隱私信息的預(yù)測模型相比于僅僅基于節(jié)點度信息的預(yù)測模型以及僅僅基于用戶節(jié)點隱私信息的預(yù)測模型對預(yù)測結(jié)果的準(zhǔn)確度均有所提高。對于準(zhǔn)確率、召回率以及F1度量，基于節(jié)點度信息和用戶節(jié)點隱私信息的預(yù)測模型要比基于節(jié)點度信息的預(yù)測模型的預(yù)測結(jié)果高出了4倍左右，而與基于用戶節(jié)點隱私信息的預(yù)測模型的預(yù)測結(jié)果比較接近，這說明網(wǎng)絡(luò)中用戶的隱私信息對預(yù)測的連邊有很大的影響，體現(xiàn)出隱私信息在預(yù)測兩用戶是否發(fā)生連接有著重要的作用。從用戶的隱私信息角度來看，兩用戶的信息相似度越高，說明其感興趣的話題就越多，這兩用戶連接的可能性就越大。

表4-2　基于節(jié)點度信息和用戶節(jié)點隱私信息的預(yù)測方法與參數(shù)p的關(guān)系

從表4-2中可以看出，對于不同的參數(shù)p，預(yù)測的結(jié)果有所不同?；诠?jié)點度信息和用戶節(jié)點隱私信息的預(yù)測模型，需要合適的p值來權(quán)衡用戶節(jié)點度信息和用戶節(jié)點隱私信息哪一方面的信息對預(yù)測的結(jié)果比較重要。當(dāng)p=0.2時，模型的預(yù)測結(jié)果達(dá)到最優(yōu)。由此可以看出，用戶的節(jié)點度信息對預(yù)測的結(jié)果也有著一定的影響，這是因為用戶節(jié)點度越高，其關(guān)注的用戶就越多，則其感興趣的話題也越多，其他用戶與其發(fā)生的連接也就越高；同時該用戶的隱私信息也就越多，其他用戶的隱私信息與其信息相似度也有可能越高，這樣兩用戶發(fā)生連接的可能性就會更高。因此，綜合考慮基于節(jié)點度信息和用戶節(jié)點隱私信息的預(yù)測模型對于好友的預(yù)測有更高的預(yù)測性能。

4.3小結(jié)

本文通過對社交網(wǎng)絡(luò)中用戶節(jié)點度及用戶隱私信息的研究，提出了一種有向網(wǎng)絡(luò)中的鏈路預(yù)測算法，并將這種算法運用到微博好友預(yù)測中，更符合社交網(wǎng)絡(luò)的實際情況，取得了較好的預(yù)測結(jié)果。

參考文獻(xiàn)

[1]Linyuan Lv, Link Prediction on Complex Network, Journal of University of Electronic Science and Technology of China, Vol.35, No.5, 651-661, 2010.

[2]Acquisti A, Grossklags J, Privacy and Rationality in Decision Making.IEEE Secur Priv 26-33, 2005.

[3]Bonneau J, Anderson J, Anderson R, Stajano F, Eight Friends Are Enough: Social Graph Approximation Via Public Listings, In: Proceedings of the Second ACM EuroSys Workshop on Social Network Systems.SNS’ 09, ACM, New York, pp 13-18, 2009.

[4]Gross R, Acquisti A, Information Revelation and Privacy in Online Social Networks, In: Proceedings of the 2005 ACM Workshop on Privacy in the Electronic Society, WPES’ 05, ACM, New York, pp 71-80, 2005.Narayanan A, Shmatikov V, De-anonymizing Social Networks, In: IEEE Symposium on Security and Privacy, 2009.

[5]Zheleva E, Getoor L, To Join or not to Join: the Illusion of Privacy in Social Networks with Mixed Public and Private User Profiles, In: Proceedings of the 18th International Conference on World Wide Web, WWW’ 09, ACM, New York, pp 531-540, 2009.

[6]Lankeshwara MUNASINGHE, Ryutaro ICHISE.Link Prediction in Social Networks Using Information Flow via Active Links.The Institute of Electronics, Information and Communication Engineers.Vol.E96-D, No.7, pp 1495-1502, 2013.

[7]Zhijie Lin, Yun Xiong and Yangyong Zhu.Link prediction using BenefitRanks in weighted networks.International Conferences on Web Intelligence and Intelligent Agent Technology, pp 423-430, 2012.

[8]Yan Yu, and Xinxin Wang.Link Prediction in Directed Network and Its Application in Microblog.Hindawi Publishing Corporation Mathematical Problems in Engineering Volume 2014.

[9]Zheng D F, Trimper S, Zheng B, et al.Weighted scale-free networks with stochastic weight assignments.Phys.Rev.E, 2003, 67(4): 040102(1-4).

項目名稱

國家自然科學(xué)基金青年項目，61401015，社交網(wǎng)絡(luò)用戶行為分析及話題演化趨勢預(yù)測方法研究。

關(guān)鍵字：社交網(wǎng)絡(luò) 鏈路預(yù)測 隱私信息