[發明專利]一種基于多標簽傳播的重疊社區檢測方法

有效

• 申請號: 201510076028.8
• 申請日: 2015-02-12
• 公開（公告）號: CN104636978B
• 公開（公告）日: 2017-11-14
• 發明（設計）人: 董學文;楊超;盛立杰;王超;姚青松;蔣中元;孫聰
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 西安通大專利代理有限責任公司61200
• 代理人: 徐文權

1.一種基于多標簽傳播的重疊社區檢測方法，其特征在于，包括以下步驟：步驟A，構造社交網絡圖：讀取網絡數據，構造以用戶為節點，用戶關系為邊的社交網絡圖；

步驟B，分析網絡粗糙核心：根據社交網絡圖，以及各節點的度，分析出社交網絡的粗糙核心集合RoughCore；

步驟C，初始化標簽集合：計算社交網絡中各邊兩節點的結構權值，結合步驟B所得RoughCore結果，初始化各節點的標簽集合，并判斷各節點核心狀態CoreStatus；

步驟D，執行標簽傳播：在整個社交網絡中根據鏈接密度，計算各節點新標簽集合，同時根據節點核心狀態CoreStatus對較小隸屬度標簽進行過濾，得到初步重疊社區結果；

步驟E，分解不連續社區：在初步重疊社區結果里將不連續社區分解為多個子社區，得到最終的社交網絡重疊社區結構。

2.根據權利要求1所述的一種基于多標簽傳播的重疊社區檢測方法，其特征在于，所述步驟B的分析網絡粗糙核心包括如下步驟：

步驟B1，將網絡各節點按照度數進行排序，得到排序后的節點集合vSetvSet；

步驟B2，從節點集合vSet中選擇度數最大的節點X，并在從屬于vSet中的X的鄰居節點中選擇度數最大的節點Y，將節點X、Y加入到空集合core中；

步驟B3，在core中節點的公共鄰居集合中，選擇度數最小的節點Z，將Z加入到core中；

步驟B4，循環執行B3，直至core中節點的公共鄰居節點為0；

步驟B5，若core中節點數大于等于3，則該core中節點組成一個粗糙核心，并從vSet中刪除core中所有節點；若core中節點數小于3，則從vSet中刪除節點X；

步驟B6，繼續執行步驟B2，直至vSet集合為空，得到社交網絡的粗糙核心集合。

3.根據權利要求2所述的一種基于多標簽傳播的重疊社區檢測方法，其特征在于，所述步驟C的初始化標簽集合具體包括如下步驟：

步驟C1，首先對網絡利用結構權值描述網絡中鏈接密度，計算各邊(x，y)的兩節點的結構權值sw(x,y)=|τ(x)∩τ(y)||τ(x)∪τ(y)|·kx+ky2*kmax,]]>

其中τ(x)表示節點x的鄰域，包含x和x的鄰居節點，k_x表示節點x的度；

步驟C2，初始化數組source和coreStatus，對于網絡中的每個節點x，設置source.x為空集，coreStatus.x為1；

其中source存儲各個節點標簽集合，每個標簽由(社區標記comId，隸屬度b)組成；coreStatus存儲各個節點的核心狀態，值越大表示越處于核心位置；

步驟C3，對于RoughCore中每個節點x及其鄰居節點集合N(x)的每個節點y，識別其標簽數并確定core Status，然后對網絡中每個節點的標簽集合進行歸一化，保證每個節點的所有隸屬度之和為1。