（1.人工智能與模式識別國際聯(lián)合實驗室（江南大學(xué)），江蘇無錫 214122；2.無錫職業(yè)技術(shù)學(xué)院物聯(lián)網(wǎng)技術(shù)學(xué)院，江蘇無錫 214121）

0 引言

數(shù)據(jù)信息可以被抽象為復(fù)雜程度不同的網(wǎng)絡(luò)，網(wǎng)絡(luò)中的點代表信息實體，邊代表實體間的相關(guān)性聯(lián)系。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中常見的拓?fù)涮卣?，即同一社區(qū)內(nèi)的節(jié)點與節(jié)點之間關(guān)系緊密，而社區(qū)與社區(qū)之間的關(guān)系稀疏。由此，社區(qū)發(fā)現(xiàn)得以出現(xiàn)，它作為從網(wǎng)絡(luò)底層結(jié)構(gòu)中提取有用信息的關(guān)鍵工具之一，對于理解網(wǎng)絡(luò)的結(jié)構(gòu)特征和組織功能具有十分重要的意義。目前，很多重要的研究任務(wù)基于社區(qū)發(fā)現(xiàn)，如網(wǎng)絡(luò)病毒傳播、鏈路預(yù)測、網(wǎng)絡(luò)演化分析、圖像挖掘等［1-5］。

根據(jù)不同的研究視角，社區(qū)發(fā)現(xiàn)的研究可分為聚類問題和優(yōu)化問題。聚類算法中包括經(jīng)典社區(qū)劃分算法（Girvan-Newman，GN）［6］、Infomap［7］、標(biāo)簽傳遞算法（Label Propagation Algorithm，LPA）［8］等，Dong［9］提出改進(jìn)的標(biāo)簽傳遞算法（Improved Label Propagation Algorithm，ILPA）在重疊社區(qū)發(fā)現(xiàn)中與其他現(xiàn)有方法相比，精度更高。從優(yōu)化的角度來看，大多數(shù)算法都是基于啟發(fā)式進(jìn)化算法逐步優(yōu)化預(yù)定義的目標(biāo)函數(shù)以獲得模塊化程度最高的社區(qū)結(jié)構(gòu)［10-13］。進(jìn)化算法（Evolutionary Algorithm，EA）等具有較強的全局優(yōu)化能力的智能優(yōu)化技術(shù)也在社區(qū)發(fā)現(xiàn)中引起廣泛關(guān)注，如遺傳算法（Genetic Algorithm，GA）［14-15］、微分進(jìn)化（Differntial Ecaluation，DE）［16］、針對社區(qū)發(fā)現(xiàn)的蜂群優(yōu)化（Bee Swarm Optimization for Community Detection，BSOCD）［17］等仿生學(xué)算法等?；谶M(jìn)化算法的社區(qū)檢測方法存在參數(shù)多、收斂慢等問題，同時交叉變異過程的復(fù)雜性導(dǎo)致了社區(qū)結(jié)構(gòu)的不穩(wěn)定性，考慮到智能粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法的參數(shù)較少，全局收斂能力較強，收斂較快，不少學(xué)者將其引入社區(qū)發(fā)現(xiàn)算法之中［18-20］。Cai 等［21］研究了離散粒子群優(yōu)化的符號網(wǎng)絡(luò)社區(qū)檢測方法，該方法有效且有應(yīng)用前景，但只是對網(wǎng)絡(luò)整體結(jié)構(gòu)進(jìn)行考量，而忽略了局部結(jié)構(gòu)信息。Cao 等［22］提出了壓縮形式的粒子群優(yōu)化社區(qū)算法（Improved Simple discrete Particle Swarm Optimization，ISPSO）和改進(jìn)的離散形式的粒子群優(yōu)化算法（Improved Discrete Particle Swarm Optimization with Redefined Operator，IDPSORO）的對比，提出了孤立節(jié)點的修正策略。Chaitanya 等［23］提出了一種基于動態(tài)鄰域拓?fù)涞牧Ｗ尤簝?yōu)化算法的社區(qū)檢測方法，該算法局部搜索能力較好，但全局搜索性能及魯棒性較差。

基于優(yōu)化算法框架的社區(qū)發(fā)現(xiàn)算法雖然取得了不同程度的成功，但仍存在算法不具備普適性、劃分網(wǎng)絡(luò)社區(qū)的難度大、算法預(yù)測準(zhǔn)確率低等問題。隨機漂移粒子群優(yōu)化（Random Drift Particle Swarm Optimization，RDPSO）［24］算法框架是一種變種的PSO 算法，是對PSO 進(jìn)行收斂性分析和對金屬導(dǎo)體中自由電子進(jìn)行運動軌跡分析的啟發(fā)而提出的。RDPSO 算法在連續(xù)優(yōu)化問題上具有良好的表現(xiàn)，但由于其粒子更新的隨機性較強，因此在社區(qū)發(fā)現(xiàn)問題上表現(xiàn)較差。為了克服RDPSO 的不足使其能夠更加適用于求解社區(qū)發(fā)現(xiàn)這類離散優(yōu)化問題，本文首先通過隨機編碼方式對社區(qū)結(jié)構(gòu)進(jìn)行編碼，然后針對社區(qū)發(fā)現(xiàn)問題，提出離散化的隨機漂移粒子群優(yōu)化（Discrete Random Drift Particle Swarm Optimization，DRDPSO）算法用于求解多目標(biāo)社區(qū)劃分問題，通過核K 均值（Kernel K-Means，KKM）和比例割（Ratio Cut，RC）兩個目標(biāo)函數(shù)來控制網(wǎng)絡(luò)中的社區(qū)規(guī)模、緩解模塊度分辨率。根據(jù)多目標(biāo)求解策略逐步更新Pareto非劣解集，從Pareto非劣解集選取滿足需求的目標(biāo)社區(qū)結(jié)構(gòu)。

1 相關(guān)工作

1.1 復(fù)雜網(wǎng)絡(luò)的社區(qū)定義

復(fù)雜網(wǎng)絡(luò)依據(jù)圖論可以由二元組G={V，E}表示，其中：V={v1，v2，…，vn}為n維點集，E=｛（i，j）|vi∈V，vj∈V，andi≠j｝代表邊集。

假設(shè)C={C1，C2，…，Ck}是圖G中的k個子集，Ci需要滿足下列條件：

1）Ci?V且Ci≠?，其中i=1，2，…，k；

社區(qū)發(fā)現(xiàn)優(yōu)化問題是將圖G中的點集V分成若干個子集，每個子集代表一個社區(qū)。復(fù)雜網(wǎng)絡(luò)的定義依據(jù)其內(nèi)部的結(jié)構(gòu)信息，有在對節(jié)點度的度量下將社區(qū)分為強社區(qū)和弱社區(qū)［25］，也有針對復(fù)雜網(wǎng)絡(luò)中邊概率的比例對其進(jìn)行分類［26］。

1.2 RDPSO算法

RDPSO 算法可描述為一個由M個N維粒子在空間上的不斷向最優(yōu)方向聚集搜索的過程。粒子在下一時刻的位置可表示為其中i表示第i個粒子，t為當(dāng)前迭代步，而其在下一時刻的速度定位為RDPSO 中粒子的速度和位置更新公式定義如下：

其中：α?|為隨機速度；α為熱敏系數(shù)，控制隨機速度的大小，一般隨時間線性下降；Mt j為當(dāng)前時刻的個體平均最優(yōu)位置?？捎墒剑?）得出：

而式（1）中的β?則是定向速度，其中β被稱為漂移系數(shù)，用于控制粒子向?qū)W習(xí)傾向點的速度，可定義為：

在搜索過程中，粒子始終朝著學(xué)習(xí)傾向點聚集，而隨機速度又給予算法很強的逃離局部最優(yōu)區(qū)域的能力。因此，算法不僅具有全局搜索能力且收斂性較強。

2 多目標(biāo)社區(qū)發(fā)現(xiàn)問題

2.1 問題描述

多目標(biāo)優(yōu)化問題的目的是通過同時優(yōu)化多個目標(biāo)函數(shù)尋找滿足約束條件的最優(yōu)決策解集。一般來說多目標(biāo)優(yōu)化問題中的各個目標(biāo)函數(shù)是相互沖突的，因此多目標(biāo)優(yōu)化問題的難點在于找到一組合理的解集。一個含有D個決策變量、N個目標(biāo)函數(shù)以及m+k個約束條件的多目標(biāo)約束優(yōu)化問題可以描述為：

其中：y是由多個目標(biāo)函數(shù)構(gòu)成的目標(biāo)函數(shù)向量；fn(x)為第n個目標(biāo)函數(shù)；x為決策向量。另外，其可行解域通過hi(x) ≤0和gj(x)=0 約束函數(shù)確定，xd_min和xd_max是各個決策變量的上下限。

2.2 目標(biāo)函數(shù)

文獻(xiàn)［27］指出核K均值（KKM）是社區(qū)內(nèi)部節(jié)與其內(nèi)部緊密度的平均值；與此相反，比例割（RC）則為所有社區(qū)內(nèi)部的節(jié)點與其他外部間連接的平均值。最小化RC 則會使社區(qū)節(jié)點數(shù)量增加，使得網(wǎng)絡(luò)的社區(qū)數(shù)量減少，與其他社區(qū)間的連接稀疏，所以這兩個函數(shù)能有效平衡社區(qū)規(guī)模，提高劃分準(zhǔn)確度。文獻(xiàn)［28］指出模塊度的分辨率限制是由于其不包含社區(qū)的節(jié)點數(shù)量信息，并且該方式下社區(qū)的劃分對網(wǎng)絡(luò)的連接關(guān)系是高度敏感的。而這兩個函數(shù)與網(wǎng)絡(luò)中的子圖密度有關(guān)，但對網(wǎng)絡(luò)中的連接總數(shù)的敏感性不強。因此，KKM 可以看作是群落內(nèi)部聯(lián)系密度的總和，RC 可視為群落間聯(lián)系密度的總和。

由于復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)的本質(zhì)是社區(qū)間連接稀疏、社區(qū)內(nèi)連接密切，因此可以采用社區(qū)間與社區(qū)內(nèi)部的兩個不同標(biāo)準(zhǔn)需求來對社區(qū)進(jìn)行劃分，即可以采用優(yōu)化算法同時優(yōu)化KKM和RC兩個目標(biāo)函數(shù)。

在無向圖G中，其鄰接矩陣為A，若將圖G劃分為m個社區(qū)，即C={C1，C2，…，Cm}，其目標(biāo)函數(shù)KMM和RC可定義為：

其中：n是網(wǎng)絡(luò)節(jié)點總數(shù)，m為社區(qū)個數(shù)。而是集合Ci的補集節(jié)點，|Ci|是其社區(qū)i的節(jié)點個數(shù)。

2.3 更新Pareto外部存檔庫

Pareto 外部存檔庫是用來保存算法在粒子更新過程中獲取的非占優(yōu)粒子群（非占優(yōu)解），它也可以被認(rèn)為是一個目標(biāo)解的存儲空間。在計算目標(biāo)函數(shù)之后，當(dāng)前粒子群需要和歷史種群中的其他個體進(jìn)行比較確定其是否為非占優(yōu)粒子。而存檔庫的空間大小是具有一定數(shù)量限制，即種群中的非占優(yōu)解的個數(shù)是有限的。

Pareto 外部存檔的更新過程為：在每次更新中，將當(dāng)前粒子群根據(jù)Pareto 支配原則，計算Archive 集并獲取此時的非劣解集；再將此時的非劣解集與當(dāng)前Pareto 外部存檔進(jìn)行第二輪支配關(guān)系比較，更新Pareto 外部存檔；最后，判斷其存檔數(shù)是否超過閾值。需要指出的是，本文通過擁擠度的計算來刪除超出閾值范圍的非占優(yōu)解，保持外部存檔的數(shù)目。Pareto外部存檔更新步驟如下：

步驟1 初始化外部存檔P、網(wǎng)格等分?jǐn)?shù)S；

步驟2 計算t時刻目標(biāo)空間的邊界和

步驟3 計算網(wǎng)格的模

步驟4 統(tǒng)計網(wǎng)格信息、粒子的擁擠度概率；

步驟5 保存高擁擠概率中粒子的索引值；

步驟6 輸出外部存檔P中的待刪除檢索值。

2.4 最佳社區(qū)的確定

在多目標(biāo)社區(qū)發(fā)現(xiàn)優(yōu)化問題中，最佳社區(qū)的確定并不是由種群的全局最優(yōu)位置決定的，而是利用最終的Pareto 外部存檔庫P進(jìn)行選擇最優(yōu)需求的解。因此，本文使用社區(qū)模塊度Q與歸一化互信息（Normalizaed Mutual Information，NMI）的最大值對算法獲得的社區(qū)進(jìn)行評價，這兩個評價指標(biāo)的定義如下：

3 DRDPSO算法

3.1 粒子的編碼方式

為了更好地求解社區(qū)發(fā)現(xiàn)優(yōu)化問題中，粒子的每一維即復(fù)雜網(wǎng)絡(luò)中的點會被重新編碼。

求解社區(qū)優(yōu)化問題一定程度上依賴于粒子的初始值，常見的粒子的編碼方式有兩種：1）每個粒子的位置值為［1，n］內(nèi)的隨機整數(shù)，但該方式具有較強的隨機性、易使劃分的社區(qū)結(jié)構(gòu)不穩(wěn)定；2）使用LAR（Locus-based Adjacency Represent）方式，即粒子的編碼值根據(jù)鄰居節(jié)點的編號取值，粒子能獲取較好的初始值，但該方式復(fù)雜度較高［29-30］。

為降低解碼過程的復(fù)雜度，DRDPSO 算法采取隨機編碼的方式對社區(qū)網(wǎng)絡(luò)的節(jié)點進(jìn)行編碼。但如果僅僅將對粒子值賦值為｛1，2，…，n｝，容易使算法劃分網(wǎng)絡(luò)得到的社區(qū)結(jié)構(gòu)單一、缺乏多樣性，并且社區(qū)質(zhì)量較差。為此，首先對粒子初始位置值進(jìn)行預(yù)處理操作。因此，在DRDPSO 算法中引入了粒子預(yù)處理操作［31］，算法復(fù)雜度相對較低且它可以發(fā)現(xiàn)網(wǎng)絡(luò)中潛在的社區(qū)結(jié)構(gòu)，這有助于提高算法的準(zhǔn)確性。

3.2 粒子的預(yù)處理

粒子預(yù)處理是對粒子xi，t(t)作如下計算：

其中：函數(shù)f返回的是節(jié)點t的鄰居節(jié)點所屬社區(qū)的最多數(shù)的社區(qū)編號；k為節(jié)點t所擁有的鄰居節(jié)點的數(shù)目。通過對粒子進(jìn)行預(yù)處理操作，即基于鄰居節(jié)點的成員關(guān)系決定粒子的位置，因此可以將那些具有更緊密連接的節(jié)點劃分為相同的社區(qū)。

3.3 粒子的離散化定義

RDPSO 是針對連續(xù)性優(yōu)化問題設(shè)計的，對于社區(qū)發(fā)現(xiàn)這種離散型的優(yōu)化問題不適用，需將RDPSO 算法的粒子更新狀態(tài)重新進(jìn)行離散化定義。本文將“?”“?”“⊕”和“⊙”離散操作符取代RDPSO 算法中的連續(xù)計算符，其DRDPSO 算法中粒子的離散化定義如下：

其中，粒子的速度通過二進(jìn)制化可重新定義如下：

其中fi為均勻分布產(chǎn)生的0-1的隨機數(shù)。

而根據(jù)式（15）的離散計算方式和速度更新結(jié)果，粒子的位置做出相應(yīng)的改變：

其中：lw，v表示社區(qū)w、社區(qū)v的連接情況；dw、dv分別為社區(qū)w、社區(qū)v的總度數(shù)；m為邊數(shù)。

3.4 DRDPSO求解多目標(biāo)社區(qū)優(yōu)化問題

在搜索過程中，首先DRDPSO 算法通過預(yù)處理和離散化的編碼方式將該網(wǎng)絡(luò)的數(shù)據(jù)集轉(zhuǎn)化為對應(yīng)的種群各個粒子的初始值。緊接著，初始化算法的相關(guān)參數(shù)，構(gòu)建初始的網(wǎng)絡(luò)社區(qū)模型，并計算目標(biāo)函數(shù)得到每一個可行解的適應(yīng)值。進(jìn)一步，依據(jù)Pareto 支配原則，獲取具有一定數(shù)量的非占優(yōu)解并保存在外部存檔庫中。最后，依據(jù)式（6）～（7）更新粒子種群。需要注意的是，在更新外部存儲庫中的非占優(yōu)解時需要將其擁有高擁擠距離的個體刪除以減少計算時間。當(dāng)滿足終止條件時，最優(yōu)解將從非占優(yōu)解集中選擇出。

DRDPSO算法求解多目標(biāo)社區(qū)優(yōu)化問題的算法如下：

輸入：n個節(jié)點的復(fù)雜網(wǎng)絡(luò)G={V，E}、種群大小pop、最大迭代次數(shù)itermax、外部存檔容量rp；

輸出：滿足需求的最優(yōu)社區(qū)劃分C={C1，C2，…，Cm}。

DRDPSO算法流程如圖1所示。

圖1 DRDPSO算法流程Fig.1 Flowchart of DRDPSO algorithm

4 實驗與結(jié)果分析

實驗采用的網(wǎng)絡(luò)數(shù)據(jù)集分別為生成網(wǎng)絡(luò)與真實網(wǎng)絡(luò)。在生成網(wǎng)絡(luò)中，利用3種類型的網(wǎng)絡(luò)驗證相關(guān)算法：GN、LFR1和LFR2。其中：GN 是Lancichinetti 等［33］在經(jīng)典基準(zhǔn)網(wǎng)絡(luò)上提出的擴展網(wǎng)絡(luò)；LFR1、LFR2分別是不同大小規(guī)模的LFR標(biāo)準(zhǔn)基網(wǎng)絡(luò)類型。在表1中給出了生成這些網(wǎng)絡(luò)的一些參數(shù)，其中：N是合成網(wǎng)絡(luò)的節(jié)點數(shù)；Kavg為平均節(jié)點度數(shù)；Kmax為節(jié)點度數(shù)上限；Cmin和Cmax是社區(qū)規(guī)模的最小值和最大值；另外γ稱為最小參數(shù)，它控制社區(qū)內(nèi)外的連接部分。這里生成了10個網(wǎng)絡(luò)，通過控制最小參數(shù)在0.0～0.5的區(qū)間內(nèi)每隔0.05生成一個網(wǎng)絡(luò)。

表1 生成網(wǎng)絡(luò)參數(shù)值Tab.1 Parameter values of generated networks

在真實網(wǎng)絡(luò)中，包含具有真實社區(qū)結(jié)構(gòu)的空手道俱樂部Zachary’s Karate Club Network 數(shù)據(jù)集、海豚Dolphins Social Network 數(shù)據(jù)集、美國大學(xué)橄欖球聯(lián)盟American College Football 數(shù)據(jù)集，分別用Karate、Dolphin、Football 表示。表2 中呈現(xiàn)了這3個真實數(shù)據(jù)集的相關(guān)信息。

從圖5可以看出，隨流速的增加，樹脂對花色苷的解吸效果越來越差，可能是流速過快導(dǎo)致乙醇不能與被吸附的花色苷充分作用而將其從樹脂上洗脫出來。但是流速太慢會導(dǎo)致解析的時間延長，故選擇 1 mL/min作為洗脫流速。

表2 真實網(wǎng)絡(luò)數(shù)據(jù)集特征描述Tab.2 Feature description of real network datasets

由于GN［6］、Louvain［13］、Infomap［7］、IDPSO-RO［22］、BSOCD［17］等算法效率比較高，可覆蓋所有類型的網(wǎng)絡(luò)，且發(fā)現(xiàn)的社區(qū)質(zhì)量也比較好，因此將其與提出的DRDPSO 算法進(jìn)行實驗數(shù)據(jù)比較。實驗中，針對生成網(wǎng)絡(luò)，每種規(guī)模各生成10 個網(wǎng)絡(luò)進(jìn)行實驗對比分析，同時針對三種真實網(wǎng)絡(luò)進(jìn)行實驗分析，記錄GN、Louvain、Infomap、IDPSO-RO、BSOCD、DRDPSO 算法取得的Q與NMI值。

實驗參數(shù)設(shè)置為：種群大小pop為200；最大迭代次數(shù)itermax為100；外部存檔容量rp為50；網(wǎng)格等分?jǐn)?shù)S為10。

實驗環(huán)境為：Intel Core i7 CPU 2.5 GHz，內(nèi)存為8 GB，Python 3.6中，并使用networkx API。

4.1 生成網(wǎng)絡(luò)的實驗結(jié)果與分析

4.1.1 GN網(wǎng)絡(luò)結(jié)果的分析

在GN 網(wǎng)絡(luò)中分析這6 種算法獲得的相應(yīng)社區(qū)其Q與NMI值的情況，如表3、4所示。

表3 記錄了各算法獲得最大模塊度Qmax值以及平均模塊度Qavg值。除了A3（Infomap 算法），其他算法的最大模塊度值處于整體下降趨勢，如圖2 所示。而在0.45 ≤γ≤0.5 對應(yīng)的網(wǎng)絡(luò)中，DRDPSO 的Qmax，Qavg相對較大，證明DRDPSO 算法是一種模塊度優(yōu)化較強的算法，其獲得社區(qū)結(jié)構(gòu)質(zhì)量相較其他網(wǎng)絡(luò)更好。

表3 不同算法在GN網(wǎng)絡(luò)上的Q 值Tab.3 Q values of different algorithms on GN network

表4 各算法在GN網(wǎng)絡(luò)上的NMI值Tab.4 NMI values of different algorithms on GN network

圖2 不同算法最大模塊度Q 值趨勢Fig.2 Maximum modularity Q value trend of different algorithms

表4 中記錄了各算法最大標(biāo)準(zhǔn)化互信息NMImax與平均標(biāo)準(zhǔn)化互信息NMIavg值。由于網(wǎng)絡(luò)中最小參數(shù)越小，網(wǎng)絡(luò)中相對存在的社區(qū)結(jié)構(gòu)也越清晰，因此當(dāng)0.05 ≤γ≤0.35，對應(yīng)的網(wǎng)絡(luò)中絕大數(shù)算法都能發(fā)現(xiàn)其正確的社區(qū)。在γ=0.45 的網(wǎng)絡(luò)中，IDPSO-RO 其NMImax=0.469 4，但NMIavg=0.073 1。而在γ=0.5，對應(yīng)的網(wǎng)絡(luò)中幾乎就偵測不出其社區(qū)結(jié)構(gòu)。因此，整體上IDPSO-RO 在0.45 ≤γ≤0.5 對應(yīng)的網(wǎng)絡(luò)其劃分的準(zhǔn)確率并不高。另外，其他算法偵測其社區(qū)的結(jié)構(gòu)相對之下都較為穩(wěn)定。

通過上述分析，可以發(fā)現(xiàn)DRDPSO在GN這種網(wǎng)絡(luò)規(guī)模中能獲取更精確劃分的社區(qū)，社區(qū)的劃分質(zhì)量也相對較好。當(dāng)最小參數(shù)增大時，其他算法在GN 網(wǎng)絡(luò)上劃分得到的社區(qū)的結(jié)果劣于DRDPSO。

綜上，DRDPSO 在LFR1上的各個網(wǎng)絡(luò)中得到的劃分社區(qū)的效果還是比較理想的，隨著參數(shù)的增大，其正確劃分的社區(qū)的精度高的且社區(qū)的質(zhì)量較好。

4.1.2 LFR1網(wǎng)絡(luò)結(jié)果的分析

在LFR1 網(wǎng)絡(luò)中這里分析6 種算法獲得的相應(yīng)的社區(qū)模塊度與NMI值的情況，如表5、6中。

在表5 中，可以看出γ=0.2 對應(yīng)的網(wǎng)絡(luò)中，其IDPSO-RO獲得社區(qū)的質(zhì)量均高于其他算法；在γ=0.35、γ=0.45 的網(wǎng)絡(luò)中，DRDPSO 劃分的社區(qū)質(zhì)量最好；在γ=0.4 的網(wǎng)絡(luò)中，Louvain算法劃分的社區(qū)質(zhì)量最好。

在表6 中，DRDPSO 算法在0.05 ≤γ≤0.35 對應(yīng)的網(wǎng)絡(luò)中的NMImax=1，并且在0.05 ≤γ≤0.45 對應(yīng)的網(wǎng)絡(luò)中NMImax、NMIavg的值也均高于其他算法，而γ=0.5 的網(wǎng)絡(luò)中DRDPSO算法的NMImax、NMIavg的值略優(yōu)于其他算法。

綜上，DRDPSO 在LFR1上的各個網(wǎng)絡(luò)中得到的劃分社區(qū)的效果較為穩(wěn)定，且隨著參數(shù)的增大其正確劃分社區(qū)的精度較為穩(wěn)定，社區(qū)的質(zhì)量也比較好，魯棒性較高。

表6 各算法在LFR1網(wǎng)絡(luò)上的NMI值Tab.6 NMI values of different algorithms on LFR1 network

4.1.3 LFR2網(wǎng)絡(luò)結(jié)果的分析

表7 和表8 記錄了6 種算法在LFR2 網(wǎng)絡(luò)中獲得的相應(yīng)社區(qū)其模塊度Q與NMI值的情況。在表7中，可以看出DRDPSO在LFR2 的10 個網(wǎng)絡(luò)中，獲得Qmax、Qavg值相對較高，在模塊度上獲取的社區(qū)結(jié)構(gòu)質(zhì)量稍高一些。

表8 記錄了各算法在該網(wǎng)絡(luò)中得到的指標(biāo)的情況，可以清晰地發(fā)現(xiàn)DRDPSO 算法其劃分的社區(qū)的精確率在LFR2 網(wǎng)絡(luò)上比其他算法都高，尤其是在0.05 ≤γ≤0.45 的網(wǎng)絡(luò)中其均有NMImax=1、NMIavg=1，在γ=0.5 的網(wǎng)絡(luò)上其NMI指標(biāo)值比其他算法都高。

綜上所述，DRDPSO 相較于其他幾種算法能更準(zhǔn)確地劃分LFR2網(wǎng)絡(luò)。

表7 各算法在LFR2網(wǎng)絡(luò)上的Q 值Tab.7 Q values of different algorithms on LFR2 network

表8 各算法在LFR2網(wǎng)絡(luò)上的NMI值Tab.8 NMI values of different algorithms on LFR2 network

4.2 真實網(wǎng)絡(luò)的實驗結(jié)果與分析

4.2.1 真實網(wǎng)絡(luò)中Pareto 前沿值

圖3 給出了DRDPSO 算法在Karate、Dolphin 與Football 網(wǎng)絡(luò)中獲取的Pareto 前沿值。每幅圖的橫坐標(biāo)為KKM函數(shù)值，縱坐標(biāo)為RC函數(shù)值。另外，在每幅圖中有兩個箭頭，分別對了Qmax與NMImax值時所對應(yīng)的兩目標(biāo)函數(shù)。因此，可以看出Qmax與NMImax時，其KKM與RC值是不同的。

4.2.2Q與NMI的實驗結(jié)果與分析

表9、10 分別給出了各個算法在Karate、Dolphin 上的各項評價指標(biāo)數(shù)據(jù)。通過分析算法在Karate 網(wǎng)絡(luò)上得到的實驗結(jié)果，可以發(fā)現(xiàn)DRDPSO 算法獲得的Qmax，NMImax均優(yōu)于其他對比算法。

圖3 DRDPSO在Karate、Dolphin、Football網(wǎng)絡(luò)中獲取Qmax與NMImax時的Pareto前沿值Fig.3 Pareto front values when DRDPSO obtaining Qmaxand NMImaxin Karate，Dolphin and Football networks

表11 中記錄了6 種算法在Football 數(shù)據(jù)集上的各項評價指標(biāo)的取值。DRDPSO 在社區(qū)劃分的精確度為NMImax=0.962 9，因此可以同樣得出DRDPSO 在Football 網(wǎng)絡(luò)中劃分的社區(qū)最好。

表9 各算法在Karate數(shù)據(jù)集上的評價值Tab.9 Evaluation values of different algorithms on Karate dataset

表10 各算法在Dolphin數(shù)據(jù)集上的評價值Tab.10 Evaluation values of different algorithms on Dolphin dataset

表11 各算法在Football數(shù)據(jù)集上的評價值Tab.11 Evaluation values of different algorithms on Football dataset

5 結(jié)語

本文提出了一種針對復(fù)雜網(wǎng)絡(luò)多目標(biāo)社區(qū)發(fā)現(xiàn)問題的離散化隨機漂移粒子群（DRDPSO）算法，在多個生成網(wǎng)絡(luò)數(shù)據(jù)集及真實網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實驗。實驗結(jié)果表明，在兩個最佳社區(qū)評價指標(biāo)下，DRDPSO 算法表現(xiàn)均優(yōu)于其他對比算法，能夠更好更有效地挖掘網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，并能夠在較大規(guī)模的網(wǎng)絡(luò)中具有更強的社區(qū)劃分性能。接下來，我們會對該算法在概率度量空間中進(jìn)行收斂性及粒子軌跡分析，同時，將利用多目標(biāo)框架優(yōu)化拓?fù)渑c屬性特征函數(shù)改進(jìn)本文提出的算法，并應(yīng)用到具有屬性信息的復(fù)雜網(wǎng)絡(luò)社區(qū)中。