[發明專利]一種基于差分隱私的局部高階圖聚類方法

在審

• 申請號: 201910490628.7
• 申請日: 2019-06-06
• 公開（公告）號: CN110263831A
• 公開（公告）日: 2019-09-20
• 發明（設計）人: 李蜀瑜;邊錦;曹菡
• 申請（專利權）人: 陜西師范大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 西安睿通知識產權代理事務所(特殊普通合伙) 61218
• 代理人: 惠文軒

本發明公開了一種基于差分隱私的局部高階圖聚類方法，該方法的具體步驟為：利用局部高階網絡子圖Motif的結構，將原始社交網絡轉化成基于Motif的鄰接矩陣，基于Motif網絡子圖結構的多樣性，對生成的Motif鄰接矩陣中的權重設置一定的閾值，并對在閾值范圍內的權重進行拉普拉斯噪聲擾動，實現對社交網絡子圖的隱私保護；為了提升隨機游走算法運行的效率，采用近似熱核頁面排名種子算法，對擾動后的Motif矩陣進行隨機游走，根據游走后的熱核向量計算劃分集合的切割比，并輸出聚類集合。

技術領域

本發明屬于數據安全技術領域，特別涉及一種基于差分隱私的局部高階圖聚類方法。

背景技術

隨著博客、微博等社交媒體的興起，以用戶為節點、以用戶關系為邊的社交網絡迅猛增長。用戶的興趣、行為、功能等關系使社交網絡中存在多個社區或簇。其高效的聚類方法，使用戶更高效的了解自己所在社區的親密程度，但在聚類的過程中，存在侵犯用戶隱私的風險。一方面，用戶擔心在聚類過程中包含太多內容，會泄露自己的隱私信息；另一方面，對社交用戶進行社區劃分時依據網絡子圖特點存在很多不確定因素，限制其技術改進的能力；因此，處理隱私數據通常需要考慮數據可用性與隱私保護之間的平衡。

在整個圖聚類過程中，社交網絡作為圖數據的重要組成部分，被廣泛應用于各種聚類方法中，聚類通過網絡的有向性、高階子圖的結構特性等低級特征，節點鏈接稠密關系、節點功能特性等高級特征，然后對網絡節點進行聚劃分，計算同一子集向量的切割比(Cheeger ratio)，最終通過劃分子集的Cheeger ratio進行最優切割；但是，當前基于高階子圖的聚類劃分并沒有對數據進行隱私保護，進而可能會導致網絡數據的泄露，無法保證用戶數據的安全性。

發明內容

針對上述現有技術存在的隱私保護問題，本發明的目的在于提出一種基于差分隱私的局部高階圖聚類方法，本發明采用社交網絡子圖的結構特性及差分隱私設計了一種隱私保護模型，基于熱核頁面排名隨機游走原理，通過限制隨機游走的步數，解決了復雜社交網絡局部高階圖的聚類問題；在具體改進中，基于社交網絡子圖的結構，首先將原始社會網絡轉化為基于網絡子圖的Motif權重矩陣，然后通過構建的Motif權重矩陣，來確定對Motif權重矩陣的隱私保護力度；最后采用近似熱核頁面排名種子算法對擾動后的Motif權重矩陣進行隨機游走，使得社交網絡在隱私保護的前提下，依然能夠有良好的聚類結果。

本發明的技術原理：利用局部高階網絡子圖Motif的結構，將原始社交網絡轉化成基于Motif的鄰接矩陣，基于Motif網絡子圖結構的多樣性，對生成的Motif鄰接矩陣中的權重(節點之間生成Motif的個數)設置一定的閾值，并對在閾值范圍內的權重運用拉普拉斯機制進行噪聲擾動，實現對社交網絡子圖的隱私保護；為了提升隨機游走算法運行的效率，采用近似熱核頁面排名種子算法，對擾動后的Motif矩陣進行隨機游走，根據游走后的熱核向量計算劃分集合的切割比，并輸出聚類集合。

為了達到上述目的，本發明采用以下技術方案予以解決。

一種基于差分隱私的局部高階圖聚類方法，包括以下步驟：

步驟1，獲取社交網絡數據集，即有向圖G(V，E)，選取三角Motif模型中的M₇連接結構，作為有向圖G(V，E)的高階網絡子圖Motif結構；構建Motif鄰接矩陣，權重矩陣W_M；采用差分隱私算法，對有向圖的Motif權重矩陣中Motif結構個數進行干擾，得到具有隱私保護的有向圖G_λ′。

其中，V為節點集，E為邊集。

子步驟1.1，構建Motif權重矩陣W_M，其具體為：計算有向圖G(V，E)中從節點v_i到節點v_j之間的所有路徑中生成的Motif結構的數量，并將其作為鄰接矩陣中對應節點之間的權重w，生成Motif權重矩陣W_M。