摘? 要：復(fù)雜網(wǎng)絡(luò)的節(jié)點聚集呈現(xiàn)符合社區(qū)結(jié)構(gòu)的動態(tài)、無標度和非對稱的特性，為了優(yōu)化復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，研究當(dāng)前發(fā)現(xiàn)和優(yōu)化社區(qū)結(jié)構(gòu)的方法的不足，研究用約束正態(tài)分布來改進社區(qū)結(jié)構(gòu)的節(jié)點聚集歸屬方法，借助信息熵，提出了基于正太分布的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)劃分算法，通過算法得出聚集節(jié)點的正態(tài)分布概率，用正太分布概率作為信息熵的輸入，重新調(diào)整信息熵的變化，根據(jù)信息熵變化的幅度，確定節(jié)點的劃分歸屬。本算法在確定網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分的同時，也能夠確定社區(qū)內(nèi)節(jié)點的模糊關(guān)系。

關(guān)鍵詞：正太分布;復(fù)雜網(wǎng)絡(luò);社區(qū)結(jié)構(gòu);結(jié)構(gòu)精簡;優(yōu)化算法

中圖分類號：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）

復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的研究是當(dāng)前國內(nèi)外研究的熱點之一，社區(qū)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)重要的特性，對認識節(jié)點內(nèi)部關(guān)聯(lián)、信息傳播、興趣點推薦等具有重要的研究價值。復(fù)雜網(wǎng)絡(luò)社區(qū)檢測是指從復(fù)雜網(wǎng)絡(luò)中挖掘出有實際意義的模塊或?qū)哟谓Y(jié)構(gòu)的過程，能夠提取出網(wǎng)絡(luò)拓撲結(jié)構(gòu)特征，有助于理解和分析網(wǎng)絡(luò)的拓撲特性、功能特性及動力學(xué)特性，挖掘出復(fù)雜網(wǎng)絡(luò)中蘊含的屬性關(guān)聯(lián)性等深層次信息并對網(wǎng)絡(luò)行為進行預(yù)測[1]。

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

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

2? ?問題建模（Problem modeling）

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

2.1? ?信息熵

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

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

2.2? ?正態(tài)分布

正態(tài)分布是數(shù)理統(tǒng)計中非常重要的一種概率分布，在解決與中心點距離有關(guān)的概率分布具有很廣泛的應(yīng)用。正態(tài)分布的概率密度函數(shù)為：

2.3? ?信息熵值探測模型

社區(qū)結(jié)構(gòu)的節(jié)點聚集具有距離靠近聚集的大概率[12]，為此我們通過探測社區(qū)C中節(jié)點v在正太分布概率密度下的信息熵H（Xv）的值來確定初始社區(qū)的第一個節(jié)點，以此節(jié)點為基準，根據(jù)探測的尺度發(fā)現(xiàn)新成員，最終形成一個網(wǎng)絡(luò)社區(qū)。

3? 基于正太分布的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)劃分算法（Complex network structure division algorithm based on normal distribution）

首先，要確定復(fù)雜網(wǎng)絡(luò)社區(qū)的探測“中心點”，依據(jù)中心點計算概率密度覆蓋區(qū)域內(nèi)節(jié)點的信息上值，通過信息熵值與閾值之間的對比關(guān)系來進一步確定進入社區(qū)的節(jié)點，從而構(gòu)建探測和優(yōu)化社區(qū)結(jié)構(gòu)。

算法1 探測復(fù)雜網(wǎng)絡(luò)的社區(qū)“中心點”

在算法2的第6步會產(chǎn)生現(xiàn)有復(fù)雜網(wǎng)絡(luò)的一些孤立節(jié)點，這些節(jié)點的集合R=∑LCCk（k=0，1，2，…）。集合R的規(guī)模決定了復(fù)雜網(wǎng)絡(luò)在基于正太分布的社區(qū)發(fā)現(xiàn)過程中，剔除冗余節(jié)點的比例R/N，對于規(guī)模龐大的復(fù)雜網(wǎng)絡(luò)來說，具有一定的優(yōu)化作用。

4? ?驗證（Experimental verification）

通過實驗的方式檢驗上述算法在復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)和優(yōu)化中的可行行，算法可以發(fā)現(xiàn)不能劃分到社區(qū)的節(jié)點，從而展示算法的有效性。

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

通過閾值的調(diào)整，可以進一步改進社區(qū)結(jié)構(gòu)的節(jié)點聚集關(guān)系，從而可以實現(xiàn)復(fù)雜網(wǎng)絡(luò)的優(yōu)化升級。

算法執(zhí)行過程中，對應(yīng)的節(jié)點變化走勢如圖1所示。

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

5? ?結(jié)論（Conclusion）

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

參考文獻（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] 王剛.一個融合貝葉斯概率的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)方法研究[J].計算機技術(shù)與發(fā)展，2018（12）：1-5.

[5] 顧炎，熊超.動態(tài)社區(qū)的點增量發(fā)現(xiàn)算法[J].計算機技術(shù)與發(fā)展，2017，27（6）：81-85.

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

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

[8] 李春英，湯志康，湯庸，等.局部優(yōu)先的社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)檢測算法[J].計算機科學(xué)與探索，2018，12（08）：1263-1274.

[9] 闕建華.社交網(wǎng)絡(luò)中基于近似因子的自適應(yīng)社區(qū)檢測算法[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，F(xiàn)rance，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] 李兆南，楊博，劉大有.復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘的距離相似度算法[J].計算機科學(xué)與探索，2011，5（4）：336-344.

作者簡介：

段忠祥（1978-），男，碩士，高級實驗師.研究領(lǐng)域：軟件設(shè)計，計算機應(yīng)用技術(shù)，高職教育.