[發明專利]一種基于節點結構特征的社交網絡去匿名化方法

在審

• 申請號: 201711203750.9
• 申請日: 2017-11-27
• 公開（公告）號: CN107945037A
• 公開（公告）日: 2018-04-20
• 發明（設計）人: 段大高;高陽;韓忠明;莫倩
• 申請（專利權）人: 北京工商大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 北京慧泉知識產權代理有限公司11232
• 代理人: 王順榮,唐愛華

技術領域

本發明涉及一種基于節點結構特征的社交網絡去匿名化的方法，它應用于社交網絡中匿名化用戶的識別，屬于數據挖掘技術領域。

背景技術

近年來，論壇、微博和博客等社會網絡平臺的增加為社會網絡數據的商業化應用鋪平了道路，然而，除了合法的利用，一些非法的濫用也隨之增多。同時，隨著社會網絡平臺深度融合到我們的日常生活中，也給了政府一個很好的提高監察能力的機會。這種用戶和商業組織的權利不平衡和政府對隱私監督問題的持續督促促進了社會網絡相關的積極應用。

本發明考慮的問題是如何僅僅利用網絡的圖結構來匹配不同社會網絡中的同一用戶，從而導致用戶隱私的泄露。更具體的是，我們關注的是大規模網絡用戶的再識別，即將兩個大規模網絡中的用戶關聯起來從而將其中一個網絡去匿名化。結果是，匿名圖中的每一個節點都可能關聯到另一個網絡中的某一個已知身份的節點。也就意味匿名圖中的節點的身份被識別或者稱為被去匿名化。去匿名化有很多目的，比如，一個商業組織受利益的驅使購買匿名的數據集用于去匿名化為了利用新數據更新它之前已有的記錄。同時，將一些社交網絡聯合起來對于政府機構也是有很大價值的(比如郵件和電話網絡)。

目前對于去匿名化的研究多從網絡的拓撲結構出發，雖然細節上有一些差異，但是通常包含兩個依次的執行過程。第一個階段是初始化階段(種子階段，全局比較)，另一個是用迭代的方法進行再識別的過程(傳播階段，局部比較)。

發明內容

1、目的：本發明目的是提供一種基于圖結構，在擁有輔助圖的基礎上將匿名化網絡中節點與輔助圖中屬于同一用戶的節點匹配出來，從而達到去匿名化的方法本發明的原理是：將用戶和用戶間的關系抽象為網絡拓撲結構中的節點和連邊形成社會網絡拓撲圖。以圖為對象，一個圖中節點身份信息已知作為輔助圖，另外一個圖中節點身份信息未知作為匿名圖，首先根據已有的方法獲取到種子節點即已經匹配出的節點作為匹配集，然后迭代的進行傳播過程。迭代過程根據節點的共同鄰居數和節點各自的度值來度量節點之間的相似度。將相似度最大的節點對關聯起來。傳播過程直到沒有新的節點被匹配出來，結束去匿名化過程。

2、技術方案：本發明一種基于節點結構特征的社交網絡去匿名化方法，包括步驟如下：

步驟一：數據獲取及處理:

構造以社會網絡中用戶為節點,連接關系為連邊的社會網絡拓撲結構G：用G＝(V,E),V是G中所有節點的集合,E是所有連邊的集合；其中|V|＝n、|E|＝m,表示G中有n個節點m條邊；用鄰接矩陣A表示網絡節點間的連通關系；G＝(V,E)中節點個數為n，節點依次標記為Vi(i＝1,2,3……n)；若節點Vi和Vj之間有邊相連，則Aij＝1，若節點Vi和Vj之間無邊相連，則Aij＝0。

其中，輔助圖定義為Gsrc＝(Vsrc，Esrc)，Vsrc為已知圖中的節點；Esrc是已知圖中的邊，|Vsrc|為Gsrc中節點個數。匿名圖定義為Gtar＝(Vtar，Etar)。Vtar是匿名圖中的節點；Etar是匿名圖中的邊。|Vtar|為Gtar中節點個數。定義表示在兩個網絡中共同存在的節點。

步驟二：確定種子節點，作為最初的匹配集合μ(也稱為種子集合)。本發明采用的獲取種子節點的方法是在兩個網絡中選取度值(度值為節點連接的邊的數目，)最高的一部分節點，通過人工標注的方法匹配出種子節點集。種子節點定義為u：Vsrc→Vtar，(→表示Gsrc中的節點Vsrc與Gtar中的Vtar相匹配，屬于同一用戶)。

步驟三：根據匹配集合μ，開始迭代的傳播過程，直到沒有新的匹配可以被添加。傳播過程如下：

(1)迭代選取輔助圖Gsrc中某一節點Vi∈Vsrc(i＝1，2……n；n＝|Vsrc|)，然后依次選取節點Vi的鄰居節點集合Ni(Ni表示節點i的鄰居節點集合，Ni＝{j,Aij＝1且j∈Vsrc})中每個元素,通過匹配集合μ判斷出Ni中已經匹配出的節點Vi′和匿名網絡Gtar中對應于Vi′的匹配節點Vj′∈Vtar。再找到Vj′的鄰居節點集合Nj′，Nj′中的元素Vj作為候選節點。然后根據相似度公式(1)計算Vi和所有可能候選節點vj之間的相似度。式中(Vi∩Vj)表示Vi和Vj共有的已匹配鄰居節點數，|Vi|，|Vj|表示節點Vi、Vj的度值。n和m分別為Gsrc何Gtar中節點的總個數，即n＝|Vsrc|，m＝|Vtar|；公式(1)為相似度度量方法；

其中，i＝1，2……n；j＝1，2……m；