[發明專利]基于局部稠密度的社團劃分算法

在審

• 申請號: 201410006332.0
• 申請日: 2014-01-07
• 公開（公告）號: CN103761271A
• 公開（公告）日: 2014-04-30
• 發明（設計）人: 馬杰良;潘貞貞
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 顧進

技術領域

????本發明屬于復雜網絡中劃分社團的算法領域，具體涉及一種利用局部信息對復雜網絡進行高效社團劃分的基于局部稠密度的社團劃分算法。

背景技術

現實中許多系統和關系都可以用復雜網絡進行抽象表示，復雜網絡一般指節點眾多、連接關系復雜的網絡，由于其靈活普適的描述能力，能夠廣泛應用于各科學領域對復雜系統進行建模和分析，近年來吸引了越來越多的人對其進行研究。隨著目前對網絡性質、物理意義以及數學特性的深入研究，發現在許多復雜網絡中可以包含多個社團，即具有社團結構，各個社團均為一組相互之間有著較大的相似性而與其所在復雜網絡中的其他社團之間有著很大不同的節點群，也就是說，各個社團中內部節點之間的連接非常緊密，而每個社團之間的連接相對稀疏；每個社團中包含多個節點，節點之間的連線稱為邊，每條邊具有方向性，每條邊在其方向上具有其各自的邊權值。社團發現則是利用圖拓撲結構中所蘊藏的信息從復雜網絡中解析出其模塊化的社團結構，該問題的深入研究有助于以一種分而治之的方式研究整個網絡的模塊、功能及其演化，更加準確地理解復雜系統的組織原則、拓撲結構與動力學特性，具有十分重要的意義。

事實上，研究人員為了搞清網絡社團結構的特性，對尋找網絡中社團結構的多種方法進行了實驗和研究，以找到有效的算法，盡量用比較少的信息區尋找盡量準確的社團結構。以基于聚合思想的Newman快速算法的發現方案為例，其思想為：將復雜網絡中的每個節點作為一個社團，合并使得模塊度函數值增益最大的兩個社團，依次迭代計算，直到整個復雜網絡合并成為一個大社團。整個計算過程以樹狀圖呈現，在模塊度函數Q取得最大值時對網絡進行劃分。Newman快速算法的優點是計算速度快，總的時間復雜度為0（m(m+n)），其中m為網絡中的邊數，n為節點數。雖然Newman算法能夠實現復雜網絡中的社團發現，但是忽略了復雜網絡中存在節點間邊的方向以及權重等特點，使得其進行社團發現的準確率較低。

到目前為止，研究人員還提出了其他社團發現算法，包括譜分析法、最優目標函數算法、基于連邊密度、介數、信息中心度、隨機行走等，計算機領域中的圖分割（Graph?Partitioning）算法、社會科學中的層次聚類（Hierarchical?Clustering）算法、W-H算法和GN算法是最有代表性的方法。例如，一些社團監測算法創立了模塊度Q以及對Q的優化，但是這種算法對于獲取整個網絡的信息是十分困難的并且信息量較大。

發明內容

為解決上述問題，本發明提供一種基于局部稠密度的社團劃分算法，高效利用局部信息將復雜網絡劃分為社團，化整為零簡化對復雜網絡的研究，提高研究時效性。

為達到上述目的，本發明提供如下技術方案：

一種基于局部稠密度的社團劃分算法，其特征在于：包括算法描述、算法檢測以及算法仿真；所述算法描述是將算法用簡單的語言以及數學公式表達復雜的算法，具體方法為：

（a）將一個具體網絡抽象為一個有點集V和邊集E組成的圖G=（V,E），網絡的節點為n；如果頂點????????????????????????????????????????????????和之間有邊相連，則，否則；將網絡的節點標號，計算每個節點及其一階鄰點所構成的局域網絡的；把中的最大的點的局域網絡設為初始社團S；

（b）將初始社團S的一階鄰點集中的全部點加入到S中，加入之后如果稠密度則將全部加入，否則任選中的一點v，它的鄰點集合為，如果入團率，則v可以加入到簇中，把滿足條件的節點都加入到這個簇中，組成一個新簇，在找的鄰居節點；

（c）重復步驟（b），當時，則停止節點加入；并把這些點所在的團，標記為社團C1；接下來所找的社團，依次類推標記；

（d）在剩余沒標記的節點中，找出最大的點，重復步驟（b）-（d）；

（e）查找還沒有歸為社團的點，計算每個點的入團率，把點放入最大的社團。

通過上述描述方法，不需要著手于整體信息，從局部點或團開始，通過凝聚的方式逐步擴大社團的范圍，從而實現社團劃分。

算法檢測的方法為：尋找算法中沒有正確劃分的節點，提出檢測社團劃分精度的一個指標，使沒有正確劃分的節點劃分到正確的社團中。

其中，檢測社團劃分精度的指標為平均內部連接；越大，劃分的社團內部連接越緊密，外部連接越稀疏，表明劃分的社團越好；當社團內一點的內部連接小于0.5時，則重新計算該點的，并把它放入最大的社團中。