一種基于正態分布的復雜網絡結構劃分算法

摘? 要：復雜網絡的節點聚集呈現符合社區結構的動態、無標度和非對稱的特性，為了優化復雜網絡的社區結構，研究當前發現和優化社區結構的方法的不足，研究用約束正態分布來改進社區結構的節點聚集歸屬方法，借助信息熵，提出了基于正太分布的復雜網絡結構劃分算法，通過算法得出聚集節點的正態分布概率，用正太分布概率作為信息熵的輸入，重新調整信息熵的變化，根據信息熵變化的幅度，確定節點的劃分歸屬。本算法在確定網絡社區結構劃分的同時，也能夠確定社區內節點的模糊關系。

關鍵詞：正太分布;復雜網絡;社區結構;結構精簡;優化算法

中圖分類號：TP393? ? ?文獻標識碼：A

Abstract：The node aggregation of complex networks presents the dynamic，fuzzy and asymmetrical characteristics of the community structure.In order to optimize the community structure of complex networks，the paper studies the current methods of discovering and optimizing community structures，and the node aggregation method to improve the community structure by constraining normal distribution.Based on information entropy，the paper proposes a complex network structure partitioning algorithm based on positive distribution.The normal distribution probability of the aggregation node is obtained by the algorithm.The positive distribution probability is used as the input of information entropy to re-adjust the information entropy.According to the magnitude of the information entropy change，the division of the node is determined.The algorithm can determine the fuzzy relationship of nodes in the community while determining the division of the network community structure.

Keywords：normal distribution;complex network;community structure;structure simplification;optimization algorithm

1? ?引言（Introduction）

復雜網絡中社區發現的研究是當前國內外研究的熱點之一，社區結構作為復雜網絡重要的特性，對認識節點內部關聯、信息傳播、興趣點推薦等具有重要的研究價值。復雜網絡社區檢測是指從復雜網絡中挖掘出有實際意義的模塊或層次結構的過程，能夠提取出網絡拓撲結構特征，有助于理解和分析網絡的拓撲特性、功能特性及動力學特性，挖掘出復雜網絡中蘊含的屬性關聯性等深層次信息并對網絡行為進行預測[1]。

目前研究人員對復雜網絡社區結構的劃分和檢測進行了大量的研究：文獻[2]提出一種基于k-派系滲透的動態網絡社區檢測算法，該算法需要以較長的檢測時間作為代價實現重疊社區的檢測;文獻[3]提出一種探尋復雜網絡最短路徑的近似算法;文獻[4]提出一個融合貝葉斯概率的社區結構發現方法研究;文獻[5]提出動態社區的點增量發現算法;文獻[6]提出基于單目標PSO的社區檢測算法;文獻[7]提出節點相似度感知的DTN交疊社區結構檢測機制;文獻[8]提出局部優先的社會網絡社區結構檢測算法;文獻[9]提出社交網絡中基于近似因子的自適應社區檢測算法。文獻[10]提出一種基于常量因子近似的動態社區檢測算法，但該算法需要確定明確量化的懲罰成本，而復雜動態網絡多數情況無法預知該懲罰成本，因此，該算法對現實復雜網絡不具有可行性。

針對上述問題，本文提出一種基于正太分布的復雜網絡結構劃分算法（A Complex Network Structural division Algorithm Based on Normal Distribution，CSAN）并利用具有社區結構的已知網絡現實數據檢驗算法的有效性。本文算法的特點是：①算法從中心μ開始擴展，通過距離密度閾值的探測，探查社區結構，實現社區結構的擴展;②算法形成有效社區結構劃分的同時，也能夠把社區結構中遠離社區中心μ的節點重新歸類，減輕社區結構的節點冗余，提高社區結構的工作效率。

2? ?問題建模（Problem modeling）

復雜網絡可以用一個無向圖G=（V，E）表示，其中，節點數量為N=|V|，復雜網絡中節點間連接邊的數量為M=|E|。節點間連接邊的鄰接矩陣A表示為A=（Aij），如果節點i和j之間有一條邊連接，則Aij=1，否則Aij=0。用C=（C1，C2，…，Ck）表示復雜網絡中的社區，CSi（i=1，2，…，k）表示i社區的社區結構。表1列出了本文涉及的符號和各自代表的含義。

2.1? ?信息熵

信息熵[11]是信息論中用于度量信息量的一個概念，它是有明確定義的科學名詞，不隨信息的具體表達形式的變化而改變，是抽象的概念。香農在1948年第一次提出“信息熵（Information Entropy）”的概念，在香農的概念中，信息是消除或減少不確定性的東西。獲得信息，意味著不確定性的減少。不確定性的減少導致“熵”減小，即信息熵越小，表示事件的不確定性越小，則包含的信息量越小;反之則大。信息熵的計算公式如下：

其中，x∈X，X表示一個離散的隨機變量，P（x）表示一個概率密度函數，-log2P（x）表示在狀態x下所含信息量或者不確定性數量。

2.2? ?正態分布

正態分布是數理統計中非常重要的一種概率分布，在解決與中心點距離有關的概率分布具有很廣泛的應用。正態分布的概率密度函數為：

2.3? ?信息熵值探測模型

社區結構的節點聚集具有距離靠近聚集的大概率[12]，為此我們通過探測社區C中節點v在正太分布概率密度下的信息熵H（Xv）的值來確定初始社區的第一個節點，以此節點為基準，根據探測的尺度發現新成員，最終形成一個網絡社區。

3? 基于正太分布的復雜網絡結構劃分算法（Complex network structure division algorithm based on normal distribution）

首先，要確定復雜網絡社區的探測“中心點”，依據中心點計算概率密度覆蓋區域內節點的信息上值，通過信息熵值與閾值之間的對比關系來進一步確定進入社區的節點，從而構建探測和優化社區結構。

算法1 探測復雜網絡的社區“中心點”

在算法2的第6步會產生現有復雜網絡的一些孤立節點，這些節點的集合R=∑LCCk（k=0，1，2，…）。集合R的規模決定了復雜網絡在基于正太分布的社區發現過程中，剔除冗余節點的比例R/N，對于規模龐大的復雜網絡來說，具有一定的優化作用。

4? ?驗證（Experimental verification）

通過實驗的方式檢驗上述算法在復雜網絡社區結構發現和優化中的可行行，算法可以發現不能劃分到社區的節點，從而展示算法的有效性。

實驗數據來源于實驗機房隨機選定的8臺計算機，每臺計算機都能夠通過級聯的交換機互聯，其中編號0—3的計算機連接在1號交換機，4—7號計算機連接在2號交換機。利用算法2計算節點之間的熵值關系矩陣如表2所示。矩陣的值表示有序節點之間的連接概率，矩陣值越大，反映出節點之間的同社區可能性越大，根據設定的閾值ε=0.5，通過算法的執行，得到節點逐步優化分割的社區結構。

通過閾值的調整，可以進一步改進社區結構的節點聚集關系，從而可以實現復雜網絡的優化升級。

算法執行過程中，對應的節點變化走勢如圖1所示。

從算法執行的過程，能夠看出社區結構的形成是符合實際的有價值的結構，對于信息熵值低于閾值的節點將從不隸屬于任何一個社區結構，這些點從復雜網絡中獨立劃分，單獨處理。本算法的時間復雜度為O（N2），隨著網絡規模的急劇增長，算法的計算時間曲線斜率線性增長，耗費大量的系統時間。算法的計算時間同網絡規模之間的關系如圖2所示。

5? ?結論（Conclusion）

復雜網絡的節點聚集呈現符合社區結構的動態、無標度和非對稱的特性，為了優化復雜網絡的社區結構，本文提出的提出一種基于正態分布的復雜網絡結構優化算法（CSAN），本算法既能發現并重構社區結構，也能發現社區內節點之間的動態模糊指向關系，采用了信息熵的變化來發掘社區節點，同時，能夠發掘網絡中的信息相對孤立的冗余節點，這些節點不劃歸任何一個社區，從而優化了社區結構，精簡了社區規模，這是本研究的創新之處。現實中，復雜網絡節點之間的關系復雜，存在多種關系形態，如關聯關系，因果關系，相反關系等，深入研究這種關系對于復雜網絡的優化具有十分重要的意義。本研究只用簡單的局域網進行了檢驗，檢驗算法的數據有限，在實際復雜網絡環境下本算法的具體性能研究還需要做進一步的檢驗工作。對根據信息熵的變化和社區結構具有位置相對靠近聚集的特點，采用正態分布概率密度作為信息熵值估計，從而判斷節點是否屬于一個社區，熵閾值確定很重要，如何確定更好的閾值，使得發現的社區結構有更好的可用性，這也是目前所有社區發現方法面臨的問題，也是下一步的重點研究方向。本研究所涉算法的復雜度偏高，如何降低社區結構發現和優化的算法時間復雜度也是下一步研究的方向。

參考文獻（References）

[1] Qiao Shao-Jie，Guo Jun，Han Nan，et al.Parallel Algorithm for Discovering Communities in Large-Scale Complex Networks[J].Chinese Journal of Computers，2017，3（40）：687-700.

[2] Roy S D，LotanG，ZengWenjun.The Attention Automaton：Sensing Collective User Interests in Social Network Communities[J].IEEETransactionsonNetworkScienceand Engineering，2015，2（1）：40-52.

[3] TANGJin-Tao，WANGTing，WANGJi.Shortest Path Approximate Algorithm for Complex Network Analysis[J].Journal of Software，2011，22（10）：2279-2290.

[4] 王剛.一個融合貝葉斯概率的社區結構發現方法研究[J].計算機技術與發展，2018（12）：1-5.

[5] 顧炎，熊超.動態社區的點增量發現算法[J].計算機技術與發展，2017，27（6）：81-85.

[6] 楊令興，張喜斌.基于單目標PSO的社區檢測算法[J].計算機科學，2015，42（6A）：57-60.

[7] 王崢，王于波，朱承治.節點相似度感知的DTN交疊社區結構檢測機制[J].微電子學與計算機，2017，34（12）：74-78.

[8] 李春英，湯志康，湯庸，等.局部優先的社會網絡社區結構檢測算法[J].計算機科學與探索，2018，12（08）：1263-1274.

[9] 闕建華.社交網絡中基于近似因子的自適應社區檢測算法[J].計算機工程，2016（05）：134-138.

[10] TantipathananandhC，Berger-Wolf T.Constant-factor Approximation Algorithms for Identifying Dynamic Communities[C].Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Paris，France，June 28-July 1，2009：827-836.

[11] Peng CG，Ding HF，Zhu YJ，et al.Informationentropy models and privacy metrics methods for privacy protection[J].Journal of Software，2016，27（8）：1891-1903.

[12] 李兆南，楊博，劉大有.復雜網絡社區挖掘的距離相似度算法[J].計算機科學與探索，2011，5（4）：336-344.

作者簡介：

段忠祥（1978-），男，碩士，高級實驗師.研究領域：軟件設計，計算機應用技術，高職教育.