章 迪，潘 理

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

0 引 言

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

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

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

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

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

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

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

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

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

中心節(jié)點(diǎn)。對(duì)于節(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á)。對(duì)于節(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。

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

1.2 社交圈模型

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

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

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

個(gè)人網(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)集合，是劃分出來的社交圈，并識(shí)別個(gè)人網(wǎng)絡(luò)中的橋梁節(jié)點(diǎn)。本文算法根據(jù)節(jié)點(diǎn)之間的相鄰關(guān)系，加入屬性內(nèi)容來判斷相鄰關(guān)系，使得節(jié)點(diǎn)之間的鄰居關(guān)系更加準(zhǔn)確，容易將同一個(gè)社交圈節(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ù)雜度，同時(shí)劃分出不同社交圈之間的橋梁節(jié)點(diǎn)，可以減少不同社交圈之間的信息傳播，有利于提高個(gè)人網(wǎng)絡(luò)的隱私安全性。

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

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

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

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

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

生成一個(gè)新的社交圈序號(hào)；

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

WHILE Q≠0 Do∶

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

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

FOR 每一個(gè)x∈R Do∶

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

THEN∶

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

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

將x添加到隊(duì)列Q中；

將y從隊(duì)列Q中移除；

ELSE

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

END FOR

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

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

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

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

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

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

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

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

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

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

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

本文實(shí)驗(yàn)主要內(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值

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

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

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

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

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

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

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

4 結(jié) 語

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