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

背景技術：

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

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

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

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

技術實現要素：

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

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

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

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

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

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

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

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

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

作為上述方案的改進，通過Python壓縮社區圖形。

相應地，本發明還提供了一種基于Louvain算法的社區發現系統，包括：初始化模塊，用于初始化社區，把每個節點作為一個社區；第一構建模塊，用于將每個節點依次分配到每個鄰居節點所在社區以構建社區圖形；第二構建模塊，用于根據社區圖形把社區看作一個節點，重新構建社區圖形；輸出模塊，用于當所有狀態穩定時，輸出結果。

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

作為上述方案的改進，所述第二構建模塊包括：第一轉化單元，用于把社區內節點度數和，轉化為新節點到自己的環路的權重；第二轉化單元，把社區間的邊權重轉化為新節點間的邊權重。

作為上述方案的改進，所述基于Louvain算法的社區發現系統還包括壓縮模塊，用于壓縮社區圖形。

作為上述方案的改進，所述壓縮模塊通過Python壓縮社區圖形。

實施本發明，具有如下有益效果：

本發明利用大數據中的聚類算法技術，實現復雜網絡中的社區發現。將網絡中的每個節點當作社區，并針對社區的模塊度和邊權重分析，從而可以得到更加精準的社區發現，具體地：

1、本發明采用基于Louvain算法實現社區發現，針對社區中的節點進行模塊度的關聯分析；

2、本發明采用兩層計算。開始通過模塊度變化量對每個節點進行社區劃分，然后針對劃分后形成的社區，做圖形壓縮，從而再次進行社區的模塊度和邊權重分析并進行社區劃分，直到所有狀態穩定，再輸出結果，對社區的發現更加深入。

3、由于節點具有隨機性，本發明沒有使用節點的特征向量對節點進行相似度判斷，而是直接對節點進行向量及模塊度的關聯，更為準確。

附圖說明

圖1是社區節點示意圖；

圖2是本發明基于Louvain算法的社區發現方法的第一實施例流程；

圖3是本發明基于Louvain算法的社區發現方法的第二實施例流程；

圖4是本發明基于Louvain算法的社區發現系統的第一實施例結構示意圖；

圖5是本發明中第一構建模塊的結構示意圖；

圖6是本發明中第二構建模塊的結構示意圖；

圖7是本發明基于Louvain算法的社區發現系統的第二實施例結構示意圖。

具體實施方式

為使本發明的目的、技術方案和優點更加清楚，下面將結合附圖對本發明作進一步地詳細描述。僅此聲明，本發明在文中出現或即將出現的上、下、左、右、前、后、內、外等方位用詞，僅以本發明的附圖為基準，其并不是對本發明的具體限定。

復雜網絡是一個復雜系統的抽象，網絡中的節點表示個體，邊表示個體間的關系。社區結構是復雜網絡中的一個普通特征，整個網絡是由多個社區組成。社區發現(Community Detection)算法用來發現網絡中的社區結構，也可以看作是一種聚類算法。該算法是一個復雜而有意義的過程，它對研究復雜網絡特征具有重要作用。算法試圖歸納各個節點為社區，使得同一個社區內節點連接緊密，而社區間連接比較稀疏(參見圖1)。本發明選用基于模塊度評估的Louvain算法實現社區發現過程。

參見圖2，圖2顯示了本發明一種基于Louvain算法的社區發現方法的第一實施例流程圖，其包括：

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

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

具體地，所述步驟S102包括：

(1)將每個節點，依次嘗試分配到每個鄰居節點所在社區；優選地，采用輪詢方式進行分配。

(2)計算分配前與分配后的模塊度變化量；其中，分配前與分配后的模塊度變化量是指分配前模塊度與分配后模塊度之差。

(3)提取模塊度變化量的最大值；

(4)若模塊度變化量的最大值大于0，則將節點分配到該社區，一直重復這個步驟，直到所有節點不再變化，形成社區圖形。

具體地，與模塊度變化量相關統計指標如下：

節點的度：與節點相連的邊的權和(無權圖則＝邊數)，對于有向圖，度可以分為入度及出度，分別對應以該節點為終點的權和與起點的權和，入度+出度＝度

節點聚類系數：節點與其鄰居實際存在的邊數與可能存在的邊數之比聚類系數越大，節點與周圍連接越密切。

圖的平均聚類系數：節點聚類系數平均值，越大則圖形中的點的關系越密切，更容易成團。

最短路徑長度：圖中指定節點有任意路徑相連，經過路徑最短的長度為最短路徑長度。

模塊度：評估一個社區網絡劃分好壞的度量方法，它的物理含義是社區內節點的連邊數與隨機情況下的邊數之差：其中Aij為邊ij的權重，ki＝∑j，iAij表示節點i的度，ci表示i所屬社區，表示圖的總度數。以上社區劃分方法基于模塊度計算。

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

具體地，所述重新構建社區圖形的方法包括：

(1)把社區內節點度數和，轉化為新節點到自己的環路的權重；

(2)把社區間的邊權重轉化為新節點間的邊權重；

(3)重復步驟S102。

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

社區的穩定狀態，是指社區號不變的狀態。一開始，大家都有一個社區號，自成一個社區，然后就迭代。如果跟旁邊結合，模塊度會下降，就結合，然后結合在一起的就記共同一個社區號。繼續迭代，同樣的，一個點，如果要去旁邊的社區，就必須脫離現在的社區，如果去旁邊的社區模塊度比脫離現在社區的模塊度還要大，那就不脫離了，那就穩定下來了。當所有點都穩定了，迭代結束。社區號不變，就是一個穩定的狀態。

參見圖3，圖3顯示了本發明一種基于Louvain算法的社區發現方法的第二實施例流程圖，其包括：

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

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

具體地，所述步驟S202包括：

(1)將每個節點，依次嘗試分配到每個鄰居節點所在社區；

(2)計算分配前與分配后的模塊度變化量；其中，分配前與分配后的模塊度變化量是指分配前模塊度與分配后模塊度之差。

(3)提取模塊度變化量的最大值；

(4)若模塊度變化量的最大值大于0，則將節點分配到該社區，一直重復這個步驟，直到所有節點不再變化，形成社區圖形。

S203，壓縮社區圖形。

通過Python方式實現降維及類聚，從而實現社區圖形的壓縮。

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

具體地，所述重新構建社區圖形的方法包括：

(1)把社區內節點度數和，轉化為新節點到自己的環路的權重；

(2)把社區間的邊權重轉化為新節點間的邊權重；

(3)重復步驟S202。

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

因此，本發明利用大數據中的聚類算法技術，實現復雜網絡中的社區發現。將網絡中的每個節點當作社區，并針對社區的模塊度和邊權重分析，從而可以得到更加精準的社區發現。相應地，通過社區發現，在教育領域中，可以發現學校內全部學生的社區關系，為學校內學生的大數據分析及服務提供幫助，如可以提供好友發現，更加精準的為學生推薦好友；圖書推薦，可以利用社區中的閱讀風格或者閱讀內容，進行圖書推薦；課程推薦，促進學生個性化學習；職業推薦，根據社區關系推進類似的工作，增加職業推薦的智能性等。

參見圖4，圖4顯示了本發明基于Louvain算法的社區發現系統100的第一實施例，其包括：

初始化模塊1，用于初始化社區，把每個節點作為一個社區；

第一構建模塊2，用于將每個節點依次分配到每個鄰居節點所在社區以構建社區圖形；

第二構建模塊3，用于根據社區圖形把社區看作一個節點，重新構建社區圖形；

輸出模塊4，用于當所有狀態穩定時，輸出結果。

如圖5所示，所述第一構建模塊2包括：

分配單元21，用于將每個節點，依次嘗試分配到每個鄰居節點所在社區；優選地，采用輪詢方式進行分配。

計算單元22，用于計算分配前與分配后的模塊度變化量；其中，分配前與分配后的模塊度變化量是指分配前模塊度與分配后模塊度之差。

提取單元23，用于提取模塊度變化量的最大值；

圖形單元24，用于若模塊度變化量的最大值大于0，則將節點分配到該社區，直到所有節點不再變化，形成社區圖形。

如圖6所示，所述第二構建模塊3包括：

第一轉化單元31，用于把社區內節點度數和，轉化為新節點到自己的環路的權重；

第二轉化單元32，把社區間的邊權重轉化為新節點間的邊權重。

參見圖7，圖7顯示了本發明基于Louvain算法的社區發現系統的第二實施例，與圖4所示的第一實施例不同的是，本實施例中所述基于Louvain算法的社區發現系統還包括壓縮模塊5，所述壓縮模塊5用于壓縮社區圖形。優選地，壓縮模塊5通過Python方式實現降維及類聚，從而實現社區圖形的壓縮。

由上可知，本發明具有以下有益效果：

1、本發明采用基于Louvain算法實現社區發現，針對社區中的節點進行模塊度的關聯分析；

2、本發明采用兩層計算。開始通過模塊度變化量對每個節點進行社區劃分，然后針對劃分后形成的社區，做圖形壓縮，從而再次進行社區的模塊度和邊權重分析并進行社區劃分，直到所有狀態穩定，再輸出結果，對社區的發現更加深入。

3、由于節點具有隨機性，本發明沒有使用節點的特征向量對節點進行相似度判斷，而是直接對節點進行向量及模塊度的關聯，更為準確。

以上所述是本發明的優選實施方式，應當指出，對于本技術領域的普通技術人員來說，在不脫離本發明原理的前提下，還可以做出若干改進和潤飾，這些改進和潤飾也視為本發明的保護范圍。

總結

以上是生活随笔為你收集整理的louvain算法python_一种基于Louvain算法的社区发现方法及系统与流程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。