K-對稱-N算法的社交網絡的隱私保護

◆高 潔 肖基毅 向 霞

（南華大學計算機科學與技術學院 湖南 421001）

K-對稱-N算法的社交網絡的隱私保護

◆高 潔 肖基毅 向 霞

（南華大學計算機科學與技術學院 湖南 421001）

針對k匿名算法在對抗結構攻擊的不足，采用k-對稱匿名算法對社會網絡的隱私進行保護。本文對k-對稱匿名算法進行可行性分析，并對其還原算法進行描述。雖然社會網絡的隱私保護取得了大量的研究成果，社區結構的隱私保護也取得了很多成功，但是其成果都是彼此相對獨立的，鮮有將二者兼顧。本文設計出一種k-對稱-N匿名算法來解決此類問題。

k-對稱匿名; 社區結構; 隱私保護

0 前言

隨著社交網絡的普及以及數據挖掘的技術的成熟，人們的隱私保護問題成為了近些年來的研究熱點。人們在期望信息共享的同時又畏懼著信息共享[1]。太多的信息泄漏事件使得人們不敢將信息放在社交網絡上進行交流，這就給數據挖掘等相關科研或者企業帶來了一定的困難。一般的社區網絡數據發布要在發布之前對數據進行一定的處理才把數據發布到網絡中。一般采用泛化與隱匿技術來進行數據的預處理。一般采用簡單匿名的方式，但是簡單匿名采用自底往上的匿名方式，會使得匿名后的數據可能世界空間加大，無法保持數據的可用性。本文采用不確定性泛化策略來克服這種困難。隱私保護技術現階段有很多模型被廣泛應用。其中為k-匿名模型、l-多樣性算法、以及個性化（a，k）-匿名三種最為廣泛應用[3]。其中k匿名算法的應用最非常廣泛，但是其存在多種不足[4]，本文在其基礎上，針對其針對社會網絡圖中的不足之處提出的改進k-對稱匿名算法運用到社區網絡之中。社區網絡是社交網絡中一個經典的問題。社區網絡的發現算法包括KL算法、分割算法、譜分割算法、多級別圖圖分割算法、基于馬爾科夫聚類的算法、局部圖聚類算法等。本文基于分割算法對社交網絡進行社區劃分。然后結合k-對稱匿名算法提出了k-對稱N匿名算法。

1 k-對稱-社區匿名算法的實現過程

k-對稱-社區匿名算法（K-symmetry-community anonymity algorithm）是一種在基于社區網絡劃分的前提下的關于結構圖的k匿名算法。其流程圖如圖1下面將對算法進行詳情介紹。

2 數據的預處理

傳統的社區擾亂技術通常在于擾亂社區內朋友之間的邊得關系，并不注重社區結構的保持。我們采用一種特殊的社區擾亂技術。在進行社區劃分之前對數據進行簡單處理。

（1）迭代查詢節點H的社會網絡圖。H1（節點）、H2（節點的度）、H3（節點的鄰接節點的度集合）。

（2）If Hx3==Hy3交換節點Hx、Hy

它使得攻擊者事先插入的節點改變了位置，導致攻擊錯誤的攻擊到其不感興趣的社區導致攻擊失敗。

3 社區劃分算法

社區發現技術是本算法研究中核心部分。本算法采用邊分割算法，其依據是社區間邊的權值betweenness大于社區內邊的權值。通過刪除較大權值的邊來進行社區分割。循環分割直到社區數目達到預期的數目為止。

4 社區聚類

數據挖掘中聚類一般分為三種:基于劃分的方法、基于層次的方法、基于密度的方法三種。

本文采用第三種基于密度的聚類方式對社區進行聚類。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一個比較有代表性的基于密度的聚類算法。能夠把具有足夠高密度的區域劃分為簇，并能發現任意形狀的聚類。

圖1 k-對稱-N社區隱私保護算法流程圖

社區聚類的目地是將相似度大于一定閥值的社區進行聚集，使得一個簇內含有N個社區。這與k匿名算法的思想相同，將每個社區隱藏在與其相似的其余N-1個社區中。并用NMI對社區劃分準確度進行測量。

5 虛擬社區的產生

對于一個簇內不滿N個的社區采取虛擬社區產生的方式，使其滿足一個簇內至少有N個社區。

傳統的算法虛擬社區的產生與邊的數目都是隨機的，這種形式下的虛擬社區與本來存在的社區的差別很大。為了更好的使得社區的產生更加真實化，本文對每個簇內節點期望值與邊的期望值作為最初的虛擬社區的節點數目與邊的條數，并在簇內隨機挑選本簇內的節點作為虛擬社區的節點，并隨機生成期望值條邊。形成初始的社區。根據公式（1）求此簇內與其他社區內相似度最大的社區。并計算虛擬社區與此社區之間的相似度。

設A1=(M1,N1),A2=(M2,N2)是社區網絡A=(M.N)的非空社區。Ni1=Ni(兩個社區中的邊),Ni2={nxy=(mx,my)∈N|mx∈M1,my∈M2},(兩個社區連接邊)，Ni3={nx,y=(mx,my) ∈N|mx∈Mi,my∈M-N1-M2}(社區空間中非這兩個社區與兩社區的連接邊)，其中1,2,j=1,2,3,設集合Q，則A1和A2的相似度S(A1,A2)定義為：

其中?為加權印子 (0≤?≤1),其中 ?用于確定節點相似度(邊相似度)占社區相似度所占的比重。std(Q)和分別為實數集合Q中的均值和標準差。e-|M1|,f=|M2|,rx∈M1,ty∈M2。

這種方法即考慮了節點的相似度，也考慮了邊的相似度。

若虛擬社區與相似度最大社區之間的相似度小于閥值時，求虛擬社區對相似度最大社區的等異度子集，并將其按度的降序排列的同時將相似度最大的社區度按降序排列，然后將虛擬社區等異度子集度的一半數目的節點用最大社區降序前相同數目的節點替換。將虛擬社區交換后的節點相連的邊刪除。并在社區內隨機產生相同數目的邊（邊的數目不變原則）。重新計算虛擬社區與相似度最大社區的相似度，小于閥值繼續上述步驟。大于閥值則結束。

6 社區內部優化k-對稱算法

由于社區的聚類使得每個節點至少隱藏在N個社區之內，但是對于這種隱藏方式與k匿名一樣對預防鏈接攻擊有很好的療效。但一個簇內的社區很大程度上是敏感同質的，對于社區內的節點有時保護度不夠，我們對于社區內部再次使用k-對稱匿名算法。是其應對對于社區內部的結構攻擊。

K-對稱匿名算法是k匿名的算法在圖論中應用的一種變種。其將圖論中的圖對稱理論運用到k-匿名算法中。簡單講是對社區的節點進行對稱處理后再進行k-匿名。本文由于篇幅問題紙描述一個社區的k-對稱匿名過程。

其步驟如下:

對圖中的節點做出社會網路關系矩陣，本文中因為是無向圖，矩陣是對稱矩陣。

找出圖中自首等價數目最少的節點，對其進行對稱處理。判斷每個節點是否至少有k個自守等價的節點，不滿足重復步驟2。滿足則結束。

其是k-匿名算法在圖結構的變種，是可行的。相對于傳統的將每個節點都做對稱處理節點和邊都減少很多。復雜度降低。

其還原算法，將最后相同的等價類只留一個，這種還原方法雖然無法百分之百還原原始數據，但在一定程度上還是可取的。

7 實驗及分析

將k-對稱N社區發現算法在不同的k值下的信息損失與經典的p-Sensitive k-匿名算法進行比較。已判斷其數據的真實性。

K-對稱-N匿名算法與經典p-Sensitive k-匿名算法信息損失對比如圖2。

由實驗可知k-對稱-N算法比p-Sensitive k-匿名算法數據損失小，證明了其有效性。

其數據隱私保護度相對與傳統的k匿名算法又增加了N社區匿名。大大提高了隱私的保護度。