[發明專利]一種基于Louvain算法的社區發現方法及系統

在審

• 申請號: 201810290415.5
• 申請日: 2018-04-03
• 公開（公告）號: CN108509607A
• 公開（公告）日: 2018-09-07
• 發明（設計）人: 李果;鐘金順;李永杰;王曉嘎;宋敏峰
• 申請（專利權）人: 三盟科技股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 胡楓

本發明公開了一種基于Louvain算法的社區發現方法，包括：S1，初始化社區，把每個節點作為一個社區；S2，將每個節點依次分配到每個鄰居節點所在社區以構建社區圖形；S3，根據社區圖形把社區看作一個節點，重新構建社區圖形；S4，重復步驟S3，直到所有狀態穩定，則輸出結果。本發明還公開了一種基于Louvain算法的社區發現系統。采用本發明，將網絡中的每個節點當作社區，并針對社區的模塊度和邊權重分析，從而可以得到更加精準的社區發現。

技術領域

本發明涉及數據挖掘技術領域，尤其涉及一種基于Louvain算法的社區發現方法及一種基于Louvain算法的社區發現系統

背景技術

隨著信息化技術的發展，信息系統中保存著大量用戶的信息特征，用戶與用戶之間也存在著某種關聯性。用戶的特征具有多維度，且多關聯性。社區發現能幫助人們更有效地了解網絡的結構特征，從而提供更有效、更具個性化的服務。

當前，許多研究通過分析網絡的結構來發現社區。其中，Blondel等人基于現實中的大規模網絡的社區結構都具有層次性，提出了一種迭代的兩階段模塊度最大化的快速算法(BGL算法)用于發現社區。該算法分為兩步：第一步、通過社區之間局部交換節點使得社區劃分的模塊度最大化。第二步、將前一步網絡劃分產生的社區作為新的網絡中的一個節點，節點之間邊的權值為其代表的兩個社區之間的邊的權值之和。反復迭代以上兩個步驟，直到模塊度的大小不再可能增加。BGL算法所使用的模塊度度量標準如下式所定義，該定義適用于加權網絡：

其中，A_ij表示節點i和節點j之間的邊的權重；k_i＝∑_jA_ij表示與節點i相連的所有邊的權值之和；c_i表示節點i所在的(所屬的)社區；δ函數δ(u，v)表示當u與v相等時為1，而其余情況下為0；表示網絡中所有邊的權值之和。

然而，BGL算法沒有涉及到網絡節點的屬性信息。而研究表明，在真實的在線社交網絡中，節點的屬性信息可以是判斷的標準之一，在結構緊密的前提下，同一社區內的節點屬性越相似越好。除此之外，雖然現有的很多聚類方法已將網絡的結構和節點的屬性特征(或稱節點屬性或節點屬性信息)結合起來考慮(例如，通過對屬性和結構進行加權的方法構造新的網絡，并在新的網絡上進行社區劃分)，但是這些聚類的結果往往存在結構上并不緊密或者不關聯的社區，從而導致社區發現的結果不準確；而且，這些方法的時間復雜度較高，不適于處理大規模的數據。

發明內容

本發明所要解決的技術問題在于，提供一種基于Louvain算法的社區發現方法及系統，可將網絡中的每個節點當作社區，并針對社區的模塊度和邊權重分析，從而可以得到更加精準的社區發現。

為了解決上述技術問題，本發明提供了一種基于Louvain算法的社區發現方法，包括：

S1，初始化社區，把每個節點作為一個社區；

S2，將每個節點依次分配到每個鄰居節點所在社區以構建社區圖形；

S3，根據社區圖形把社區看作一個節點，重新構建社區圖形；

S4，重復步驟S3，直到所有狀態穩定，則輸出結果。

作為上述方案的改進，所述步驟S2包括：將每個節點，依次嘗試分配到每個鄰居節點所在社區；計算分配前與分配后的模塊度變化量；提取模塊度變化量的最大值；若模塊度變化量的最大值大于0，則將節點分配到該社區，一直重復這個步驟，直到所有節點不再變化，形成社區圖形。

作為上述方案的改進，所述重新構建社區圖形的方法包括：把社區內節點度數和，轉化為新節點到自己的環路的權重；把社區間的邊權重轉化為新節點間的邊權重；重復步驟S2。

作為上述方案的改進，所述步驟S3之前還包括：壓縮社區圖形。