摘要：針對網絡數據中的隱私保護問題，浙江大學加州大學戴維斯分校和阿里云團隊，共同發表了最新的研究成果，這項成果也已論文形式收錄在中。

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

背景

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

隱私保護方法和流程

針對網絡數據的隱私保護相較于一般數據而言，更為困難，原因主要有以下兩點：

1) 網絡數據自身結構特征繁多，例如，度數分布，最短路徑分布，接近中心性分布等，任意的結構特征都有可能成為攻擊者的攻擊入口，可謂是防不勝防；

2) 網絡數據中節點和邊都攜帶了大量的數據，這些數據無疑給了攻擊者更多的機會去識別用戶現實世界中的身份。

因此，想要完全解決圖數據中的隱私問題，將會是一個非常復雜和困難的工作。在當前階段，我們將研究的重點放在了網絡數據的結構特征上，通過修改圖的結構特征保護用戶的身份不被泄露。其中，之所以選擇結構特征作為著手點，最重要的原因是結構特征是網絡數據的基礎屬性，解決結構特征暴露的隱私風險是是解決隱私暴露的必經之路。在這次的研究中，我們先以以下三種結構特征作為示例：

度數：節點度數是和它關聯的邊的總數（如圖二中，圖c表格中Degree展示了原始圖圖a的度數分布）；

中心指紋：是指在最長路徑i的限制下，圖中普通節點和中心節點們之間的最短路徑所形成的向量。這里為了簡化復雜度，我們取i設為了1，即普通節點和中心節點們是否存在相鄰關系作為節點的中心指紋（如圖二中，圖c中HubFingerprint為選取了原始圖圖a中4號節點和7號節點作為中心的的中心指紋分布）；

子圖：指節點集和邊集分別是某一圖的節點集的子集和邊集的子集的圖（如圖二中，圖b為原始圖圖a的子圖）；

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

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

在k-匿名模型的基礎上，為了盡可能地減少對數據質量的損害，我們采取了保持節點個數不變，僅增加或減少邊的策略。同時，在目前我們的研究中，為了減少保護方法之間的沖突以及降低計算的復雜度，我們首先將研究的重點放在了增加邊的策略上。

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

1）為當前等價類中的元素增加適當的邊，使得這些元素全部轉移到其他等價類中，使得當前等價類不存在，也就不會存在隱私暴露風險；

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

下圖展現了采用GraphProtector進行網絡數據隱私保護的流程：

數據導入：首先，導入待保護的網絡數據，系統將使用節點連接圖的形式呈現原始數據。此外，系統還提供一些原始數據的結構特征分布供使用者觀察和探索。

優先級制定及評估指標選?。?/strong>在這個階段，通過觀察原始數據的結構特征分布，使用者對節點的優先級進行排序，優先級排序決定了節點的處理順序，排序較高的節點將會被優先處理。此外，使用者在優先級排序時可以鎖定一些節點，被鎖定的節點（一般為比較重要的節點，如核心人物等）將不會參與到處理過程中，因此在隱私保護處理前后，它的關聯關系將不發生改變。在這個階段，使用者還需要選擇關注的實用性指標，在數據處理前后，系統將呈現這些指標的變化，使用者可以通過它們來評估數據質量的變化。