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

有效

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

技術領域

本發明屬于網絡數據挖掘技術領域，具體涉及一種基于多標簽傳播的重疊社區檢測方法。

背景技術

數據挖掘(Data Mining)是指從大量數據中提取隱含的、未知的、有潛在應用價值的信息或模式的過程。對網絡社區結構進行挖掘，能夠發現網絡中隱含的組織結構信息、社會功能以及社區成員之間隱含的有趣屬性，如共同愛好等。通過研究社會網絡中社區之間、個體之間以及個體與社區之間的關系，可以挖掘出大量有價值的信息，可應用于許多領域。

在過去十年中，已經出現了一系列的社區檢測算法。這些算法可以分為如下幾類：基于密度的社區檢測方法、基于圖論的社區檢測方法、基于模塊度優化的聚類算法、基于標簽傳播的社區檢測方法等等。

DBSCAN是一種代表性的基于密度的社區檢測算法，可在含噪聲的空間數據集中快速發現密度超過給定閾值的任意形狀聚類.但是，它把參數Eps和MinPts的設置任務留給用戶，且算法對參數Eps較為敏感。基于圖論的Chameleon聚類算法將矢量數據建模為圖，通過引入互連性和近似性兩個指標來控制簇的分裂和合并，可以發現高質量的任意形狀社區。2004年Newman和Grivin提出模塊度函數用以評估社團聚類質量。模塊度定義為簇內實際連接數目與隨機連接情況下簇內期望連接數目之差,用來定量地刻畫網絡簇結構的優劣。研究人員提出一些基于模塊度優化的算法，如FastModularity。近年來，研究人員開始利用同步技術進行社區檢測算法的研究。同步是自然、社會、工程中普遍存在的現象，表現為不同的進程對于時間的一致性。研究人員提出一些能有效捕捉同步動力過程的模型，如廣義Kuramoto模型。受同步現象啟發，等提出了一種基于同步原理的社區檢測算法Sync，利用同步動力模型來探測數據集中的聚類。給定一個鄰域半徑，一個對象在以自身為圓心的一個超球形鄰域內的所有鄰居對象的同步作用下產生位移。在非線性作用力的影響下，相近的對象將會同步達到相同的相位并形成社區。

Raghavan等提出標簽傳播方法用于社區發現，該算法具有線性時間復雜度，但是只能用于非重疊社區發現。Steve Gregory提出COPRA算法將標簽傳播技術應用到重疊社區挖掘領域，之后武志昊等又提出一種平衡的多標簽重疊社區檢測算法BMLPA算法。陳羽中等人申請專利“一種社交網絡中的多標簽傳播重疊社區發現方法”，采用綜合考慮節點中心度以及標簽度分布約束的標簽傳播方法進行社區發現，同時在標簽傳播過程中計算不同層級節點之間的標簽傳播增益。上述多標簽傳播方法均存在需手動輸入參數，以及未考慮節點間鏈接密度等缺點。

發明內容

本發明的目的在于針對現有技術存在的缺陷和不足，提供一種基于多標簽傳播的重疊社區檢測方法，解決現有多標簽傳播方法需要手動輸入參數，以及未考慮節點間鏈接密度等問題。

為實現上述目的，本發明采用以下技術方案：包括以下步驟：步驟A，構造社交網絡圖：讀取網絡數據，構造以用戶為節點，用戶關系為邊的社交網絡圖；

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

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

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

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

進一步的，所述步驟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；