基于局部高階子圖的差分隱私保護(hù)社區(qū)發(fā)現(xiàn)算法

侯小軍，李澤華，邊 錦

（1.西安理工大學(xué) 信息化管理處，陜西 西安 710048；2.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710010；3.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710010）

1.緒論

近年來(lái)，隨著互聯(lián)網(wǎng)技術(shù)應(yīng)用的迅猛發(fā)展，在線社交網(wǎng)絡(luò)服務(wù)已經(jīng)成為人們交流溝通、分享傳遞信息的重要平臺(tái)，通過(guò)網(wǎng)絡(luò)維系著用戶的社會(huì)關(guān)系，逐漸形成了潛在的社區(qū)結(jié)構(gòu)，其中根據(jù)個(gè)人的行為將個(gè)人分組為社區(qū)，通常，同一社區(qū)內(nèi)的個(gè)體更有可能分享直接的社交鏈接，共同的朋友和相似的個(gè)人資料等。但是社交關(guān)系常常處于不斷變化的狀態(tài)，其動(dòng)態(tài)范圍從分分秒秒的變化逐漸到多年來(lái)所呈現(xiàn)的模式，故而衍生出動(dòng)態(tài)社交網(wǎng)絡(luò)。

本文針對(duì)在動(dòng)態(tài)的社區(qū)劃分過(guò)程中存在的局部子圖隱私信息泄露問(wèn)題，結(jié)合社區(qū)發(fā)現(xiàn)算法、隨機(jī)游走算法以及差分隱私提出了一種可以保證子圖隱私信息安全性的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法，實(shí)現(xiàn)了高效的非重疊社區(qū)劃分操作。

2.基礎(chǔ)理論與相關(guān)工作

2.1 基礎(chǔ)理論

定義1（差分隱私—Differential Privacy[1]）假定隨機(jī)算法M，PM表示M的取值范圍，對(duì)于任意兩個(gè)鄰近數(shù)據(jù)集D與D"，在PM下的任意一個(gè)子集SM中，如果任意輸出結(jié)果M滿足如下不等式：

定義2（ω-事件隱私[2]）ω-事件隱私是一種基于差分隱私的機(jī)制，為ω時(shí)間戳的任何窗口內(nèi)發(fā)生的任何事件提供可證明的隱私保證。針對(duì)時(shí)間戳為i的兩個(gè)鄰近數(shù)據(jù)集Di,，無(wú)限序列的流前綴在時(shí)間戳為t時(shí)定義為

定義3（局部高階子圖（Motif）[3]）社交網(wǎng)絡(luò)豐富的高階組織結(jié)構(gòu)通過(guò)高階鏈接模式的聚類從而表現(xiàn)出來(lái)，最普通的局部高階子圖為小網(wǎng)絡(luò)子圖，稱為網(wǎng)絡(luò)基序（主題），被認(rèn)為是復(fù)雜網(wǎng)絡(luò)的構(gòu)建塊，如圖1所示。

圖1 局部高階子圖

定義4（主題電導(dǎo)—Motif Conductance[4]）對(duì)于一個(gè)網(wǎng)絡(luò)主題實(shí)例M的主題電導(dǎo)定義如下：

網(wǎng)絡(luò)主題M為任意小的連通子圖。節(jié)點(diǎn)S集合的主題劃分由cutM(S)表示，其中至少存在一個(gè)節(jié)點(diǎn)在S中，另一個(gè)節(jié)點(diǎn)在中，如圖2中A圖所示，節(jié)點(diǎn)S的主題劃分體積由volM(S)表示主題實(shí)例節(jié)點(diǎn)在S中的數(shù)量，社區(qū)劃分操作如圖2中B圖所示。

圖2 主題電導(dǎo)及劃分

定義5（時(shí)序圖-時(shí)序主題[5]）時(shí)序邊為有序節(jié)點(diǎn)對(duì)之間帶有時(shí)間戳的有向邊，時(shí)序圖由多條時(shí)序邊組成，時(shí)序圖如圖3中A圖所示。A:一個(gè)有九條時(shí)序邊的時(shí)序圖，每條邊都有一個(gè)時(shí)間戳（以秒為單位）。B:三個(gè)節(jié)點(diǎn)，三條邊的δ-時(shí)序網(wǎng)絡(luò)主題M。C:δ-時(shí)序主題M的實(shí)例，時(shí)間戳范圍δ=10s，被消去的主題均不是M的實(shí)例，因?yàn)檫叾ㄏ蜿P(guān)系方向不正確或者在δ時(shí)間戳范圍內(nèi)未發(fā)生。

圖3 時(shí)序圖

2.2 相關(guān)工作

基于局部高階子圖的圖聚類劃分，Hu[6]等人提出m-派系主題，并在大型異構(gòu)信息網(wǎng)絡(luò)中尋求最大的網(wǎng)絡(luò)主題派系，探索多種復(fù)雜網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)特征。Li[7]等人引入三角網(wǎng)絡(luò)主題劃分加權(quán)完整圖的節(jié)點(diǎn)，運(yùn)用模擬退火算法解決劃分過(guò)程中重疊聚類的節(jié)點(diǎn)。Zhang[8]等人基于局部高階網(wǎng)絡(luò)主題提出新的局部社區(qū)檢測(cè)方法（LCD-motif），通過(guò)在局部光譜范圍內(nèi)尋找稀疏矢量來(lái)劃分聚簇。以上基于局部高階子圖進(jìn)行社區(qū)劃分的研究大多應(yīng)用均在靜態(tài)社交網(wǎng)絡(luò)上執(zhí)行，但是，現(xiàn)實(shí)的網(wǎng)絡(luò)系統(tǒng)多數(shù)情況下不是靜態(tài)的，它們之間的鏈接對(duì)象隨著時(shí)間動(dòng)態(tài)變化[9]，如郵件系統(tǒng)等。依據(jù)對(duì)以上現(xiàn)有局部高階子圖研究的分析，目前動(dòng)態(tài)社交網(wǎng)絡(luò)進(jìn)行社區(qū)劃分主要存在兩個(gè)問(wèn)題：1）依據(jù)局部高階子圖的多樣性，在基于時(shí)間動(dòng)態(tài)變化的社交網(wǎng)絡(luò)上如何保證獲取準(zhǔn)確的局部子圖結(jié)構(gòu)。2）動(dòng)態(tài)社交網(wǎng)絡(luò)實(shí)現(xiàn)社區(qū)劃分的同時(shí)如何避免子圖隱私信息的泄露以及如何保證社區(qū)劃分的準(zhǔn)確度；

針對(duì)第一個(gè)問(wèn)題，基于時(shí)序網(wǎng)絡(luò)主題定義在δ時(shí)間戳范圍內(nèi)定義時(shí)序邊，提出運(yùn)用快速算法統(tǒng)計(jì)在δ時(shí)序內(nèi)生成網(wǎng)絡(luò)主題的個(gè)數(shù)，提高了算法計(jì)數(shù)的時(shí)間效率。針對(duì)第二個(gè)問(wèn)題，為δ時(shí)間戳范圍內(nèi)生成網(wǎng)絡(luò)主題的鄰接矩陣，運(yùn)用ω-事件隱私機(jī)制為相鄰時(shí)間戳鄰接矩陣的變化量添加噪聲進(jìn)行干擾，避免后期進(jìn)行隨機(jī)游走時(shí)因噪聲過(guò)大造成社區(qū)劃分準(zhǔn)確度低的問(wèn)題，與此同時(shí)且有效保護(hù)了網(wǎng)絡(luò)演化過(guò)程中局部子圖的隱私信息。

本文主要的貢獻(xiàn)如下：1）通過(guò)定義時(shí)序邊統(tǒng)計(jì)在δ時(shí)間戳范圍內(nèi)生成的網(wǎng)絡(luò)主題結(jié)構(gòu)構(gòu)建動(dòng)態(tài)主題序列，運(yùn)用快速算法統(tǒng)計(jì)真實(shí)社交網(wǎng)絡(luò)上節(jié)點(diǎn)之間生成網(wǎng)絡(luò)主題實(shí)例的個(gè)數(shù)。2）針對(duì)隨時(shí)間戳動(dòng)態(tài)變化的時(shí)序網(wǎng)絡(luò)主題子圖隱私泄露的問(wèn)題，結(jié)合ω-事件差分隱私機(jī)制[10]對(duì)δ時(shí)間戳范圍內(nèi)相鄰的網(wǎng)絡(luò)主題鄰接矩陣的變化量添加拉普拉斯噪聲進(jìn)行干擾，因?yàn)棣?事件差分隱私機(jī)制相比于其他隱私機(jī)制更好地控制了敏感度的大小；3）針對(duì)擾動(dòng)后網(wǎng)絡(luò)主題的鄰接矩陣，提出了近似個(gè)性化頁(yè)面排名算法，該排名算法對(duì)擾動(dòng)后的鄰接矩陣進(jìn)行隨機(jī)游走，其算法運(yùn)行時(shí)間不受輸入圖形大小的影響，優(yōu)于目前基于邊的個(gè)性化頁(yè)面方法。

3.基于局部高階子圖的隱私保護(hù)社區(qū)發(fā)現(xiàn)算法

3.1 算法簡(jiǎn)述

算法整體目標(biāo)是運(yùn)用有向無(wú)權(quán)圖G=(V，E)，通過(guò)定義時(shí)序邊序列，統(tǒng)計(jì)在δ時(shí)間戳內(nèi)形成的網(wǎng)絡(luò)主題，并統(tǒng)計(jì)主題在社交網(wǎng)絡(luò)節(jié)點(diǎn)上形成的個(gè)數(shù)，由鄰接矩陣Gw=(V，E，W)表示，權(quán)重W為節(jié)點(diǎn)之間生成網(wǎng)絡(luò)主題實(shí)例的個(gè)數(shù)。隨著時(shí)序網(wǎng)絡(luò)中時(shí)序邊的添加與刪除生成的基于網(wǎng)絡(luò)主題的鄰接矩陣隨時(shí)發(fā)生變化，針對(duì)網(wǎng)絡(luò)在演化過(guò)程中局部子圖隱私信息的泄露問(wèn)題，對(duì)δ時(shí)間戳內(nèi)相鄰的網(wǎng)絡(luò)主題鄰接矩陣的變化量添加拉普拉斯噪聲，對(duì)干擾后的鄰接矩陣進(jìn)行隨機(jī)游走，對(duì)社交節(jié)點(diǎn)執(zhí)行非重疊聚類劃分，從而依據(jù)動(dòng)態(tài)時(shí)序主題有效實(shí)現(xiàn)社交網(wǎng)絡(luò)的局部高階聚類挖掘。本算法運(yùn)用時(shí)序網(wǎng)絡(luò)中定義時(shí)序邊的方法，為每一條定向邊分配時(shí)間戳，構(gòu)建動(dòng)態(tài)主題序列；運(yùn)用快速算法統(tǒng)計(jì)真實(shí)社交網(wǎng)絡(luò)圖在δ時(shí)間戳內(nèi)生成的時(shí)序網(wǎng)絡(luò)主題個(gè)數(shù)，運(yùn)用鄰接權(quán)重矩陣表示；對(duì)δ時(shí)間戳內(nèi)相鄰的鄰接矩陣變化量運(yùn)用ω-事件隱私保護(hù)機(jī)制分配隱私預(yù)算，進(jìn)行干擾；針對(duì)干擾后的鄰接矩陣，運(yùn)用近似個(gè)性化頁(yè)面排名算法進(jìn)行隨機(jī)游走，計(jì)算社交網(wǎng)絡(luò)個(gè)體的特征向量，并對(duì)δ時(shí)間戳上社交個(gè)體的特征向量執(zhí)行掃描操作，輸出帶有最小主題的電導(dǎo)，執(zhí)行非重疊聚類劃分操作。

3.2 算法詳述

3.2.1 時(shí)序網(wǎng)絡(luò)主題

時(shí)序網(wǎng)絡(luò)主題作為時(shí)序網(wǎng)絡(luò)中的基本單位，也是理解社交網(wǎng)絡(luò)結(jié)構(gòu)和功能的局部高階子圖，時(shí)序網(wǎng)絡(luò)主題的節(jié)點(diǎn)之間包含許多帶時(shí)間戳的鏈接，以時(shí)間戳變化為基礎(chǔ)，定義時(shí)序邊，生成動(dòng)態(tài)時(shí)序網(wǎng)絡(luò)主題。對(duì)于三角網(wǎng)絡(luò)主題來(lái)說(shuō)，由3個(gè)節(jié)點(diǎn)組成的子圖結(jié)構(gòu)，其中任意一對(duì)節(jié)點(diǎn)之間至少有一條有向邊，在一個(gè)時(shí)序圖上去統(tǒng)計(jì)生成的三角網(wǎng)絡(luò)主題實(shí)例應(yīng)當(dāng)滿足（1）運(yùn)用快速靜態(tài)圖三角枚舉算法[11]去查找由時(shí)序圖[12]所誘導(dǎo)出靜態(tài)圖G中所有的三角網(wǎng)絡(luò)實(shí)例；（2）對(duì)于每一個(gè)三角節(jié)點(diǎn)(u，v，w)，合并每對(duì)節(jié)點(diǎn)的所有時(shí)序邊去獲取含有時(shí)序邊的列表。

對(duì)于三角網(wǎng)絡(luò)主題，對(duì)給定中心節(jié)點(diǎn)的所有網(wǎng)絡(luò)主題實(shí)例進(jìn)行計(jì)數(shù)，只需遍歷一次與中心節(jié)點(diǎn)相鄰的邊即可。如圖3-4所示，三角主題的三類邊形式如下，每一類都對(duì)應(yīng)三個(gè)邊上每個(gè)可能的方向。

圖4 三類主題邊

3.2.2ω-事件隱私機(jī)制的擾動(dòng)

運(yùn)用ω-事件隱私機(jī)制[10]以保護(hù)任意網(wǎng)絡(luò)主題在任何連續(xù)時(shí)間戳上的隱私信息，事件隱私機(jī)制讓主題實(shí)例M成為一種以流前綴St作為輸入的機(jī)制，并且輸出假設(shè)M可以分解為t個(gè)子機(jī)制使得 ，每一個(gè)Mi都能產(chǎn)生獨(dú)立的隨機(jī)性并實(shí)現(xiàn)εi-差分隱私。所以M滿足ω-事件隱私時(shí)，ω-事件隱私可以在大小為ω的任何滑動(dòng)窗口中設(shè)置總的隱私預(yù)算ε，并在時(shí)間戳中適當(dāng)?shù)姆峙潆[私預(yù)算的一部分。

通過(guò)算法1對(duì)時(shí)序網(wǎng)絡(luò)主題進(jìn)行計(jì)數(shù)，將節(jié)點(diǎn)之間生成的網(wǎng)絡(luò)主題個(gè)數(shù)運(yùn)用鄰接權(quán)重矩陣進(jìn)行存儲(chǔ)，矩陣中的權(quán)重表示兩節(jié)點(diǎn)生成的網(wǎng)絡(luò)主題M7的個(gè)數(shù)。選取特定時(shí)間戳上生成的基于網(wǎng)絡(luò)主題的鄰接矩陣，在時(shí)間戳為t時(shí)生成的主題鄰接矩陣表示為記為At。t+1時(shí)刻的鄰接矩陣為At+1，針對(duì)局部高階子圖從t時(shí)刻動(dòng)態(tài)演變至t+1時(shí)刻網(wǎng)絡(luò)主題鄰接矩陣的變化量為At+1-At，即At+1=At+Δt，考慮到時(shí)間戳動(dòng)態(tài)變化過(guò)程中基于網(wǎng)絡(luò)主題的邊隱私泄露情況，為鄰接矩陣的變化量Δt添加拉普拉斯噪聲進(jìn)行干擾，公式如下：

εi表示為每一時(shí)間戳δ內(nèi)生成的網(wǎng)絡(luò)主題鄰接矩陣分配的隱私預(yù)算。敏感度Δf為任意連續(xù)時(shí)間戳內(nèi)生成網(wǎng)絡(luò)主題個(gè)數(shù)變化量的最大值，也就是鄰接矩陣中權(quán)重變化量的最大值。為鄰接矩陣進(jìn)行加噪干擾的偽代碼如算法2所示：

3.2.3 基于擾動(dòng)后網(wǎng)絡(luò)主題的近似個(gè)性化頁(yè)面排名算法

近似個(gè)性化頁(yè)面排名算法基于網(wǎng)絡(luò)主題權(quán)重圖在給定種子節(jié)點(diǎn)的情況下，聚類劃分出一個(gè)帶有最小主題電導(dǎo)的集合。過(guò)程步驟如圖5所示：

圖5 局部高階聚類劃分

個(gè)性化頁(yè)面排名的向量表示一個(gè)特定隨機(jī)游走的平穩(wěn)分布，隨機(jī)游走的每一步中，都有參數(shù)隨機(jī)游走者以概率1-α傳送回特定種子節(jié)點(diǎn)u，以概率α執(zhí)行隨機(jī)游走的每一步。對(duì)其隨機(jī)游走的平穩(wěn)分布表示為其中，I是單位矩陣，P表示在圖上進(jìn)行隨機(jī)游走的列隨機(jī)轉(zhuǎn)移矩陣，eu是種子節(jié)點(diǎn)u的指示向量，形式上定義P=AD-1，A是基于時(shí)序網(wǎng)絡(luò)主題的鄰接矩陣，D=diag(Ae)是節(jié)點(diǎn)的對(duì)角度矩陣，e是所有整數(shù)的向量。

Andersen等人[13]提出一種快速的近似個(gè)性化頁(yè)面排名向量Pu通過(guò)向量其近似向量滿足式4，ξ為損失參數(shù)。

將近似個(gè)性化頁(yè)面排名算法應(yīng)用于時(shí)序網(wǎng)絡(luò)主題中，通過(guò)在時(shí)序網(wǎng)絡(luò)鄰接權(quán)重矩陣上進(jìn)行隨機(jī)游走計(jì)算近似個(gè)性化頁(yè)面排名向量劃分具有最小主題電導(dǎo)的聚簇，針對(duì)時(shí)序網(wǎng)絡(luò)主題實(shí)例M，構(gòu)建基于時(shí)序網(wǎng)絡(luò)主題的鄰接權(quán)重矩陣，對(duì)時(shí)序網(wǎng)絡(luò)主題進(jìn)行ω-事件隱私機(jī)制進(jìn)行擾動(dòng)后的鄰接權(quán)重矩陣，作為近似化頁(yè)面排名算法的輸入；針對(duì)每一時(shí)間戳上的擾動(dòng)鄰接權(quán)重矩陣進(jìn)行隨機(jī)游走，計(jì)算基于鄰接權(quán)重矩陣的近似化個(gè)性向量；執(zhí)行掃描操作輸出帶有最小主題電導(dǎo)的集合。

其中隨機(jī)游走后執(zhí)行掃描操作的步驟即，通過(guò)隨機(jī)游走計(jì)算向量的值，通過(guò)向量值降序?qū)?jié)點(diǎn)進(jìn)行排列，計(jì)算該排序列表中每個(gè)前綴的電導(dǎo)，最終輸出帶有最小主題電導(dǎo)的前綴集合。

基于以上分析，對(duì)擾動(dòng)后的基于時(shí)序網(wǎng)絡(luò)主題的鄰接矩陣進(jìn)行近似個(gè)性化隨機(jī)游走的算法步驟如算法3所示：

基于每一時(shí)間戳上擾動(dòng)后的鄰接權(quán)重矩陣，進(jìn)行隨機(jī)游走，計(jì)算節(jié)點(diǎn)的近似個(gè)性化向量，算法步驟如算法4所示：

3.3 隱私性分析

算法統(tǒng)計(jì)δ-時(shí)間戳范圍內(nèi)社交網(wǎng)絡(luò)節(jié)點(diǎn)間生成網(wǎng)絡(luò)主題的個(gè)數(shù)，將其作為ω-事件隱私機(jī)制的流輸入，ω-事件隱私機(jī)制將加噪機(jī)制M分解為t個(gè)子機(jī)制M1，…，Mt使得針對(duì)相鄰的鄰接權(quán)重矩陣Di和Di+1，使得Mi(Di)=si，輸出的每一個(gè)Mi都能產(chǎn)生獨(dú)立的隨機(jī)性并實(shí)現(xiàn)εi-差分隱私，因此對(duì)于任意算法滿足差分隱私并行組合定理。所以隱私機(jī)制M滿足ω-事件隱私當(dāng)式5成立時(shí)。

ω-事件隱私可以在大小為ω的任何滑動(dòng)窗口中計(jì)算總的隱私預(yù)算ε，并在特定時(shí)間戳范圍內(nèi)平均分配隱私預(yù)算。依據(jù)差分隱私并行組合定理2-6可以證明隨時(shí)間戳動(dòng)態(tài)變化生成的時(shí)序網(wǎng)絡(luò)主題算法滿足ω-事件ε-差分隱私。

4.實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)硬件環(huán)境為：Intel(R) Core(TM) i5-6600U CPU@ 3.30GHz，8G內(nèi)存，1T硬盤空間；軟件環(huán)境為Windows10，64位操作系統(tǒng)，VirtualBox-6.0.6，Spyder3.6；數(shù)據(jù)集分別采用了有向無(wú)權(quán)的電子郵件網(wǎng)絡(luò)[15]和來(lái)自Google+的社交網(wǎng)絡(luò)[15]。由于這兩個(gè)真實(shí)數(shù)據(jù)集節(jié)點(diǎn)和邊的數(shù)據(jù)量較大，考慮運(yùn)行時(shí)間以及運(yùn)行效率的問(wèn)題，因此只采用了數(shù)據(jù)集的部分?jǐn)?shù)據(jù)進(jìn)行實(shí)驗(yàn)。信息統(tǒng)計(jì)結(jié)果如表1所示：

表1 數(shù)據(jù)集信息統(tǒng)計(jì)表

4.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)與Andersen[13]和Chung等人[14]在社交網(wǎng)絡(luò)上實(shí)現(xiàn)局部聚類的算法進(jìn)行實(shí)驗(yàn)對(duì)比，分別運(yùn)用基于網(wǎng)絡(luò)主題的電導(dǎo)，擴(kuò)展的互信息化函數(shù)和F-度量三個(gè)評(píng)價(jià)指標(biāo)來(lái)驗(yàn)證算法的有效性。擴(kuò)展的互信息化函數(shù)（Extend Normalized Mutual Information ENMI）用于測(cè)量不同時(shí)間戳下社區(qū)劃分的準(zhǔn)確度，其值范圍在[0，1]之間，計(jì)算劃分的結(jié)果值越接近于1，劃分的社區(qū)結(jié)果效果越準(zhǔn)確。定義如下式6：

N為社交網(wǎng)絡(luò)節(jié)點(diǎn)的個(gè)數(shù)，C"代表真實(shí)的社區(qū)結(jié)構(gòu)，C"表示算法基于時(shí)序網(wǎng)絡(luò)矩陣劃分的社區(qū)結(jié)構(gòu)，Ni表示在社區(qū)C"中第i個(gè)社區(qū)的節(jié)點(diǎn)個(gè)數(shù)，Nj表示在社區(qū)C"中第j個(gè)社區(qū)的節(jié)點(diǎn)個(gè)數(shù)，因此，Nij分別表示在社區(qū)C"中第i個(gè)社區(qū)和在社區(qū)C"中第j個(gè)社區(qū)共有的節(jié)點(diǎn)個(gè)數(shù)。

F-度量（F-measure Index）又稱F-Score，用于評(píng)判不同時(shí)間戳下分配不同的隱私預(yù)算算法的聚類劃分情況。定義如下式7：

其中，精確率為Pi，召回率為Ri，N表示聚類劃分的社區(qū)個(gè)數(shù)，F(xiàn)-Score結(jié)合精確率和召回率綜合評(píng)價(jià)整體社區(qū)劃分情況。

實(shí)驗(yàn)針對(duì)2個(gè)數(shù)據(jù)集，分別選取不同數(shù)據(jù)節(jié)點(diǎn)個(gè)數(shù)，執(zhí)行近似個(gè)性化隨機(jī)游走計(jì)算的主題電導(dǎo)。email-Eu-core數(shù)據(jù)集選取的社交個(gè)體節(jié)點(diǎn)分別為20，40，60，80，100，120，140，隨機(jī)游走后計(jì)算的主題電導(dǎo)如圖3-8所示。因?yàn)閑go-Gplus數(shù)據(jù)集數(shù)據(jù)量較大，則取2500，5000，7500，10000，12500，15000，17500，20000，隨機(jī)游走后執(zhí)行掃描操作計(jì)算的主題電導(dǎo)如圖7所示。

圖6 email-Eu-core數(shù)據(jù)集主題電導(dǎo)

圖6，7表示的是特定數(shù)據(jù)集節(jié)點(diǎn)在不同時(shí)間戳下生成主題實(shí)例M進(jìn)行隨機(jī)游走計(jì)算主題電導(dǎo)的均值情況，分別選取δ時(shí)間戳取值范圍為5，10，15，20，25，30（單位為秒）。對(duì)于email-Eu-core數(shù)據(jù)集，通過(guò)多次試驗(yàn)對(duì)比，在δ時(shí)間戳內(nèi)生成網(wǎng)絡(luò)主題實(shí)例頻數(shù)最高的是M1，M2，M3，并且這三個(gè)網(wǎng)絡(luò)主題實(shí)例分別在社交個(gè)體節(jié)點(diǎn)為80時(shí)，計(jì)算的主題電導(dǎo)最小，依據(jù)主題電導(dǎo)原理進(jìn)行聚類劃分效果最好，因此，選取社交個(gè)體節(jié)點(diǎn)為80時(shí)評(píng)估不同時(shí)間戳下社區(qū)劃分的準(zhǔn)確率。

同理，圖7表示ego-Gplus數(shù)據(jù)集統(tǒng)計(jì)不同社交節(jié)點(diǎn)下生成的主題電導(dǎo)，ego-Gplus數(shù)據(jù)集在δ時(shí)間戳內(nèi)生成的頻數(shù)最高的網(wǎng)絡(luò)主題實(shí)例為M7，M6，M3，M1，綜合分析這四種網(wǎng)絡(luò)主題實(shí)例在節(jié)點(diǎn)為10000時(shí)主題電導(dǎo)最小，聚類效果最好，所以選取節(jié)點(diǎn)數(shù)為10000進(jìn)行社區(qū)劃分的對(duì)比實(shí)驗(yàn)。

圖8 email-Eu-core數(shù)據(jù)集

圖8表示email-Eu-core數(shù)據(jù)集基于主題實(shí)例M2，M3進(jìn)行聚類劃分的對(duì)比實(shí)驗(yàn)。分別運(yùn)用文獻(xiàn)[13][14]中提出的隨機(jī)游走算法與近似個(gè)性化頁(yè)面排名算法進(jìn)行對(duì)比，可知在時(shí)間戳為15，20時(shí)聚類劃分的準(zhǔn)確率最高。綜合分析，在不同時(shí)間戳下，近似個(gè)性化頁(yè)面排名算法較其他兩種算法有較高的效用性。

圖9 ego-Gplus數(shù)據(jù)集

圖9表示ego-Gplus數(shù)據(jù)集基于主題實(shí)例M7，M6進(jìn)行聚類劃分的對(duì)比試驗(yàn)，由于主題實(shí)例M7是最具代表社交網(wǎng)絡(luò)的局部高階子圖，從圖4-4中可知運(yùn)用實(shí)例M7進(jìn)行社區(qū)聚類劃分，準(zhǔn)確率最高可達(dá)到0.9左右，相比較圖4-4中M2，M3實(shí)例有明顯優(yōu)勢(shì)。

圖10表示email-Eu-core數(shù)據(jù)集基于網(wǎng)絡(luò)主題實(shí)例M2分配隱私預(yù)算的情況，依據(jù)圖10中a），b）得知，針對(duì)不同頁(yè)面排名算法，對(duì)于同一網(wǎng)絡(luò)主題實(shí)例，在相同時(shí)間戳下對(duì)鄰居權(quán)重矩陣分配隱私預(yù)算進(jìn)行干擾，分配的隱私預(yù)算越小，產(chǎn)生的誤差越大，因此聚類劃分的準(zhǔn)確性越低。

圖11表示ego-Gplus數(shù)據(jù)集基于網(wǎng)絡(luò)主題實(shí)例M7分配隱私預(yù)算的情況，執(zhí)行近似化個(gè)性頁(yè)面排名算法之后，針對(duì)同一網(wǎng)絡(luò)主題實(shí)例M7，在時(shí)間戳為15的情況下，隱私預(yù)算分配0.5的F-score值為0.57，當(dāng)隱私預(yù)算分配0.75時(shí)F-score值為0.63，表明同一條件下，隱私預(yù)算越大，產(chǎn)生的噪聲越小，對(duì)比實(shí)驗(yàn)的聚類準(zhǔn)確度越高。

圖10 email-Eu-core數(shù)據(jù)集網(wǎng)絡(luò)主題實(shí)例為M2

圖11 ego-Gplus數(shù)據(jù)集網(wǎng)絡(luò)主題實(shí)例M7