社交網絡中基于用戶隱私信息的鏈路預測

張長倫 趙意北京建筑大學

?

社交網絡中基于用戶隱私信息的鏈路預測

張長倫 趙意
北京建筑大學

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

1　引言

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

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

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

2　相關工作

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

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

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

3　模型

3.1繼承節點集

使用文獻[9]的繼承節點的尋找方法，首先找到目標節點的相似節點集，然后根據相似節點集尋找繼承節點集。

3.1.1相似節點集

a).目標節點直接指向的節點：

b).目標節點直接指向的節點的一跳范圍內所指向的節點：

c).有共同興趣的節點（即與目標節點同時指向的節點）：

相似節點集：

如圖3-1設定目標節點為u1，則

圖3.1　有向網絡

3.1.2繼承節點集

通過相似節點所指向的節點確定為目標節點的繼承節點，定義為

如圖3-2設定u1為目標節點，則

圖3.2　相似節點集及繼承節點集

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

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

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

然后結合節點度的信息，借鑒ZTZH模型[10]中連邊連接的計算方式（即網絡連邊權重的多少以概率p取決于被連接節點i的度和以概率1- p取決于被連接節點i的適應度iη，即

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

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

圖3.3　隱私信息相似性計算

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

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

3.3計算得分

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

4　仿真分析

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

4.1評價指標

本文模型的仿真結果采用常用的三種評價指標進行評價，即準確率、召回率、F1度量來衡量該模型的優劣。

4.2仿真結果及分析

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

表4-1　兩節點連邊預測結果

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

表4-2　基于節點度信息和用戶節點隱私信息的預測方法與參數p的關系

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

4.3小結

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

參考文獻

[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).

項目名稱

國家自然科學基金青年項目，61401015，社交網絡用戶行為分析及話題演化趨勢預測方法研究。

關鍵字：社交網絡 鏈路預測 隱私信息