基于改進輪廓信息模型的異構去匿名化算法

張小云

(武警甘肅總隊，甘肅, 蘭州 730046)

0 引言

社交網絡[1-2]已成為人們生活不可或缺的一部分。隨著社交網絡的普及，人們享受著各種社交網絡的豐富功能和服務，包括分享狀態更新、發布照片、與他人交流和交友。由于不同社交網絡的功能不同，用戶往往會出于不同的目的登錄多個社交網絡，如微信、微博、QQ等。聚合不同社交網絡的用戶檔案可以揭示用戶的相關信息。然而跨網絡信息是一把雙刃劍：一方面，一旦識別或映射了用戶在不同社交網絡中的多個賬戶，就可以收集這些賬戶的配置文件、偏好和活動，從而有利于個性化、目標定位和推薦[3]；另一方面，可利用跨網絡聚合收集目標用戶的各個方面的信息，這將導致嚴重的隱私泄露問題[4]。因此，社交網絡正面臨著去匿名化攻擊的威脅。

社交網絡去匿名化是近年來的一個研究熱點。劉家霖等[5]基于社交網絡的拓撲結構，提出了一種高效高精度的無種子去匿名化算法RoleMatch識別個體身份。胡開先等[6]提出了一種基于社交關系的多數投票的身份識別方法，對社交關系中的用戶身份特征進行統計，推測當前用戶的地址信息、實體信息和用戶興趣。胡光武等[7]將社交網絡的去匿名問題轉化為輔助網絡與匿名網絡之間的節點匹配問題，并提出了一種基于隨機森林分類器的社交網絡去匿名方案。王照永等[8]利用社交網絡圖的結構特征與節點屬性的特征之間的相似性差異實現節點間的映射，并提出一種基于用戶社交網絡圖的結構和用戶節點的特征來披露用戶敏感信息的去匿名方法。上述方法大多數基于同一組用戶的不同社交網絡應該顯示相似的網絡拓撲結構的假設。這種方法的觀察結果導致用戶傾向于在不同的社交網絡中與他們感興趣或熟悉的相似用戶建立聯系。然而，在異構的社交網絡中，由于不同社交網絡的用戶并不總是重疊的，不同社交網絡使用模式的多樣性將進一步導致不同社交網絡的網絡結構不一致。

為了進一步研究異構的社交網絡聚合導致的隱私泄露，本文設計一種異構去匿名化算法。該方法聯合利用公開的網絡結構信息和用戶信息，可以顯著提高檢測精度。

1 相關概念

1.1 圖論

社交網絡結構通常表示為一個圖[9]，其中，每個用戶是圖中的一個節點，一對用戶之間的連接表示為邊。設G=(V,E)表示一個社交網絡圖，其中，V是一組用戶，E?V×V是用戶之間的一組有向/無向鏈接。e(v1,v2)表示v1和v2是朋友關系或跟隨關系，其中：e∈E；v1,v2∈V。鄰域和社區作為社交網絡圖中的重要結構，形式化定義如下。

定義1 用戶vi的鄰域集R是一組用戶Ri=[vj]j=1,…,?vj:?e(vj,vi)，他們與vi有直接的朋友關系或跟隨關系。進一步定義了函數α表示vi的鄰域集Ri，即α(vi)=Ri。

定義2 社交網絡圖中的社區C是G=(V,E)中頂點的不相交劃分。

形式上，本文將圖中的社區表示為C={C1,C2,…,Ck}，其中Ci≠Φ且Ci∩Ci=Φ(i≠j，i≥1和j≤k)。?Ci∈C，有VCi?V和ECi?VCi×VCi。本文假定社區由Infomap算法定義，該算法使用網絡上隨機游動的概率流，并通過壓縮概率流的描述將網絡分解為模塊。

1.2 輪廓信息模型

作為旨在吸引眼球、提升自我展示、促進和維持社會資本的平臺，社交網絡必須允許公眾獲得部分用戶資料信息。根據平臺定義和/或用戶定義的隱私設置，社交網絡上公開的個人資料信息量各不相同。為了利用異構社交網絡中的個人資料信息，本文首先給出一個統一的定義。

定義3 設Xi=[xik]k=1,…,d表示與用戶vi∈V相關聯的一組屬性(例如用戶名(昵稱)、位置、自我描述等)，其中，d是屬性類型的數目，xik記錄用戶vi的第k個屬性的內容。如果用戶vi的第j屬性在社交網絡上不可用(例如，用戶選擇不在微信上顯示其位置信息)，則xij=null。

需注意，一個用戶可能有幾個向量來模擬他/她擁有賬戶的社交網絡中的不同配置文件。兩個向量之間的公共屬性將用于計算輪廓相似度。

由于異構社交網絡平臺包含不同類型的概要信息，并且其中一些包含語義或句法意義，因此從2個異構社交網絡映射2個用戶賬戶類似于一個本體匹配問題。通常，本體匹配確定一對本體O1和O2的相似度。每個本體由一組離散的屬性組成，這些屬性通常以表、類、屬性的形式表示，并確定輸出關系。本文假定輪廓匹配定義如下。

定義4pA={x1,x2,…,xA}和pU={x1,x2,…,xU}為2個輪廓。如果2個屬性xi∈pA和xj∈pU，有type(xi)=type(xj)，則2個屬性之間的相似度定義為

sima=matchScore(xi,xj)

(1)

這里的相似度取決于所考慮的屬性，可以是年齡或性別值的相似度、昵稱名稱的字符串相似度、描述或文本相似度、位置或家鄉的語義相似度等。然后通過式(2)計算輪廓的相似度，

(2)

其中，wr為賦予屬性的權重，t為2個輪廓之間相同類型的屬性對的數目。

1.3 攻擊模型

假設2個異構的社會網絡圖為GA和GU，GA表示匿名網絡圖，GU表示為輔助網絡圖。注意，這里的圖不一定是社交網絡的整個圖，反匿名攻擊可以對攻擊者收集的部分圖(即子圖)進行。也就是說，攻擊者能夠通過發布的數據集或爬網站點獲得子圖G=(V,E)和對應于vi∈V的輪廓屬性Xi。攻擊者的目標是通過將GA中的用戶映射到GU中的用戶來了解不同網絡中用戶的更多信息。為了實現這一目標，攻擊者需要從2個不同的社交網絡中大規模、高置信度地識別屬于同一個人的賬戶。因此，攻擊模型可形式化定義為如下問題。

考慮2個不同的社交網絡圖GA=(VA,EA)和GU=(VU,EU)，Vi∈VA和Vj∈VU的屬性集合定義為Xi和Xj。通過迭代計算，用戶映射vi?vj(vi∈VA，vj∈VU)表示屬于同一個人，則有

(3)

其中，S是計算Xi和Xj之間相似度的函數(式(2))。Cand.A和Cand.B分別是GA和GU中由社區和鄰域結構生成的潛在正確映射的2個候選集。

2 異構去匿名模型

圖1為異構去匿名模型結構。該結構有3個主要步驟：①社區檢測，根據社交網絡圖結構檢測網絡中的社區；②社區對齊，根據輪廓自動識別種子，并對齊包含相同種子對的社區；③在社區節點映射，在每對對齊的社區中計算具有高相似度得分的節點，該得分由輪廓相似度計算，并傳播到其鄰域節點。算法1為整個過程執行過程。

圖1 異構去匿名模型結構

算法1 異構去匿名模型執行過程輸入:GA,GU,閾值θ;輸出:用戶映射μ′//社區檢測CA=Infomap(GA)CU=Infomap(GU)//社區對齊μ=SelectSeeds(VA,Vb)CommPairs=AlignCommunities(CA,CU,μ)//社區內節點映射μ′=InCommunityMapping(CommPairs,μ,θ)Returnμ′

2.1 社區檢測

第一步的目標是將社交網絡圖GA和GU劃分為兩組社區CA={c1,c2,…,cm}和CB={c1,c2,…,cn}。在Infomap算法[10]的基礎上設計社區檢測算法，該算法具有較低的時間復雜度，可以將不相交、不重疊的社區CA和CU分別劃分為2個圖。簡言之，Infomap找到了隨機游走者的最短多級描述，因此給出了網絡的最佳分層聚類、每個層次上的最佳層數和模塊劃分。因此，使用Infomap算法的另一個優點是它可以在不同的層次上生成不同尺度的CA和CU，這樣就可以選擇相似尺度的社區進行對齊。社區檢測和劃分的算法在算法1中用Infomap(·)函數表示，且其時間復雜度為O(|E|)。

2.2 社區對齊

考慮到公共可用的概要信息，社區可以更容易地對齊。選擇用戶名(或昵稱)來識別種子。主要原因如下：首先，用戶名(或昵稱)必須在每個社交網絡的網站上都可用，因此攻擊者有足夠的機會獲取或爬網它們；其次，具有相同用戶名(或昵稱)的2個賬戶有較大概率屬于同一用戶。

設計應用于社交網絡的社區對齊算法，該算法可分為兩步執行，并根據社區中相同用戶名的個數來對齊CA和CU。

步驟1 找到具有相同用戶名μ={…,(ui,uj)k,…}的所有用戶對，其中ui∈VA和uj∈VU。使用貪婪搜索會導致O(|VA||VU|)的高度復雜性。為降低復雜度，采用哈希表實現這一過程，這樣時間復雜度就可以降低到O(|VA|+|VU|)。此過程在算法1中表示為SelectSeeds(·)函數；

步驟2 將每對社區(Ci,Cj)的初始置信度csi,j(表明2個社區是否應對齊)設置為0，其中Ci∈CA，1≤i≤m，Cj∈CU，1≤j≤n。對于每對(up,uq)∈μ，csi,j逐次累計加1，且有up∈Ci和uq∈Cj。接著，檢查社區對的所有置信度cs，如果csi,j超過閾值θcs，則對齊Ci和Cj。該過程的時間復雜度為O(|μ|)

綜上，社區對齊算法的總體復雜度為O(|VA|+|VU|)。

2.3 社區內節點映射

算法2描述了社區內節點映射算法。在每對對齊的社區內，依次執行傳播和映射算法。

算法2 InCommunityMapping(·)算法執行過程輸入:社區對CommPairs,種子μ,閾值θ;輸出:用戶映射μ′ For (Ca,Cu)j∈CommPairs do μj=Propagation(Ca,Cu)endreturn μ′=∪j=1,…,len(CommPairs)μjDef Propagation(R1,R2): μj∈μ While exists∈μj do R1=α(v1),R2=α(v2) For r1 in R1 For ri in R2 scores[r1].add(MatchScore(r1,ri)) end if MAX(scores[r1])>θ rmax=r∈MAX(scores[r1]) μj← end end end return μj

該算法以Gc1=(Vc1,Ec1)，Gc2=(Vc2,Ec2)2個社區圖和社區中的種子集μc1,c2作為輸入。算法執行時在μc1,c2的相鄰種子集中迭代地尋找新的映射，并基于圖結構擴展映射過程。在每次迭代中，該算法計算2個相鄰集Ru=α(u)和Rv=α(v)內的相似度得分，且這2個相鄰集由2個已映射的用戶u和v生成。進一步，?ru∈Ru，計算與Rv中用戶的相似度得分，并找出得分最高的rv。算法中采用MatchScore(·)函數計算相似度，如果得分超過預先定義的閾值θ，則ru和rv表示成功的映射。如果一個已經映射的節點被映射到另一個具有更高相似度分數的節點，則先前的映射將被具有更高分數的新映射替換。如果沒有發現新的映射，則該過程將停止，并收集2個社區傳播過程中未訪問的節點進行比較以找到剩余的映射。

傳播過程的時間復雜度為O(min{|Vc1|,|Vc2|}dc1dc2)，其中dc1和dc2分別是Vc1和Vc2中節點度的界限。

3 仿真與分析

以2個異構在線社交網絡的數據集(Flickr和Last.fm)驗證本文所提方法。數據集包括節點信息、邊緣信息和社交網絡用戶子集的概要信息。根據社交網絡數據集中的“朋友”或“跟隨”關系構建無向社交網絡圖。統計數據信息如表1所示。仿真環境使用Python語言，程序運行在2.4 GHz CPU，內存為32 G的服務器上。此外，選取準確率及召回率作為性能指標驗證算法性能。

表1 社交網絡數據集信息統計

3.1 閾值選取測試

圖2和圖3為不同閾值θ下本文方法與傳統輪廓匹配方法分別在數據集Flickr和Last.fm準確率和召回率對比結果。可以看出，本文方法結果明顯優于傳統輪廓匹配方法。由前述可知，閾值θ是一個相似性準則，本文算法中接受一對節點作為映射，即如果2個節點之間的相似性得分超過θ，則這2個節點表示為潛在映射。因此，θ越高，接受的節點越相似，因此返回的潛在映射就越少。所以θ實際上反映了精確性和召回之間的權衡。實際情況下，攻擊者可以根據自己的要求來選擇θ。當閾值設置為0.9時，本文方法匹配準確度可達90%以上，召回率可達40%。仿真結果進一步驗證了該算法可以實現大規模精確解匿名。

圖2 Flickr數據集仿真結果

圖3 Last.fm數據集仿真結果

3.2 算法性能測試

圖4為所提出模型在Flickr數據集中與基于節點匹配[11]、RoleMatch算法[12]的性能曲線,其中閾值設置為0.9，可以看出，所提模型在40次迭代時可獲得最佳性能，而其他模型在60次以上迭代時可獲得最佳性能，且模型準確率有所提升。由此可見，所提模型收斂速度更快，且模型性能更優。

圖4 不同算法性能對比結果

4 總結

本文對異構社交網絡中去匿名化過程過程進行了研究與分析，并提出了一種異構去匿名化算法提高模型檢測精度。

本文在進行仿真及實驗驗證時假定用戶信息都為準確的，未考慮部分用戶可能會填寫“假信息”或僅有部分信息情況。未來可對信息獲取條件受限及數據存在壞值等情況進行研究，引入大數據、數據挖掘、人工智能等技術提高用戶相似性匹配度等，進一步提升模型適用性范圍。此外，社區匹配的置信度閾值在實際狀況下可以自由選擇，未來可引入機器學習模型對閾值進行調參，選取最優閾值。