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

在審

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

1.一種基于節點結構特征的社交網絡去匿名化方法，其特征在于，包括步驟如下：

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

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

輔助圖定義為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)為相似度度量方法；

SIM(Vi,Vj)=(Vi∩Vj)(1|Vi|+|Vj|-(Vi∩Vj))1/2---(1)]]>

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

(2)通過上一步得到相似度值最大的節點Vm,為了提高準確率采用反向傳播相似度驗證以修正因種子用戶不足造成的錯誤匹配用，反向傳播即用同樣的相似度度量方法找到Vm在Gsrc中的相似度最大的節點；如果Vm在Gsrc中的相似度最大的節點是Vi，則把Vi與Vm相匹配；加入匹配集合μ中；如果Vm在Gsrc中的相似度最大的節點不是Vi，則不添加；

(3)遍歷Gsrc中的節點Vi∈Vsrc，執行步驟三的過程，直到沒有新的匹配節點添加入匹配集合μ中；其中，i＝1，2……n；n＝|Vsrc|；

步驟四：輸出匹配集合μ中的節點對。