基于改進輪廓信息模型的異構(gòu)去匿名化算法

張小云

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

0 引言

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

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

為了進一步研究異構(gòu)的社交網(wǎng)絡(luò)聚合導(dǎo)致的隱私泄露，本文設(shè)計一種異構(gòu)去匿名化算法。該方法聯(lián)合利用公開的網(wǎng)絡(luò)結(jié)構(gòu)信息和用戶信息，可以顯著提高檢測精度。

1 相關(guān)概念

1.1 圖論

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

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

定義2 社交網(wǎng)絡(luò)圖中的社區(qū)C是G=(V,E)中頂點的不相交劃分。

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

1.2 輪廓信息模型

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

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

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

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

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

sima=matchScore(xi,xj)

(1)

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

(2)

其中，wr為賦予屬性的權(quán)重，t為2個輪廓之間相同類型的屬性對的數(shù)目。

1.3 攻擊模型

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

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

(3)

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

2 異構(gòu)去匿名模型

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

圖1 異構(gòu)去匿名模型結(jié)構(gòu)

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

2.1 社區(qū)檢測

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

2.2 社區(qū)對齊

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

設(shè)計應(yīng)用于社交網(wǎng)絡(luò)的社區(qū)對齊算法，該算法可分為兩步執(zhí)行，并根據(jù)社區(qū)中相同用戶名的個數(shù)來對齊CA和CU。

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

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

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

2.3 社區(qū)內(nèi)節(jié)點映射

算法2描述了社區(qū)內(nèi)節(jié)點映射算法。在每對對齊的社區(qū)內(nèi)，依次執(zhí)行傳播和映射算法。

算法2 InCommunityMapping(·)算法執(zhí)行過程輸入:社區(qū)對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個社區(qū)圖和社區(qū)中的種子集μc1,c2作為輸入。算法執(zhí)行時在μc1,c2的相鄰種子集中迭代地尋找新的映射，并基于圖結(jié)構(gòu)擴展映射過程。在每次迭代中，該算法計算2個相鄰集Ru=α(u)和Rv=α(v)內(nèi)的相似度得分，且這2個相鄰集由2個已映射的用戶u和v生成。進一步，?ru∈Ru，計算與Rv中用戶的相似度得分，并找出得分最高的rv。算法中采用MatchScore(·)函數(shù)計算相似度，如果得分超過預(yù)先定義的閾值θ，則ru和rv表示成功的映射。如果一個已經(jīng)映射的節(jié)點被映射到另一個具有更高相似度分?jǐn)?shù)的節(jié)點，則先前的映射將被具有更高分?jǐn)?shù)的新映射替換。如果沒有發(fā)現(xiàn)新的映射，則該過程將停止，并收集2個社區(qū)傳播過程中未訪問的節(jié)點進行比較以找到剩余的映射。

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

3 仿真與分析

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

表1 社交網(wǎng)絡(luò)數(shù)據(jù)集信息統(tǒng)計

3.1 閾值選取測試

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

圖2 Flickr數(shù)據(jù)集仿真結(jié)果

圖3 Last.fm數(shù)據(jù)集仿真結(jié)果

3.2 算法性能測試

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

圖4 不同算法性能對比結(jié)果

4 總結(jié)

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

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