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

章 迪，潘 理

（1.上海交通大學 電子信息與電氣工程學院，上海 200240；2.上海市信息安全綜合管理技術研究重點實驗室，上海 200240）

0 引 言

隨著互聯網技術的不斷發展，社交網絡中的用戶越來越多，社交網絡成為人們日常生活中必不可少的一部分。比較有名的社交網絡平臺有Facebook、Twitter、微信等。用戶使用社交網絡的主要目的是結識更多朋友，實現信息分享，提高交流的效率，這樣用戶就會在社交網絡中分享大量個人信息。如果這些信息被不法分子惡意傳播利用，就會使得用戶個人信息受損。比如，人們經常會在社交網絡平臺上分享個人狀態、個人信息，這些敏感信息如果被惡意用戶獲得，就可能會導致電話詐騙、身份欺詐等各種危險。

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

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

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

1 社交圈劃分算法

1.1 基本定義

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

個人網絡Gv=(Vv,Ev)代表節點v的個人網絡圖結構，Vv表示節點v的一跳好友，Ev表示一跳好友之間的連接關系。

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

結構相似度表示兩個節點v,w∈Vv在網絡結構中的相似性，即兩個節點共同的鄰居數量占比，記為：

節點相似度。由節點的屬性相似度和結構相似度通過平衡參數α組合而來，記為：

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

中心節點。對于節點v∈Vv，它的ε-鄰居集合節點數量至少為 MinPts，記為：

直接可達。節點w在中心節點v的ε-鄰居中，則稱節點w由節點v直接可達，亦節點v直接可達節點w，記為：

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

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

1.2 社交圈模型

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

社交圈是定義在參數和MinPts下的，滿足兩個條件：（1）連通性，同一個社交圈中的所有節點是相互連通的；（2）最大化，相互連通的節點都在社交圈中。通過對網絡中節點之間的間接可達關系，將同一個社交圈的節點全部劃分出來。

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

個人網絡社交圈模型包括二部分：一是不同的社交圈SC；二是所有的橋梁節點BRIDGE。

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

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

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

Input：Gv=(Vv,Ev);節點相似度表 ; ε;MinPts

Output：社交圈SC；橋梁節點BRIDGE

FOR 每一個未劃分的節點v∈VvDo∶

IF v是中心節點CENTERε,MinPts(v) THEN∶

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

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

WHILE Q≠0 Do∶

令y是隊列Q中的第一個節點；

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

FOR 每一個x∈R Do∶

IF x是未劃分節點或非社交圈節點

THEN∶

將當前的社交圈編號賦予x；

IF x是未劃分節點 THEN∶

將x添加到隊列Q中；

將y從隊列Q中移除；

ELSE

將v標記為非社交圈節點；

END FOR

FOR 每一個非社交圈節點Do∶

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

THEN∶

v被劃分為BRIDGE

END FOR

Return 社交圈SC，橋梁節點BRIDGE

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

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

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

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

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

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

3 實驗與結果分析

本文實驗采用的是SNAP數據集，從文獻[10]獲得。本文實驗利用的是Facebook的個人網絡數據，包含用戶節點的各種屬性和網絡用戶之間的連邊關系。本文實驗的實驗環境是Intel Corei7-6700 3.4G處理器，16 GB內存。

3.1 社交圈劃分實驗

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

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

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

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

表1 三種算法的1-BER值

本文社交圈劃分算法相對于當下比較準確的概率模型算法，在精確度方面比較接近，比其他的算法要優越。但是，本文算法還可以發現網絡中扮演特殊角色的橋梁節點。正是由于識別了這些節點降低了精確度。然而，相對于精確度的損失，識別出這些節點的作用和意義更大。

3.2 基于社交圈的信息分享策略實驗

實驗的評價標準是在相同隱私泄漏容忍度（Tolerance of Privacy Leakage）下，信息分享授權好友占所有好友的比例。隱私泄漏容忍度指用戶對該條信息泄漏給自己帶來的損失所能容忍的程度。隱私泄漏容忍度越大，表示該條信息越不重要，對用戶可能造成的損失越小，能夠分享的人越多。實驗目的是驗證本文提出了信息分享策略的可行性，同時驗證本文社交圈劃分算法比其他劃分算法在此信息分享策略上面的優勢。

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

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

圖1 信息分享策略授權節點占比

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

4 結 語

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