基于節點特征的不確定圖社交網絡隱私保護方法

顏 軍 胡 靜 溫 閣 田堉攀

1(商洛學院數計學院 陜西商洛 726000) 2 (陜西師范大學計算機學院 西安 710119) (yanrongjunde@snnu.edu.cn)

隨著互聯網技術的日益普及,互聯網應用從深度和廣度上不斷擴展,現在基于互聯網的辦公、娛樂、購物、教育等活動已經深入到人們日常生活中.互聯網不僅僅提高了人們的生活質量和工作效率,更重要的是改變了人們的思維方式.

中國互聯網絡信息中心(China Internet Network Information Center) 2018年發布了《第41次中國互聯網絡發展狀況統計報告》，截至 2017 年 12 月,我國網民規模達到 7.72 億,普及率達到55.8%.當前互聯網手機網民占比達 97.5%,截至 2017 年 12 月我國手機網民規模達 7.53 億[1].這些數據顯示當前移動互聯網占據了互聯網的主導地位.

伴隨著移動互聯網的發展和普及,社交網絡與人們日常生活越來越緊密.社交網絡也就是網絡+社交,它涵蓋以人們社交為核心的所有網絡服務形式.通過社交網絡把人們連接起來,從而形成具有某一特點的團體,最終社交網絡逐漸成為一個人們社交的工具.截至2017年6月,中國網絡用戶使用率排名前3的社交應用均屬于綜合類社交應用.微信朋友圈、QQ空間用戶使用率分別為84.3%和65.8%；微博用戶使用率達38.7%[1].2018年3月5日,在十三屆全國人大一次會議首場“代表通道”集中采訪中,騰訊公司董事會主席兼首席執行官馬化騰在接受記者提問時透露,在剛剛過去的2018年春節,微信和WeChat的合并月活躍賬戶數超過10億.據美國市場研究公司eMarketer估計,2017年全球有13的人正在使用社交網絡,總數達到了驚人的24.8億[2].

有了社交網絡這個平臺,越來越多的社交網絡用戶將個人相關信息上傳到個人空間,朋友們之間可以分享這些信息,以了解彼此的生活狀況.隨著社交網絡與人們的日常生活密切相關,基于社交網絡的移動支付已經成為一種主要的交易方式.在中國,基于微信的移動支付已經成為一種基本的交易方式.當人們在社交網絡上獲得樂趣時，當通過社交網絡享受各種便利時,用戶大量與隱私信息密切相關的數據都保留在了網絡.

據搜狐科技報道,暗網供應商 “雙旗(DoubleFlag)”利用黑客技術,竊取了數家中國互聯網巨頭的大量數據.這些數據屬于以下公司：網易及其下屬的126.com，163.com和Yeah.net；擁有QQ.com的騰訊控股.在2016年十大數據泄露事件中社交網絡成重災區[3].當大量用戶在社交網絡上的信息被發布,而且這些信息包括了網上交易、個人信息等敏感信息,如果其他非法用戶對這些數據進行整理、挖掘、分析，竊取用戶的隱私信息，從而用戶的隱私會受到威脅.因此，如果對社交網絡的數據實施隱私保護后再發布,惡意用戶將不能挖掘到用戶的隱私信息,極大地限制了利用隱私信息進行的非法活動.

當前對于社交網絡的隱私保護顯然存在嚴重的不足,因此社交網絡的隱私保護研究越來越受到關注[4].與傳統關系型數據的隱私保護方法不同,社交網絡的隱私保護不僅要保護每個社交網絡個體的屬性,又要保護個體間的關系.為此將社交網絡抽象成圖,用節點表示社交網絡的個體,個體之間的關系用邊來表示,個體間關系的緊密程度用對邊進行加權重來表示[5].當社交網絡被抽象為圖結構后,可以通過對圖結構的隱私保護來實現社交網絡的隱私保護.

在社交網絡隱私保護的圖修改方法中,不確定圖是一種有效的保護方法.與基本的不確定圖方法不同,本文提出了基于節點特征的不確定圖隱私保護方法.通過實驗證實,該方法不僅能夠實現社交網絡的隱私保護,而且具有較好的數據效用.

1 相關工作

目前,在社交網絡隱私保護中圖修改方法是一重要方法,包括點邊修改、聚類[6]、不確定圖.點邊修改方法分為隨機修改[7-8]和限定修改[9-10]2種方法.

與常用的圖修改方法相比較,不確定圖方法是當前一種新的隱私保護方法.不確定圖方法的主要原理是將不確定性注入到社交網絡圖的邊中,發布經混淆后的不確定圖來達到隱私保護目的.通過為圖中的邊分配概率值,該方法既能實現隱私保護,又能對原圖數據改變較小,保持了較高的原圖數據的效用.

Boldi等人[11]首次提出了(k,ε)混淆算法,該方法能夠抗擊對頂點身份攻擊,而且能滿足圖結構數據的最小化失真;文獻[12]指出，Mittal等人利用隨機游走的方法生成不確定圖,得到的不確定圖能夠防止基于鏈接攻擊;為了提高不確定圖中邊的概率分配的效率,Nguyen等人[13]提出了基于最大化方差的方法來提高數據效用;Nguyen等人[14]將鄰接矩陣UAM引入到方差最大化算法中,提出了不確定方法的通用匿名模型.

然而真實的社交網絡是一個復雜網絡,而復雜網絡中各個節點在網絡中位置不同、連接關系不同、在網絡動態變化時相互影響的程度不同[15],因此需要考慮網絡結構中節點的特征以實現更有效的隱私保護.為此本文的方法通過對網絡特征的分析,確定網絡中關鍵位置的節點,結合不確定圖方法實現基于重要節點的隱私保護.

2 基礎知識

在本文中,我們將社交網絡抽象為一個無向無權重的簡單圖G=(V,E),V表示網絡所有節點的集合,E表示網絡所有邊的集合,我們用(i,j)表示節點Vi到Vj的邊,DVi表示節點Vi的度數.

2.1 不確定圖

定義1. 不確定圖.

給定一個圖G={V,E},如果映射p:Vp→[0,1]是邊集合中每條邊存在的概率函數,那么圖G′={V,Ep}是關于圖G={V,E}的不確定圖,其中Vp表示集合V中所有可能的頂點對,即Vp={(i,j)|1≤i≤j≤n}.

2.2 網絡節點的中心性

中心性定義了網絡中一個節點的重要性.在社交網絡中,也就是誰是中心角色.度中心性(degree centrality)描述了節點在社交網絡的重要程度.

定義2. 在無向圖中,節點Vi的度中心性是：CD(i)=DVi=∑aij,其中當節點i與節點j連接時,aij=1.

3 方法設計

社交網絡中節點特征對于理解和分析網絡拓撲結構具有重要的作用.節點中心性是一種常用度量節點特征的方法,節點中心性的度量值越大,表示該節點在網絡中影響力也越高.在社交網絡的隱私保護中,這些重要的網絡節點也應該成為隱私保護的重點,因此,我們提出了基于網絡節點特征的不確定圖隱私保護方法，如圖1所示：

圖1 基于節點特征的不確定圖隱私保護方法模型

3.1 模型設計

該方法首先分析社交網絡的節點特征,計算所有節點度中心性的度量值,根據度量值的大小進行節點排序,然后選擇出度量值大的節點,將這些節點作為網絡的重要節點.以重要節點為核心,在網絡中通過邊修改方法對網絡進行修改,對于修改后的網絡,給選擇的邊賦概率值,最終得到不確定圖.

3.2 算法設計

算法1. 重要節點選擇算法.

輸入：原圖G={V,E}、節點集合V、邊數集合E.

輸出:重要節點集合VH.

① 計算所有節點的度中心性的數值;

② 節點根據數值排序;

③ 選取前10%的節點并計算所有節點的度數和;

④ 判斷度數和是否大于社交網絡邊數和的80%;

⑤ 如果滿足條件,則輸出重要節點集合VH;

⑥ 如果不滿足條件,則返回③，再增加選取的節點,繼續判斷.

算法2. 不確定圖生成算法.

輸入：原圖G={V,E}、節點集合V、邊數集合E、重要節點集合VH.

輸出:不確定圖G′={V,EP}.

① 任選重要節點集合中一節點;

② 以該節點為中心,選取該節點的所有相鄰節點;

③ 判斷相鄰節點是否相連,如果沒相連則2點間加邊;

④ 選取加邊構成的所有三角形;

⑤ 選擇出沒有公共邊的三角形;

⑥ 在該三角形中每條邊賦概率值;

⑦ 循環執行以上步驟,對所有重要節點完成操作;

⑧ 得到不確定圖G′.

4 實驗分析

4.1 實驗數據集

實驗中的數據集有2種：一種為合成的數據集；一種為真實數據集.合成數據集分別為擁有300和600個節點,連接概率為0.5的隨機網絡圖,進行10次實驗操作后取平均值.真實數據集是karate和dolphin俱樂部數據集.

4.2 隱私保護度量

依據香農定律,信息熵值的大小反映了系統不確定性的大小.當我們將社交網絡圖轉換為不確定圖時,由于不確定圖的邊具有很強的不確定性,因此很難從不確定圖找出原圖.為了度量隱私保護的效果,我們引入了邊熵,使用邊熵來衡量不確定圖的不確定性,即不確定圖的隱私保護程度.

不確定圖的邊熵定義如以下公式所示：

Ente是不確定圖的邊熵值,該數值越大,表示不確定圖的不確定性越大,同時對應隱私保護方法的隱私保護效果越好.

4.3 數據效用度量

NE表示圖中邊的個數,AD表示圖中節點的平均度,DV表示圖中節點的度方差,NE′表示不確定圖中邊的個數,AD′表示不確定圖中節點的平均度.

在社交網絡中,我們用d1,d2,…,dv來表示社交網絡中節點度的序列.不確定圖中節點的度等于節點的期望度,即任意的節點v∈V,節點v的期望度是與它相連的邊的概率之和.

4.4 結果分析

基于節點特征的不確定圖方法在生成不確定圖的過程中,先選擇重要節點,以這些重要節點為核心進行鄰接點加邊,然后再對篩選得到的三角形邊賦概率值.m為生成不確定圖的過程中總共添加的邊數,c為調節加邊數的因子,實際添加的邊數為m·c.在表1中,添加的邊數增加,生成的不確定圖的邊熵值不斷增長,這說明達到的隱私保護效果越來越好,同時證明了該方法能夠實現隱私保護.

表1 基于節點特征不確定圖方法中邊熵變化情況

為了直觀地衡量隱私保護的效果,我們將本文中的方法與 (k,ε)混淆算法進行了對比,表2為(k,ε)混淆算法中邊熵的變化情況.主要參數即混淆級別k的取值分別為10和20,其他參數分別為:ε=0.1,e=1,q=0.01.

表2 (k,ε)-混淆算法中邊熵變化情況

通過表1可知本文的方法能夠可以達到較好的隱私保護效果.對比表1和表2的隱私保護效果度量數值,當網絡較小時,本文算法的保護強度優于(k,ε)混淆算法.隨著網絡規模增大,(k,ε)混淆算法優于本文算法.

在表3中,將基于節點特征的不確定圖方法得到的不確定圖與原圖比較,度量指標NE與NE′、AD與AD′之間數值變化較小,這表明由于對原圖修改較少，該方法的數據效用性較好.與原圖對比,在不確定圖中度量指標DV的數值明顯增大,這說明在生成不確定圖之后節點的度發生了變化.表4記錄了不同k值的(k,ε)混淆算法的數據效用度量值.比較表3和表4的數據效用度量數值,表4中的數據效用度量指標與原圖相比變化較大，這表明基于節點特征的不確定圖方法的數據效用優于(k,ε)混淆算法.

表3 原始圖與本文方法生成的不確定圖的數據

表4 (k,ε) -混淆算法中不同k值的數據效用性對比

5 結論與展望

本文方法在實現隱私保護時,通過節點的度中心性選擇出重要節點,以這些重要節點為核心,結合不確定圖方法實現了社交網絡的隱私保護.經過各種數據集的實驗驗證,基于節點特征的不確定圖方法不僅能夠實現社交網絡隱私保護,而且與(k,ε)混淆算法相比具有較好的數據效用.

雖然本文方法實現了社交網絡的隱私保護，但還需要在保持數據效用的前提下,研究進一步提高隱私保護的效果.

[1]中國互聯網信息中心. 第41次《中國互聯網絡發展狀況統計報告》發布[EBOL]. [2018-03-20]. http:www.cnnic.net.cngywmxwzxrdxw201801t20180131_70188.htm

[2]eMarketer. 2017年全球社交網絡用戶達24.8億[EBOL]. [2018-03-20]. http:www.199it.comarchives678247.html

[3]Hely. 2016年十大數據泄露事件: 社交網絡成泄露重災區[EBOL]. [2018-03-20]. http:www.raincent.comcontent-10-8087-2.html

[4]劉向宇, 王斌, 楊曉春. 社會網絡數據發布隱私保護技術綜述[J]. 軟件學報, 2014, 25(3): 576-590

[5]Casas-Roma J, Herrera-Joancomartí J, Torra V. A survey of graph modification techniques for privacy-preserving on networks[J]. Artificial Intelligence Review, 2017, 47(3): 341-366

[6]Campan A, Truta T M. Data and structuralk-anonymity in social networks[C]Proc of Privacy, Security, and Trust in KDD. Berlin: Springer, 2009: 33-54

[7]Ying X, Wu X. Randomizing social networks: A spectrum preserving approach[C]Proc of the Data Mining, Society for Industrial and Applied Mathematics. Philadelphia: SIAM, 2008: 739-750

[8]Ying X, Pan K, Wu X, et al. Comparisons of rando-mization andk-degree anonymization schemes for privacy preserving social network publishing[C]Proc of the 3rd Workshop on Social Network Mining and Analysis. New York: ACM, 2009: 1-10

[9]Zou L, Chen L, ?zsu M T. K-automorphism: A general framework for privacy preserving network publication[J]. Proceedings of the VLDB Endowment, 2009, 2(1): 946-957

[10]Casas-Roma J, Herrera-Joancomartí J, Torra V.k-Degree anonymity and edge selection: Improving data utility in large networks [J]. Knowledge and Information Systems, 2017, 50(2): 447-474

[11]Boldi P, Bonchi F, Gionis A, et al. Injecting uncertainty in graphs for identity obfuscation[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1376-1387

[12]Nguyen H H, Imine A, Rusinowitch M. A maximum variance approach for graph anonymization[C]Proc of Int Symp on Foundations and Practice of Security. Berlin: Springer, 2014: 49-64

[13]Nguyen H H, Imine A, Rusinowitch M. Anonymizing social graphs via uncertainty semantics[C]Proc of the 10th ACM Symp on Information, Computer and Communi-cations Security. New York: ACM, 2015: 495-506

[14]Zhang Xiaohang. Identifying influential nodes in complex networks with community structure[J]. Knowledge-Based Systems, 2013, 42(2): 74-84

[15]Liu Y, Tang M, Zhou T, et al. Identitfy influential spreaders in complex networks, the role of neighborhood[J]. Physica a Statistical Mechanics & Its Applications, 2016 (3): 289-298