[發明專利]一種基于差分隱私的地理分布式圖計算方法及系統

有效

• 申請號: 202010518901.5
• 申請日: 2020-06-09
• 公開（公告）號: CN111914285B
• 公開（公告）日: 2022-06-17
• 發明（設計）人: 周池;邱銳波;張嘉睿;毛睿
• 申請（專利權）人: 深圳大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;H04L9/40
• 代理公司: 北京三聚陽光知識產權代理有限公司 11250
• 代理人: 劉靜

本發明公開了基于差分隱私的地理分布式圖計算方法及系統，基于差分隱私利用預設處理模型對地理分布圖進行圖計算，按指數分配機制對每輪迭代分配預算；在DC中增加聚合器收集需要發送向相鄰DC數據，將其全部加起來加上本輪迭代對應的噪音平均劃分發送給相鄰的DC；各DC接收上輪迭代后其他DC發送的數據更新頂點的有效值，重復在DC中增加聚合器來收集需要發送向相鄰DC的數據，將其全部加起來加上本輪迭代對應的噪音平均劃分發送給相鄰的DC的步驟，直至達到收斂條件迭代結束；各DC按照達到收斂條件的處理模型進行分布式圖間的數據傳輸。本發明通過減小噪音的引入而不影響保護效果，提高迭代的收斂能力，同時大大提高了數據的可用性。

技術領域

本發明涉及大規模圖分割處理領域，具體涉及一種基于差分隱私的地理分布式圖計算方法及系統。

背景技術

在地理分布式的數據中心(DC：Data Center)上進行圖處理時，為了保護個人隱私，可以應用差分隱私技術。差分隱私是一種經過嚴格證明的能夠保護個人隱私的差分技術，它通過在不同DC之間的通信上加隨機噪音(noise)的方法來實現差分隱私。這個隨機的noise的大小主要是由兩個參數決定的，一是隱私預算(budget)，一是敏感度(sensitivity)。budget的大小與隱私保護效果、noise的大小之間的關系是這樣的：budget越大，所加入的noise越小，保護效果越差；budget越小，加入的noise越大，保護效果越好。這里所說的budget是指總的budget大小，對于計算過程具有迭代特征的應用(PageRank、sssp等)，還需要把這個budget按照某種規則分配給每個迭代過程，然后在具體的每次迭代中再細分給各個頂點。現有技術存在的主要問題有兩個：1、對于具有迭代特征的某些應用差分隱私技術時由于noise太大而難以收斂；2、應用了差分隱私之后由于noise的影響實驗結果數據可用性較低。

發明內容

因此，本發明提供一種基于差分隱私的地理分布式圖計算方法及系統，要解決的技術問題在于克服現有技術中地理分布式圖計算時，對于具有迭代特征的某些應用差分隱私技術時由于noise太大而難以收斂，或應用差分隱私之后由于noise的影響實驗結果數據可用性較低的缺陷。

為達到上述目的，本發明提供如下技術方案：

第一方面，本發明實施例提供一種基于差分隱私的地理分布式圖計算方法，包括如下步驟：基于差分隱私利用預設處理模型對地理分布圖進行圖計算，按照指數分配機制對地理分布圖中每一輪迭代分配預算；

在數據中心中增加聚合器來收集需要發送向相鄰數據中心的數據，并將其全部加起來加上本輪迭代對應的噪音，再平均劃分后發送給相鄰的數據中心；

各數據中心接收上一輪迭代后其他數據中心發送的數據，并更新頂點的有效值，并重復所述在數據中心中增加聚合器來收集需要發送向相鄰數據中心的數據，并將其全部加起來加上本輪迭代對應的噪音，再平均劃分后發送給相鄰的數據中心的步驟，直至達到預設收斂條件，迭代結束；各個數據中心按照達到預設收斂條件的處理模型，進行地理分布式圖之間的數據傳輸。

在一實施例中，在數據中心中增加聚合器來收集需要發送向其他數據中心的消息的步驟之前，還包括：

在某輪迭代中丟棄所有頂點，按照預設重新采樣公式得到的概率對所有頂點進行重取樣之后，取樣成功的頂點將會分配給其應歸屬的聚合器。

在一實施例中，各個頂點有效值的獲取方式包括：最短單源路徑算法或PageRank算法；當通過最短單源路徑算法獲取時，各個頂點的有效值為最短路徑長度；當通過PageRank算法獲取時，各個頂點的有效值為rank值。

在一實施例中，重取樣概率公式為：

式中，rank代表本輪迭代中某個頂點的有效值；

n表征頂點的初始有效值。