基于局部高階子圖的差分隱私保護社區發現算法

侯小軍，李澤華，邊 錦

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

1.緒論

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

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

2.基礎理論與相關工作

2.1 基礎理論

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

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

定義3（局部高階子圖（Motif）[3]）社交網絡豐富的高階組織結構通過高階鏈接模式的聚類從而表現出來，最普通的局部高階子圖為小網絡子圖，稱為網絡基序（主題），被認為是復雜網絡的構建塊，如圖1所示。

圖1 局部高階子圖

定義4（主題電導—Motif Conductance[4]）對于一個網絡主題實例M的主題電導定義如下：

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

圖2 主題電導及劃分

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

圖3 時序圖

2.2 相關工作

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

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

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

3.基于局部高階子圖的隱私保護社區發現算法

3.1 算法簡述

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

3.2 算法詳述

3.2.1 時序網絡主題

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

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

圖4 三類主題邊

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

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

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

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

3.2.3 基于擾動后網絡主題的近似個性化頁面排名算法

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

圖5 局部高階聚類劃分

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

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

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

其中隨機游走后執行掃描操作的步驟即，通過隨機游走計算向量的值，通過向量值降序對節點進行排列，計算該排序列表中每個前綴的電導，最終輸出帶有最小主題電導的前綴集合。

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

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

3.3 隱私性分析

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

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

4.實驗結果與分析

4.1 實驗環境

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

表1 數據集信息統計表

4.2 實驗結果分析

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

N為社交網絡節點的個數，C"代表真實的社區結構，C"表示算法基于時序網絡矩陣劃分的社區結構，Ni表示在社區C"中第i個社區的節點個數，Nj表示在社區C"中第j個社區的節點個數，因此，Nij分別表示在社區C"中第i個社區和在社區C"中第j個社區共有的節點個數。

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

其中，精確率為Pi，召回率為Ri，N表示聚類劃分的社區個數，F-Score結合精確率和召回率綜合評價整體社區劃分情況。

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

圖6 email-Eu-core數據集主題電導

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

同理，圖7表示ego-Gplus數據集統計不同社交節點下生成的主題電導，ego-Gplus數據集在δ時間戳內生成的頻數最高的網絡主題實例為M7，M6，M3，M1，綜合分析這四種網絡主題實例在節點為10000時主題電導最小，聚類效果最好，所以選取節點數為10000進行社區劃分的對比實驗。

圖8 email-Eu-core數據集

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

圖9 ego-Gplus數據集

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

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

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

圖10 email-Eu-core數據集網絡主題實例為M2

圖11 ego-Gplus數據集網絡主題實例M7