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

侯小軍，李澤華，邊 錦

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

1.緒論

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

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

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

2.1 基礎(chǔ)理論

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

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

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

圖1 局部高階子圖

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

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

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

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

圖3 時序圖

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

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

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

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

3.1 算法簡述

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

3.2 算法詳述

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

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

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

圖4 三類主題邊

3.2.2ω-事件隱私機制的擾動

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

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

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

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

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

圖5 局部高階聚類劃分

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

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

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

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

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

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

3.3 隱私性分析

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

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

4.實驗結(jié)果與分析

4.1 實驗環(huá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ù)集分別采用了有向無權(quán)的電子郵件網(wǎng)絡(luò)[15]和來自Google+的社交網(wǎng)絡(luò)[15]。由于這兩個真實數(shù)據(jù)集節(jié)點和邊的數(shù)據(jù)量較大，考慮運行時間以及運行效率的問題，因此只采用了數(shù)據(jù)集的部分數(shù)據(jù)進行實驗。信息統(tǒng)計結(jié)果如表1所示：

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

4.2 實驗結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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