基于社交圈的信息分享策略研究*

章 迪，潘 理

（1.上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海 200240；2.上海市信息安全綜合管理技術(shù)研究重點(diǎn)實(shí)驗室，上海 200240）

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，社交網(wǎng)絡(luò)中的用戶越來越多，社交網(wǎng)絡(luò)成為人們?nèi)粘Ｉ钪斜夭豢缮俚囊徊糠帧１容^有名的社交網(wǎng)絡(luò)平臺有Facebook、Twitter、微信等。用戶使用社交網(wǎng)絡(luò)的主要目的是結(jié)識更多朋友，實(shí)現(xiàn)信息分享，提高交流的效率，這樣用戶就會在社交網(wǎng)絡(luò)中分享大量個人信息。如果這些信息被不法分子惡意傳播利用，就會使得用戶個人信息受損。比如，人們經(jīng)常會在社交網(wǎng)絡(luò)平臺上分享個人狀態(tài)、個人信息，這些敏感信息如果被惡意用戶獲得，就可能會導(dǎo)致電話詐騙、身份欺詐等各種危險。

針對社交網(wǎng)絡(luò)隱私保護(hù)問題，主要采用社交網(wǎng)絡(luò)的訪問控制技術(shù)，主要有基于屬性的訪問控制模型[1]、基于信任的訪問控制模型[2]、基于語義的訪問控制模型[3]、基于關(guān)系的訪問控制模型[4-5]和基于角色的訪問控制模型[6]。對于在保護(hù)用戶個人隱私的前提下如何分享個人信息充分使用社交網(wǎng)絡(luò)的需求，已有的方法已經(jīng)不能夠適用。個人網(wǎng)絡(luò)社交圈的劃分有：SQUICCIARINI等人采用共同興趣屬性進(jìn)行朋友圈群體的分類[7]；Hu和Yang提出了一個新型的個人網(wǎng)絡(luò)朋友圈劃分算法[8]，通過為每一條邊構(gòu)建屬性，將節(jié)點(diǎn)信息和網(wǎng)絡(luò)結(jié)構(gòu)結(jié)合在一起；YOUSHIDA提出了通過屬性圖進(jìn)行朋友圈劃分的算法[9]，屬性圖是由用戶屬性構(gòu)建的規(guī)則化的圖結(jié)構(gòu)；MACAULEY等人提出了無監(jiān)督學(xué)習(xí)算法來基于額外的用戶信息發(fā)現(xiàn)個人網(wǎng)絡(luò)中的潛在圈子[10]。當(dāng)前，已存在社交網(wǎng)絡(luò)中對隱私保護(hù)的信息分享研究有基于收益和分享自適應(yīng)信息分享策略[11-12]，即通過一條信息的具體內(nèi)容帶來的收益和風(fēng)險判斷該條信息是否分享。但是，這種方法需要消耗大量的時間，且對于社交網(wǎng)絡(luò)中大量的用戶，對所有用戶進(jìn)行逐一配置，不僅工作量巨大，而且往往達(dá)不到效果。

解決社交網(wǎng)絡(luò)中用戶的個人信息隱私安全問題，存在的困難有兩點(diǎn)：一是需要管理中心用戶的好友數(shù)量越來越多，面對大量的個人好友，如何方便進(jìn)行策略自動化配置和管理；二是如何設(shè)置合適的信息分享策略，保護(hù)用戶個人的隱私安全，同時使得用戶將信息分享給更多的人，不會因為隱私問題限制對社交網(wǎng)絡(luò)的使用。面對這些問題，本文設(shè)計了基于社交圈的信息分享策略方法，滿足社交網(wǎng)絡(luò)中用戶在分享信息時對隱私保護(hù)的需求。

本文的研究思路分為兩個部分。第一部分是基于密度聚類的社交圈劃分算法，通過將個人網(wǎng)絡(luò)中好友劃分到不同的社交圈便于好友管理，簡化信息分享時的配置。本文的社交圈劃分算法可以劃分出個人網(wǎng)絡(luò)中的特殊節(jié)點(diǎn)——橋梁節(jié)點(diǎn)。橋梁節(jié)點(diǎn)連接了各個社交圈，同時隔離社交圈之間的直接聯(lián)系，減少社交圈之間的信息傳播，提高社交圈之間的獨(dú)立性，避免社交圈之間的信息傳播對用戶造成隱私泄漏。第二部分是在社交圈劃分的基礎(chǔ)上，提出了一種信息分享策略，即選擇不同社交圈分享信息，解決用戶對分享信息和隱私安全之間的矛盾，將用戶分享信息問題轉(zhuǎn)化為數(shù)學(xué)中的0-1背包問題求解，既保障了用戶的隱私意識需求，又促進(jìn)了社交網(wǎng)絡(luò)的信息分享最大化。

1 社交圈劃分算法

1.1 基本定義

社交 網(wǎng)絡(luò)可以抽象為圖模型G=(V,E)，其中V代表用戶節(jié)點(diǎn)集合，E代表相應(yīng)的社交網(wǎng)絡(luò)關(guān)系。本文主要研究對象是社交網(wǎng)絡(luò)中的個人網(wǎng)絡(luò)（Ego Network），是社交網(wǎng)絡(luò)的子結(jié)構(gòu)。它包含一個中心節(jié)點(diǎn)、相鄰節(jié)點(diǎn)以及各個節(jié)點(diǎn)之間的連接關(guān)系。

個人網(wǎng)絡(luò)Gv=(Vv,Ev)代表節(jié)點(diǎn)v的個人網(wǎng)絡(luò)圖結(jié)構(gòu)，Vv表示節(jié)點(diǎn)v的一跳好友，Ev表示一跳好友之間的連接關(guān)系。

屬性相似度。對于節(jié)點(diǎn)v,w∈Vv，feature(v)和feature(w)分別代表節(jié)點(diǎn)v、w的屬性特征向量，用戶v、w之間的屬性相似度記為：

結(jié)構(gòu)相似度表示兩個節(jié)點(diǎn)v,w∈Vv在網(wǎng)絡(luò)結(jié)構(gòu)中的相似性，即兩個節(jié)點(diǎn)共同的鄰居數(shù)量占比，記為：

節(jié)點(diǎn)相似度。由節(jié)點(diǎn)的屬性相似度和結(jié)構(gòu)相似度通過平衡參數(shù)α組合而來，記為：

ε-鄰居。對于節(jié)點(diǎn)v∈Vv，其ε-鄰居包含與其直接相鄰節(jié)點(diǎn)相似度大于ε的節(jié)點(diǎn)集合，Γ(v)表示鄰居節(jié)點(diǎn)集合，記為：

中心節(jié)點(diǎn)。對于節(jié)點(diǎn)v∈Vv，它的ε-鄰居集合節(jié)點(diǎn)數(shù)量至少為 MinPts，記為：

直接可達(dá)。節(jié)點(diǎn)w在中心節(jié)點(diǎn)v的ε-鄰居中，則稱節(jié)點(diǎn)w由節(jié)點(diǎn)v直接可達(dá)，亦節(jié)點(diǎn)v直接可達(dá)節(jié)點(diǎn)w，記為：

間接可達(dá)。對于節(jié)點(diǎn)v和w，如果存在節(jié)點(diǎn)序列v1,…,vn∈Vv滿足v1=v,vn=w，且節(jié)點(diǎn)序列中相鄰的節(jié)點(diǎn)vi直接可達(dá)vi+1，則稱節(jié)點(diǎn)v間接可達(dá)節(jié)點(diǎn)w。

相互連通。對于節(jié)點(diǎn)v和w，如果存在一個中心節(jié)點(diǎn)u∈Vv，使得節(jié)點(diǎn)u同時間接可達(dá)節(jié)點(diǎn)v和節(jié)點(diǎn)w，則稱節(jié)點(diǎn)v和w是相互連通的。

1.2 社交圈模型

社交圈（SC）：如果一個非空子圖（SC）中的所有節(jié)點(diǎn)是相互連通的，且SC是滿足間接可達(dá)的最大子 圖，那么稱SC是一個社交圈。

社交圈是定義在參數(shù)和MinPts下的，滿足兩個條件：（1）連通性，同一個社交圈中的所有節(jié)點(diǎn)是相互連通的；（2）最大化，相互連通的節(jié)點(diǎn)都在社交圈中。通過對網(wǎng)絡(luò)中節(jié)點(diǎn)之間的間接可達(dá)關(guān)系，將同一個社交圈的節(jié)點(diǎn)全部劃分出來。

橋梁節(jié)點(diǎn)（BRIDGE）。對于節(jié)點(diǎn)v∈Vv，如果它與兩個或者兩個以上的社交圈有相互連接的邊，同時該節(jié)點(diǎn)不屬于任何一個社交圈，則該節(jié)點(diǎn)是橋梁節(jié)點(diǎn)。

個人網(wǎng)絡(luò)社交圈模型包括二部分：一是不同的社交圈SC；二是所有的橋梁節(jié)點(diǎn)BRIDGE。

1.3 基于密度聚類社交圈劃分算法分析

基于密度聚類的社交圈劃分算法（Density Based Social Circle Partition Algorithm，DBSCPA）利用不同節(jié)點(diǎn)之間的相似性度量和節(jié)點(diǎn)鄰居之間的關(guān)系，根據(jù)間接可達(dá)關(guān)系推導(dǎo)最大連接的節(jié)點(diǎn)集合，是劃分出來的社交圈，并識別個人網(wǎng)絡(luò)中的橋梁節(jié)點(diǎn)。本文算法根據(jù)節(jié)點(diǎn)之間的相鄰關(guān)系，加入屬性內(nèi)容來判斷相鄰關(guān)系，使得節(jié)點(diǎn)之間的鄰居關(guān)系更加準(zhǔn)確，容易將同一個社交圈節(jié)點(diǎn)劃分在一起。相比于文獻(xiàn)[9]基于屬性圖的方法，如果只根據(jù)屬性容易將網(wǎng)絡(luò)中結(jié)構(gòu)關(guān)系不緊密的節(jié)點(diǎn)劃分在一起，導(dǎo)致結(jié)果不準(zhǔn)確。相比于文獻(xiàn)[10]的方法，本文方法不考慮社交圈的重疊，降低了社交圈劃分的復(fù)雜度，同時劃分出不同社交圈之間的橋梁節(jié)點(diǎn)，可以減少不同社交圈之間的信息傳播，有利于提高個人網(wǎng)絡(luò)的隱私安全性。

算法過程。檢查一個未劃分節(jié)點(diǎn)是中心節(jié)點(diǎn)，從該節(jié)點(diǎn)生成一個新的社交圈，否則記為非社交圈節(jié)點(diǎn)。從該中心節(jié)點(diǎn)開始搜索所有間接可達(dá)節(jié)點(diǎn)，可以找到包含節(jié)點(diǎn)v的完整社交圈。新的社交圈ID將會賦予所有被搜索到的點(diǎn)。將節(jié)點(diǎn)v的所有ε-鄰居節(jié)點(diǎn)插入隊列中，對隊列中的每一個節(jié)點(diǎn)，計算它的直接可達(dá)節(jié)點(diǎn)，并將其中未劃分的節(jié)點(diǎn)插入隊列中，不停重復(fù)，直到隊列為空。對于非社交圈節(jié)點(diǎn)，進(jìn)一步劃分出橋梁節(jié)點(diǎn)。DBSCPA涉及3個參數(shù)——平衡參數(shù)α、相似度閾值ε和中心節(jié)點(diǎn)定義數(shù)值MinPts。其中，平衡參數(shù)α是用來調(diào)節(jié)屬性相似度和結(jié)構(gòu)相似度在整體相似度中的比例；相似度閾值ε和中心節(jié)點(diǎn)定義數(shù)值MinPts都是用來控制社交圈的規(guī)模。在后續(xù)實(shí)驗中，平衡參數(shù)α=0.5，相似度閾值ε=0.5，中心節(jié)點(diǎn)定義數(shù)值MinPts=2。基于密度聚類的社交圈劃分算法（DBSCPA）偽代碼如下：

Input：Gv=(Vv,Ev);節(jié)點(diǎn)相似度表 ; ε;MinPts

Output：社交圈SC；橋梁節(jié)點(diǎn)BRIDGE

FOR 每一個未劃分的節(jié)點(diǎn)v∈VvDo∶

IF v是中心節(jié)點(diǎn)CENTERε,MinPts(v) THEN∶

生成一個新的社交圈序號；

將節(jié)點(diǎn) x∈Neighborε(v) 全部插入到隊列Q中；

WHILE Q≠0 Do∶

令y是隊列Q中的第一個節(jié)點(diǎn)；

R = { x ∈ V | D irREACHε,MinPts(y, x )}；

FOR 每一個x∈R Do∶

IF x是未劃分節(jié)點(diǎn)或非社交圈節(jié)點(diǎn)

THEN∶

將當(dāng)前的社交圈編號賦予x；

IF x是未劃分節(jié)點(diǎn) THEN∶

將x添加到隊列Q中；

將y從隊列Q中移除；

ELSE

將v標(biāo)記為非社交圈節(jié)點(diǎn)；

END FOR

FOR 每一個非社交圈節(jié)點(diǎn)Do∶

IF? x , y ∈ Γ ( v)( x.c l usterID ≠ y.c l usterID)

THEN∶

v被劃分為BRIDGE

END FOR

Return 社交圈SC，橋梁節(jié)點(diǎn)BRIDGE

2 基于社交圈的信息分享策略

中心用戶u的個人網(wǎng)絡(luò)被劃分出數(shù)量為k的社交圈SC={SC1,…,SCk}和橋梁節(jié)點(diǎn)，其中每個社交圈對應(yīng)的用戶人數(shù)為N={n1,…,nk}。用戶分享一條信息m，用戶對該條信息的隱私泄漏容忍度為δ，并假定SCthreat群體是潛在的危險用戶。如果用戶自己的個人信息傳播到該社交圈，將會給用戶帶來潛在的危險和損失。傳播的信息越多，潛在的危險和損失越大。

用戶在分享個人信息后，不同社交圈之間會相互傳播信息，將導(dǎo)致信息流向潛在危險社交圈SCthreat。不同社交圈之間的信息傳播能力記為PBSC(SCi,SCj)，表示社交圈SCi和SCj之間的信息傳播能力。在不超過用戶隱私泄漏容忍度的前提下，最大化用戶分享的人數(shù)是要求解的問題。引入標(biāo)記變量xi，xi=0or1表示用戶是否將信息分享給社交圈SCi。當(dāng)滿足求解 a rgni*xi。將信息分享策略問題轉(zhuǎn)化為0-1背包最優(yōu)化問題：

這是一個常見的NP-Hard問題，采用動態(tài)規(guī)劃方法解決該問題。其中，PBSC(SCi,SCthreat)的計算公式為：

其中Edge_Weight(SC1,SCthreat)代表社交圈SCi和SCthreat之間相連接邊的權(quán)值之和，并將其進(jìn)行歸一化，作為兩個社交圈之間的信息傳播能力。社交圈之間連接的邊越多，信息傳播能力越強(qiáng)，連邊兩端的節(jié)點(diǎn)相似度越大，即連邊的權(quán)值越大，信息傳播能力越強(qiáng)。

通過求解背包問題，即使得目標(biāo)函數(shù)達(dá)到最大的解向量X=(x1,…,xk)，求解每一個社交圈標(biāo)記變量的值，確定可以分享信息的社交圈。用戶可以將信息分享到這些社交圈中，不會對隱私安全造成危險，同時分享信息的人數(shù)也是最多的。可見，在保護(hù)隱私安全的前提下，最大化地利用社交網(wǎng)絡(luò)，使用戶能在社交網(wǎng)絡(luò)中與更多的人分享信息。

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

本文實(shí)驗采用的是SNAP數(shù)據(jù)集，從文獻(xiàn)[10]獲得。本文實(shí)驗利用的是Facebook的個人網(wǎng)絡(luò)數(shù)據(jù)，包含用戶節(jié)點(diǎn)的各種屬性和網(wǎng)絡(luò)用戶之間的連邊關(guān)系。本文實(shí)驗的實(shí)驗環(huán)境是Intel Corei7-6700 3.4G處理器，16 GB內(nèi)存。

3.1 社交圈劃分實(shí)驗

本實(shí)驗使用平衡誤差率（Balanced Error Rate，BER）[10]作為評估指標(biāo)， S C = { S C1, … ,S Ck}代表預(yù)測社交圈集合，SC = { S C1, … ,S Ck}代表真實(shí)社交圈集合。

下面是平衡誤差率（BER）的公式：

實(shí)驗評估時，因為真實(shí)與預(yù)測社交圈的數(shù)量差異，令f是預(yù)測社交圈集合SC到真實(shí)社交圈集合的部分映射。預(yù)測與真實(shí)社交圈集合的1-BER值越大，則算法效果越好，計算如下：

本文實(shí)驗主要內(nèi)容比較了McAuley等人的概率模型（Probability Based Social Algorithm, PBSA）[10]、Yoshida的低秩嵌入模型（Low Rank Embedding Algorithm，LREA）[9]與本文的社交圈劃分算法（DBSCPA）。如表1所示，本文社交圈劃分算法的1-BER值為0.78，相比低秩嵌入算法的0.59要高出很多，比概率模型算法的0.83差一點(diǎn)。

表1 三種算法的1-BER值

本文社交圈劃分算法相對于當(dāng)下比較準(zhǔn)確的概率模型算法，在精確度方面比較接近，比其他的算法要優(yōu)越。但是，本文算法還可以發(fā)現(xiàn)網(wǎng)絡(luò)中扮演特殊角色的橋梁節(jié)點(diǎn)。正是由于識別了這些節(jié)點(diǎn)降低了精確度。然而，相對于精確度的損失，識別出這些節(jié)點(diǎn)的作用和意義更大。

3.2 基于社交圈的信息分享策略實(shí)驗

實(shí)驗的評價標(biāo)準(zhǔn)是在相同隱私泄漏容忍度（Tolerance of Privacy Leakage）下，信息分享授權(quán)好友占所有好友的比例。隱私泄漏容忍度指用戶對該條信息泄漏給自己帶來的損失所能容忍的程度。隱私泄漏容忍度越大，表示該條信息越不重要，對用戶可能造成的損失越小，能夠分享的人越多。實(shí)驗?zāi)康氖球炞C本文提出了信息分享策略的可行性，同時驗證本文社交圈劃分算法比其他劃分算法在此信息分享策略上面的優(yōu)勢。

假定中心用戶發(fā)布了9條隱私泄漏容忍度不同的消息m1,…,m9。這9條信息對應(yīng)中心用戶的隱私泄漏容忍度分別是δ1=0.1,…,δ9=0.9。根據(jù)不同的隱私容忍度做了9次對比實(shí)驗。為了便于實(shí)驗比較，假定對于每一條信息，中心用戶認(rèn)定的威脅用戶都是同一個社交圈。

實(shí)驗將本文的社交圈劃分算法和概率模型、低秩嵌入算法進(jìn)行對比。考慮這3種不同的社交圈劃分算法對用戶信息分享策略的影響，結(jié)果如圖1所示。授權(quán)節(jié)點(diǎn)所占的比例隨著隱私泄漏容忍度不斷增大，即信息包含隱私內(nèi)容越少，可分享的人數(shù)越多，說明本文信息分享策略是可行的。同時，概率模型和低秩嵌入模型的用戶所授權(quán)人數(shù)占比都較低。本文的算法劃分的社交圈相比其他兩種算法，在同等隱私泄漏容忍度的情況下，授權(quán)節(jié)點(diǎn)占所有好友節(jié)點(diǎn)的比例要高，說明本文的社交圈劃分算法在信息分享策略方面相比于其他劃分算法具有較高的優(yōu)勢，更能提高社交網(wǎng)絡(luò)的可用性。

圖1 信息分享策略授權(quán)節(jié)點(diǎn)占比

本文社交圈劃分算法將橋梁節(jié)點(diǎn)單獨(dú)劃分出來，而不是將其劃分在社交圈中，使得不同社交圈之間信息傳播變得困難，提高了各個社交圈之間的獨(dú)立性，減少了信息傳播。其他算法中，社交圈與危險社交圈之間關(guān)系緊密，信息傳播較多，導(dǎo)致很多用戶無法授權(quán)，說明本文的社交圈劃分算法有利于減少不同社交圈之間的信息傳播，能夠在保護(hù)用戶隱私的情況下，最大化分享人數(shù)，提高社交網(wǎng)絡(luò)的可用性。

4 結(jié) 語

提出了個人網(wǎng)絡(luò)基于密度聚類的社交圈劃分算法，能夠有效識別中心用戶好友所屬的不同社交圈，并識別出其中具有特殊角色的橋梁節(jié)點(diǎn)。針對社交網(wǎng)絡(luò)中信息分享問題，本文提出了基于社交圈劃分的隱私信息分享策略，將其轉(zhuǎn)化為數(shù)學(xué)問題中的0-1背包問題。在保護(hù)用戶隱私的前提下，選取特定的好友分享信息，使得能夠分享信息的好友數(shù)量最大。最后，通過實(shí)驗驗證本文社交圈劃分算法和信息分享策略的有效性。下一步將考慮有向網(wǎng)絡(luò)以及關(guān)于信息內(nèi)容的分析，以期完善信息分享策略。