[發明專利]Spark下基于標簽傳播的并行重疊社區發現方法

在審

• 申請號: 201710121328.2
• 申請日: 2017-03-02
• 公開（公告）號: CN106991614A
• 公開（公告）日: 2017-07-28
• 發明（設計）人: 馬廷淮;岳明亮;薛羽;曹杰
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 江蘇愛信律師事務所32241
• 代理人: 唐小紅

1.Spark下基于標簽傳播的并行重疊社區發現方法，其特征在于，包括以下步驟：

步驟1)由網絡數據集，設計map和reduce函數，得到節點的鄰接列表，計算節點的度并降序排列；

步驟2)由步驟1)得到的由節點的度降序排列的列表，依次選取節點，在網絡中尋找完全子圖，最終得到k個完全子圖g₁，g₂，…g_k，將每個完全子圖中的節點都分配一個相同的標簽，網絡中剩下的節點分配一個唯一的標簽；

步驟3)根據步驟2)得到的完全子圖，計算網絡中節點的權重；首先為網絡中的節點分配一個初始權重W₁＝1；其次計算節點與完全子圖的距離，處于完全子圖中的節點距離D＝0，不屬于完全子圖并且與完全子圖中節點有邊相連的節點距離D＝1，依次類推，計算權重W₂＝2^D；最后計算節點自身的權重d為節點的度數，d_max為網絡中節點的最大度數；綜合這3個權重，計算網絡中節點的權重；

步驟4)根據網絡中的傳播特性，即越重要的節點越容易將自己的標簽傳播給周圍的節點，由步驟3)得到的節點的權重計算節點間標簽傳播的概率；每個節點得到一個鄰接節點概率列表；

步驟5)根據步驟4)得到的節點間標簽傳播概率列表，結合節點間的相似度，確定節點選擇的標簽列表；當網絡中的標簽數目不再發生變化時停止迭代，此時，每個節點擁有的標簽就是它們所屬的社區。

2.根據權利要求1所述的方法，其特征在于，步驟1)由網絡數據集，設計map和reduce函數，這里的map函數將邊映射為一個二元組(a，b),代表節點a與節點b之間有一條邊相連；reduce函數將二元組的第一個元素作為key進行規約，最終得到節點的鄰接列表，并以此計算節點的度并降序排列。

3.根據權利要求1所述的方法，其特征在于，步驟2)根據步驟1)得到的由節點的度降序排列的列表，依次選取節點，在網絡中尋找完全子圖，最終得到k個完全子圖g₁，g₂，…g_k，將每個完全子圖中的節點都分配一個相同的標簽，網絡中剩下的節點分配一個唯一的標簽。

4.根據權利要求1所述的方法，其特征在于，步驟3)根據步驟2)得到的完全子圖，計算網絡中節點的權重；首先為網絡中的節點分配一個初始權重W₁＝1；其次計算節點與完全子圖的距離，處于完全子圖中的節點距離D＝0，不屬于完全子圖并且與完全子圖中節點有邊相連的節點距離D＝1，依次類推，計算權重W₂＝2^D；最后計算節點自身的權重d為節點的度，d_max為網絡中節點的最大度；綜合這3個權重，計算網絡中節點的權重；計算的公式如下：

W＝λ/3(W₁+W₂+W₃)

其中λ為放大因子，是一個可調參數，節點的權重取值范圍為(0,λ]。