基于節(jié)點(diǎn)特征的不確定圖社交網(wǎng)絡(luò)隱私保護(hù)方法

顏 軍 胡 靜 溫 閣 田堉攀

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

隨著互聯(lián)網(wǎng)技術(shù)的日益普及,互聯(lián)網(wǎng)應(yīng)用從深度和廣度上不斷擴(kuò)展,現(xiàn)在基于互聯(lián)網(wǎng)的辦公、娛樂、購物、教育等活動已經(jīng)深入到人們?nèi)粘Ｉ钪?互聯(lián)網(wǎng)不僅僅提高了人們的生活質(zhì)量和工作效率,更重要的是改變了人們的思維方式.

中國互聯(lián)網(wǎng)絡(luò)信息中心(China Internet Network Information Center) 2018年發(fā)布了《第41次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告》，截至 2017 年 12 月,我國網(wǎng)民規(guī)模達(dá)到 7.72 億,普及率達(dá)到55.8%.當(dāng)前互聯(lián)網(wǎng)手機(jī)網(wǎng)民占比達(dá) 97.5%,截至 2017 年 12 月我國手機(jī)網(wǎng)民規(guī)模達(dá) 7.53 億[1].這些數(shù)據(jù)顯示當(dāng)前移動互聯(lián)網(wǎng)占據(jù)了互聯(lián)網(wǎng)的主導(dǎo)地位.

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

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

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

當(dāng)前對于社交網(wǎng)絡(luò)的隱私保護(hù)顯然存在嚴(yán)重的不足,因此社交網(wǎng)絡(luò)的隱私保護(hù)研究越來越受到關(guān)注[4].與傳統(tǒng)關(guān)系型數(shù)據(jù)的隱私保護(hù)方法不同,社交網(wǎng)絡(luò)的隱私保護(hù)不僅要保護(hù)每個社交網(wǎng)絡(luò)個體的屬性,又要保護(hù)個體間的關(guān)系.為此將社交網(wǎng)絡(luò)抽象成圖,用節(jié)點(diǎn)表示社交網(wǎng)絡(luò)的個體,個體之間的關(guān)系用邊來表示,個體間關(guān)系的緊密程度用對邊進(jìn)行加權(quán)重來表示[5].當(dāng)社交網(wǎng)絡(luò)被抽象為圖結(jié)構(gòu)后,可以通過對圖結(jié)構(gòu)的隱私保護(hù)來實(shí)現(xiàn)社交網(wǎng)絡(luò)的隱私保護(hù).

在社交網(wǎng)絡(luò)隱私保護(hù)的圖修改方法中,不確定圖是一種有效的保護(hù)方法.與基本的不確定圖方法不同,本文提出了基于節(jié)點(diǎn)特征的不確定圖隱私保護(hù)方法.通過實(shí)驗(yàn)證實(shí),該方法不僅能夠?qū)崿F(xiàn)社交網(wǎng)絡(luò)的隱私保護(hù),而且具有較好的數(shù)據(jù)效用.

1 相關(guān)工作

目前,在社交網(wǎng)絡(luò)隱私保護(hù)中圖修改方法是一重要方法,包括點(diǎn)邊修改、聚類[6]、不確定圖.點(diǎn)邊修改方法分為隨機(jī)修改[7-8]和限定修改[9-10]2種方法.

與常用的圖修改方法相比較,不確定圖方法是當(dāng)前一種新的隱私保護(hù)方法.不確定圖方法的主要原理是將不確定性注入到社交網(wǎng)絡(luò)圖的邊中,發(fā)布經(jīng)混淆后的不確定圖來達(dá)到隱私保護(hù)目的.通過為圖中的邊分配概率值,該方法既能實(shí)現(xiàn)隱私保護(hù),又能對原圖數(shù)據(jù)改變較小,保持了較高的原圖數(shù)據(jù)的效用.

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

然而真實(shí)的社交網(wǎng)絡(luò)是一個復(fù)雜網(wǎng)絡(luò),而復(fù)雜網(wǎng)絡(luò)中各個節(jié)點(diǎn)在網(wǎng)絡(luò)中位置不同、連接關(guān)系不同、在網(wǎng)絡(luò)動態(tài)變化時相互影響的程度不同[15],因此需要考慮網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點(diǎn)的特征以實(shí)現(xiàn)更有效的隱私保護(hù).為此本文的方法通過對網(wǎng)絡(luò)特征的分析,確定網(wǎng)絡(luò)中關(guān)鍵位置的節(jié)點(diǎn),結(jié)合不確定圖方法實(shí)現(xiàn)基于重要節(jié)點(diǎn)的隱私保護(hù).

2 基礎(chǔ)知識

在本文中,我們將社交網(wǎng)絡(luò)抽象為一個無向無權(quán)重的簡單圖G=(V,E),V表示網(wǎng)絡(luò)所有節(jié)點(diǎn)的集合,E表示網(wǎng)絡(luò)所有邊的集合,我們用(i,j)表示節(jié)點(diǎn)Vi到Vj的邊,DVi表示節(jié)點(diǎn)Vi的度數(shù).

2.1 不確定圖

定義1. 不確定圖.

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

2.2 網(wǎng)絡(luò)節(jié)點(diǎn)的中心性

中心性定義了網(wǎng)絡(luò)中一個節(jié)點(diǎn)的重要性.在社交網(wǎng)絡(luò)中,也就是誰是中心角色.度中心性(degree centrality)描述了節(jié)點(diǎn)在社交網(wǎng)絡(luò)的重要程度.

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

3 方法設(shè)計

社交網(wǎng)絡(luò)中節(jié)點(diǎn)特征對于理解和分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有重要的作用.節(jié)點(diǎn)中心性是一種常用度量節(jié)點(diǎn)特征的方法,節(jié)點(diǎn)中心性的度量值越大,表示該節(jié)點(diǎn)在網(wǎng)絡(luò)中影響力也越高.在社交網(wǎng)絡(luò)的隱私保護(hù)中,這些重要的網(wǎng)絡(luò)節(jié)點(diǎn)也應(yīng)該成為隱私保護(hù)的重點(diǎn),因此,我們提出了基于網(wǎng)絡(luò)節(jié)點(diǎn)特征的不確定圖隱私保護(hù)方法，如圖1所示：

圖1 基于節(jié)點(diǎn)特征的不確定圖隱私保護(hù)方法模型

3.1 模型設(shè)計

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

3.2 算法設(shè)計

算法1. 重要節(jié)點(diǎn)選擇算法.

輸入：原圖G={V,E}、節(jié)點(diǎn)集合V、邊數(shù)集合E.

輸出:重要節(jié)點(diǎn)集合VH.

① 計算所有節(jié)點(diǎn)的度中心性的數(shù)值;

② 節(jié)點(diǎn)根據(jù)數(shù)值排序;

③ 選取前10%的節(jié)點(diǎn)并計算所有節(jié)點(diǎn)的度數(shù)和;

④ 判斷度數(shù)和是否大于社交網(wǎng)絡(luò)邊數(shù)和的80%;

⑤ 如果滿足條件,則輸出重要節(jié)點(diǎn)集合VH;

⑥ 如果不滿足條件,則返回③，再增加選取的節(jié)點(diǎn),繼續(xù)判斷.

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

輸入：原圖G={V,E}、節(jié)點(diǎn)集合V、邊數(shù)集合E、重要節(jié)點(diǎn)集合VH.

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

① 任選重要節(jié)點(diǎn)集合中一節(jié)點(diǎn);

② 以該節(jié)點(diǎn)為中心,選取該節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn);

③ 判斷相鄰節(jié)點(diǎn)是否相連,如果沒相連則2點(diǎn)間加邊;

④ 選取加邊構(gòu)成的所有三角形;

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

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

⑦ 循環(huán)執(zhí)行以上步驟,對所有重要節(jié)點(diǎn)完成操作;

⑧ 得到不確定圖G′.

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)中的數(shù)據(jù)集有2種：一種為合成的數(shù)據(jù)集；一種為真實(shí)數(shù)據(jù)集.合成數(shù)據(jù)集分別為擁有300和600個節(jié)點(diǎn),連接概率為0.5的隨機(jī)網(wǎng)絡(luò)圖,進(jìn)行10次實(shí)驗(yàn)操作后取平均值.真實(shí)數(shù)據(jù)集是karate和dolphin俱樂部數(shù)據(jù)集.

4.2 隱私保護(hù)度量

依據(jù)香農(nóng)定律,信息熵值的大小反映了系統(tǒng)不確定性的大小.當(dāng)我們將社交網(wǎng)絡(luò)圖轉(zhuǎn)換為不確定圖時,由于不確定圖的邊具有很強(qiáng)的不確定性,因此很難從不確定圖找出原圖.為了度量隱私保護(hù)的效果,我們引入了邊熵,使用邊熵來衡量不確定圖的不確定性,即不確定圖的隱私保護(hù)程度.

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

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

4.3 數(shù)據(jù)效用度量

NE表示圖中邊的個數(shù),AD表示圖中節(jié)點(diǎn)的平均度,DV表示圖中節(jié)點(diǎn)的度方差,NE′表示不確定圖中邊的個數(shù),AD′表示不確定圖中節(jié)點(diǎn)的平均度.

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

4.4 結(jié)果分析

基于節(jié)點(diǎn)特征的不確定圖方法在生成不確定圖的過程中,先選擇重要節(jié)點(diǎn),以這些重要節(jié)點(diǎn)為核心進(jìn)行鄰接點(diǎn)加邊,然后再對篩選得到的三角形邊賦概率值.m為生成不確定圖的過程中總共添加的邊數(shù),c為調(diào)節(jié)加邊數(shù)的因子,實(shí)際添加的邊數(shù)為m·c.在表1中,添加的邊數(shù)增加,生成的不確定圖的邊熵值不斷增長,這說明達(dá)到的隱私保護(hù)效果越來越好,同時證明了該方法能夠?qū)崿F(xiàn)隱私保護(hù).

表1 基于節(jié)點(diǎn)特征不確定圖方法中邊熵變化情況

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

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

通過表1可知本文的方法能夠可以達(dá)到較好的隱私保護(hù)效果.對比表1和表2的隱私保護(hù)效果度量數(shù)值,當(dāng)網(wǎng)絡(luò)較小時,本文算法的保護(hù)強(qiáng)度優(yōu)于(k,ε)混淆算法.隨著網(wǎng)絡(luò)規(guī)模增大,(k,ε)混淆算法優(yōu)于本文算法.

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

表3 原始圖與本文方法生成的不確定圖的數(shù)據(jù)

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

5 結(jié)論與展望

本文方法在實(shí)現(xiàn)隱私保護(hù)時,通過節(jié)點(diǎn)的度中心性選擇出重要節(jié)點(diǎn),以這些重要節(jié)點(diǎn)為核心,結(jié)合不確定圖方法實(shí)現(xiàn)了社交網(wǎng)絡(luò)的隱私保護(hù).經(jīng)過各種數(shù)據(jù)集的實(shí)驗(yàn)驗(yàn)證,基于節(jié)點(diǎn)特征的不確定圖方法不僅能夠?qū)崿F(xiàn)社交網(wǎng)絡(luò)隱私保護(hù),而且與(k,ε)混淆算法相比具有較好的數(shù)據(jù)效用.

雖然本文方法實(shí)現(xiàn)了社交網(wǎng)絡(luò)的隱私保護(hù)，但還需要在保持?jǐn)?shù)據(jù)效用的前提下,研究進(jìn)一步提高隱私保護(hù)的效果.

[1]中國互聯(lián)網(wǎng)信息中心. 第41次《中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告》發(fā)布[EBOL]. [2018-03-20]. http:www.cnnic.net.cngywmxwzxrdxw201801t20180131_70188.htm

[2]eMarketer. 2017年全球社交網(wǎng)絡(luò)用戶達(dá)24.8億[EBOL]. [2018-03-20]. http:www.199it.comarchives678247.html

[3]Hely. 2016年十大數(shù)據(jù)泄露事件: 社交網(wǎng)絡(luò)成泄露重災(zāi)區(qū)[EBOL]. [2018-03-20]. http:www.raincent.comcontent-10-8087-2.html

[4]劉向宇, 王斌, 楊曉春. 社會網(wǎng)絡(luò)數(shù)據(jù)發(fā)布隱私保護(hù)技術(shù)綜述[J]. 軟件學(xué)報, 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