摘要：針對網(wǎng)絡(luò)數(shù)據(jù)中的隱私保護(hù)問題，浙江大學(xué)加州大學(xué)戴維斯分校和阿里云團(tuán)隊(duì)，共同發(fā)表了最新的研究成果，這項(xiàng)成果也已論文形式收錄在中。

個(gè)人數(shù)據(jù)挖掘和個(gè)人隱私保護(hù)，并非魚與熊掌，可視分析的技術(shù)手段能夠幫助我們保護(hù)個(gè)人隱私數(shù)據(jù)，避免后續(xù)的數(shù)據(jù)挖掘暴露隱私的同時(shí)，平衡數(shù)據(jù)質(zhì)量發(fā)生的變化，減少對后續(xù)數(shù)據(jù)挖掘的影響。針對網(wǎng)絡(luò)數(shù)據(jù)中的隱私保護(hù)問題，浙江大學(xué)、加州大學(xué)戴維斯分校和阿里云DataV團(tuán)隊(duì)，共同發(fā)表了最新的研究成果《GraphProtector: a Visual Interface for Employing andAssessing Multiple Privacy Preserving Graph Algorithms》【1】，這項(xiàng)成果也已論文形式收錄在IEEE TVCG中。

背景

關(guān)系描述了人與人之間的互相聯(lián)系，它可以是一種靜態(tài)的連接，如“親屬”、“朋友”等，也可以是動(dòng)態(tài)的，通過動(dòng)作將其關(guān)聯(lián)，例如“通話”、“郵件”等?？萍嫉倪M(jìn)步使得人與人之間的聯(lián)系更為密切，關(guān)系變得更復(fù)雜，進(jìn)而形成了一張偌大的網(wǎng)，因此，我們也把這類數(shù)據(jù)稱之為網(wǎng)絡(luò)數(shù)據(jù)（或圖數(shù)據(jù)）。網(wǎng)絡(luò)數(shù)據(jù)的研究被廣泛應(yīng)用于各個(gè)領(lǐng)域，它能夠幫助識(shí)別社團(tuán)、劃分人群，定位特殊人物、研究信息傳播、追蹤欺詐行為等。但在對這類數(shù)據(jù)進(jìn)行研究的同時(shí)，伴隨著巨大的隱私泄露風(fēng)險(xiǎn)。為了能夠在探索數(shù)據(jù)背后巨大價(jià)值的同時(shí)，保護(hù)用戶的隱私不被泄露，我們提出了一個(gè)能夠應(yīng)對網(wǎng)絡(luò)數(shù)據(jù)隱私攻擊，提供有效隱私保護(hù)的可視分析系統(tǒng)——GraphProtector，它不僅能夠更全面、更細(xì)致地保護(hù)用戶隱私，同時(shí)也能夠兼顧數(shù)據(jù)的實(shí)用性，保證數(shù)據(jù)的質(zhì)量。

隱私保護(hù)方法和流程

針對網(wǎng)絡(luò)數(shù)據(jù)的隱私保護(hù)相較于一般數(shù)據(jù)而言，更為困難，原因主要有以下兩點(diǎn)：

1) 網(wǎng)絡(luò)數(shù)據(jù)自身結(jié)構(gòu)特征繁多，例如，度數(shù)分布，最短路徑分布，接近中心性分布等，任意的結(jié)構(gòu)特征都有可能成為攻擊者的攻擊入口，可謂是防不勝防；

2) 網(wǎng)絡(luò)數(shù)據(jù)中節(jié)點(diǎn)和邊都攜帶了大量的數(shù)據(jù)，這些數(shù)據(jù)無疑給了攻擊者更多的機(jī)會(huì)去識(shí)別用戶現(xiàn)實(shí)世界中的身份。

因此，想要完全解決圖數(shù)據(jù)中的隱私問題，將會(huì)是一個(gè)非常復(fù)雜和困難的工作。在當(dāng)前階段，我們將研究的重點(diǎn)放在了網(wǎng)絡(luò)數(shù)據(jù)的結(jié)構(gòu)特征上，通過修改圖的結(jié)構(gòu)特征保護(hù)用戶的身份不被泄露。其中，之所以選擇結(jié)構(gòu)特征作為著手點(diǎn)，最重要的原因是結(jié)構(gòu)特征是網(wǎng)絡(luò)數(shù)據(jù)的基礎(chǔ)屬性，解決結(jié)構(gòu)特征暴露的隱私風(fēng)險(xiǎn)是是解決隱私暴露的必經(jīng)之路。在這次的研究中，我們先以以下三種結(jié)構(gòu)特征作為示例：

度數(shù)：節(jié)點(diǎn)度數(shù)是和它關(guān)聯(lián)的邊的總數(shù)（如圖二中，圖c表格中Degree展示了原始圖圖a的度數(shù)分布）；

中心指紋：是指在最長路徑i的限制下，圖中普通節(jié)點(diǎn)和中心節(jié)點(diǎn)們之間的最短路徑所形成的向量。這里為了簡化復(fù)雜度，我們?nèi)?b>i設(shè)為了1，即普通節(jié)點(diǎn)和中心節(jié)點(diǎn)們是否存在相鄰關(guān)系作為節(jié)點(diǎn)的中心指紋（如圖二中，圖c中HubFingerprint為選取了原始圖圖a中4號(hào)節(jié)點(diǎn)和7號(hào)節(jié)點(diǎn)作為中心的的中心指紋分布）；

子圖：指節(jié)點(diǎn)集和邊集分別是某一圖的節(jié)點(diǎn)集的子集和邊集的子集的圖（如圖二中，圖b為原始圖圖a的子圖）；

前人的研究提供了多種隱私匿名保護(hù)思路，如k-匿名、聚類和查分隱私等等，我們在研究中選取了k-匿名模型作為我們保護(hù)的基本方法。k-匿名模型是最經(jīng)典的語義匿名模型之一，在隱私保護(hù)領(lǐng)域得到了廣泛的應(yīng)用，在這個(gè)模型中，它通過準(zhǔn)標(biāo)識(shí)符將數(shù)據(jù)分成若干個(gè)等價(jià)類（例如度數(shù)相同的節(jié)點(diǎn)形成了一個(gè)度數(shù)等價(jià)類，中心指紋相同的節(jié)點(diǎn)形成了一個(gè)中心指紋等價(jià)類，結(jié)構(gòu)相同的子圖形成了一個(gè)子圖等價(jià)類），并要求每個(gè)等價(jià)類中至少存在k個(gè)數(shù)據(jù)記錄（例如當(dāng)k為2時(shí)，k-匿名模型要求每一個(gè)度數(shù)等價(jià)類中至少存在2個(gè)節(jié)點(diǎn)），對于這k個(gè)數(shù)據(jù)記錄中的任意一條，被識(shí)別出的概率為1/k，從而使得攻擊者無法確定他們的攻擊目標(biāo)。

通過前人的研究分析我們得知，沒有任何一種隱私保護(hù)方法能夠抵抗所有的攻擊，k-匿名模型是眾多方法中最為強(qiáng)大的一種，它在一定條件下可以抵抗大部分的隱私攻擊，并且對于數(shù)據(jù)質(zhì)量傷害的程度較小，使得經(jīng)過隱私匿名保護(hù)后的數(shù)據(jù)仍然能夠應(yīng)用于后面的分析和研究中。

在k-匿名模型的基礎(chǔ)上，為了盡可能地減少對數(shù)據(jù)質(zhì)量的損害，我們采取了保持節(jié)點(diǎn)個(gè)數(shù)不變，僅增加或減少邊的策略。同時(shí)，在目前我們的研究中，為了減少保護(hù)方法之間的沖突以及降低計(jì)算的復(fù)雜度，我們首先將研究的重點(diǎn)放在了增加邊的策略上。

上文中多次提到了“數(shù)據(jù)質(zhì)量”，保證數(shù)據(jù)質(zhì)量是我們隱私保護(hù)過程中的一個(gè)重要目標(biāo)（試想，如果不考慮數(shù)據(jù)質(zhì)量，我們完全可以同化所有的用戶數(shù)據(jù)，這樣一來攻擊者將無法定位到攻擊目標(biāo)，但這樣的數(shù)據(jù)卻失去了研究意義）。在使用k-匿名模型增加邊的方法來保護(hù)數(shù)據(jù)隱私時(shí)，有兩種處理策略：

1）為當(dāng)前等價(jià)類中的元素增加適當(dāng)?shù)倪?，使得這些元素全部轉(zhuǎn)移到其他等價(jià)類中，使得當(dāng)前等價(jià)類不存在，也就不會(huì)存在隱私暴露風(fēng)險(xiǎn)；

2）為其他等價(jià)類中元素增加適當(dāng)?shù)倪?，使其中的元素轉(zhuǎn)移到當(dāng)前等價(jià)類中，從而使當(dāng)前等價(jià)類滿足k-匿名模型的要求?；诒Ｗo(hù)數(shù)據(jù)質(zhì)量的目的，對于這兩種策略，我們將計(jì)算它們的代價(jià)，及增加邊的數(shù)量，采取代價(jià)較小的的方法執(zhí)行。我們設(shè)計(jì)了詳細(xì)的算法來實(shí)現(xiàn)這一目標(biāo)。另一方面，對于數(shù)據(jù)質(zhì)量的變化，系統(tǒng)提供若干的實(shí)用性指標(biāo)，如度數(shù)、最短路徑等，我們將在數(shù)據(jù)處理中以及數(shù)據(jù)處理后呈現(xiàn)這些指標(biāo)的變化，幫助使用者進(jìn)行決策，從而能夠采取“最優(yōu)”的解決方案。

下圖展現(xiàn)了采用GraphProtector進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)隱私保護(hù)的流程：

數(shù)據(jù)導(dǎo)入：首先，導(dǎo)入待保護(hù)的網(wǎng)絡(luò)數(shù)據(jù)，系統(tǒng)將使用節(jié)點(diǎn)連接圖的形式呈現(xiàn)原始數(shù)據(jù)。此外，系統(tǒng)還提供一些原始數(shù)據(jù)的結(jié)構(gòu)特征分布供使用者觀察和探索。

優(yōu)先級(jí)制定及評估指標(biāo)選?。?/strong>在這個(gè)階段，通過觀察原始數(shù)據(jù)的結(jié)構(gòu)特征分布，使用者對節(jié)點(diǎn)的優(yōu)先級(jí)進(jìn)行排序，優(yōu)先級(jí)排序決定了節(jié)點(diǎn)的處理順序，排序較高的節(jié)點(diǎn)將會(huì)被優(yōu)先處理。此外，使用者在優(yōu)先級(jí)排序時(shí)可以鎖定一些節(jié)點(diǎn)，被鎖定的節(jié)點(diǎn)（一般為比較重要的節(jié)點(diǎn)，如核心人物等）將不會(huì)參與到處理過程中，因此在隱私保護(hù)處理前后，它的關(guān)聯(lián)關(guān)系將不發(fā)生改變。在這個(gè)階段，使用者還需要選擇關(guān)注的實(shí)用性指標(biāo)，在數(shù)據(jù)處理前后，系統(tǒng)將呈現(xiàn)這些指標(biāo)的變化，使用者可以通過它們來評估數(shù)據(jù)質(zhì)量的變化。