求解多目標社區發現問題的離散化隨機漂移粒子群優化算法

（1.人工智能與模式識別國際聯合實驗室（江南大學），江蘇無錫 214122；2.無錫職業技術學院物聯網技術學院，江蘇無錫 214121）

0 引言

數據信息可以被抽象為復雜程度不同的網絡，網絡中的點代表信息實體，邊代表實體間的相關性聯系。社區結構是復雜網絡中常見的拓撲特征，即同一社區內的節點與節點之間關系緊密，而社區與社區之間的關系稀疏。由此，社區發現得以出現，它作為從網絡底層結構中提取有用信息的關鍵工具之一，對于理解網絡的結構特征和組織功能具有十分重要的意義。目前，很多重要的研究任務基于社區發現，如網絡病毒傳播、鏈路預測、網絡演化分析、圖像挖掘等［1-5］。

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

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

1 相關工作

1.1 復雜網絡的社區定義

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

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

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

社區發現優化問題是將圖G中的點集V分成若干個子集，每個子集代表一個社區。復雜網絡的定義依據其內部的結構信息，有在對節點度的度量下將社區分為強社區和弱社區［25］，也有針對復雜網絡中邊概率的比例對其進行分類［26］。

1.2 RDPSO算法

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

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

而式（1）中的β?則是定向速度，其中β被稱為漂移系數，用于控制粒子向學習傾向點的速度，可定義為：

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

2 多目標社區發現問題

2.1 問題描述

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

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

2.2 目標函數

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

由于復雜網絡的社區發現的本質是社區間連接稀疏、社區內連接密切，因此可以采用社區間與社區內部的兩個不同標準需求來對社區進行劃分，即可以采用優化算法同時優化KKM和RC兩個目標函數。

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

其中：n是網絡節點總數，m為社區個數。而是集合Ci的補集節點，|Ci|是其社區i的節點個數。

2.3 更新Pareto外部存檔庫

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

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

步驟1 初始化外部存檔P、網格等分數S；

步驟2 計算t時刻目標空間的邊界和

步驟3 計算網格的模

步驟4 統計網格信息、粒子的擁擠度概率；

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

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

2.4 最佳社區的確定

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

3 DRDPSO算法

3.1 粒子的編碼方式

為了更好地求解社區發現優化問題中，粒子的每一維即復雜網絡中的點會被重新編碼。

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

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

3.2 粒子的預處理

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

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

3.3 粒子的離散化定義

RDPSO 是針對連續性優化問題設計的，對于社區發現這種離散型的優化問題不適用，需將RDPSO 算法的粒子更新狀態重新進行離散化定義。本文將“?”“?”“⊕”和“⊙”離散操作符取代RDPSO 算法中的連續計算符，其DRDPSO 算法中粒子的離散化定義如下：

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

其中fi為均勻分布產生的0-1的隨機數。

而根據式（15）的離散計算方式和速度更新結果，粒子的位置做出相應的改變：

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

3.4 DRDPSO求解多目標社區優化問題

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

DRDPSO算法求解多目標社區優化問題的算法如下：

輸入：n個節點的復雜網絡G={V，E}、種群大小pop、最大迭代次數itermax、外部存檔容量rp；

輸出：滿足需求的最優社區劃分C={C1，C2，…，Cm}。

DRDPSO算法流程如圖1所示。

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

4 實驗與結果分析

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

表1 生成網絡參數值Tab.1 Parameter values of generated networks

在真實網絡中，包含具有真實社區結構的空手道俱樂部Zachary’s Karate Club Network 數據集、海豚Dolphins Social Network 數據集、美國大學橄欖球聯盟American College Football 數據集，分別用Karate、Dolphin、Football 表示。表2 中呈現了這3個真實數據集的相關信息。

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

表2 真實網絡數據集特征描述Tab.2 Feature description of real network datasets

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

實驗參數設置為：種群大小pop為200；最大迭代次數itermax為100；外部存檔容量rp為50；網格等分數S為10。

實驗環境為：Intel Core i7 CPU 2.5 GHz，內存為8 GB，Python 3.6中，并使用networkx API。

4.1 生成網絡的實驗結果與分析

4.1.1 GN網絡結果的分析

在GN 網絡中分析這6 種算法獲得的相應社區其Q與NMI值的情況，如表3、4所示。

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

表3 不同算法在GN網絡上的Q 值Tab.3 Q values of different algorithms on GN network

表4 各算法在GN網絡上的NMI值Tab.4 NMI values of different algorithms on GN network

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

表4 中記錄了各算法最大標準化互信息NMImax與平均標準化互信息NMIavg值。由于網絡中最小參數越小，網絡中相對存在的社區結構也越清晰，因此當0.05 ≤γ≤0.35，對應的網絡中絕大數算法都能發現其正確的社區。在γ=0.45 的網絡中，IDPSO-RO 其NMImax=0.469 4，但NMIavg=0.073 1。而在γ=0.5，對應的網絡中幾乎就偵測不出其社區結構。因此，整體上IDPSO-RO 在0.45 ≤γ≤0.5 對應的網絡其劃分的準確率并不高。另外，其他算法偵測其社區的結構相對之下都較為穩定。

通過上述分析，可以發現DRDPSO在GN這種網絡規模中能獲取更精確劃分的社區，社區的劃分質量也相對較好。當最小參數增大時，其他算法在GN 網絡上劃分得到的社區的結果劣于DRDPSO。

綜上，DRDPSO 在LFR1上的各個網絡中得到的劃分社區的效果還是比較理想的，隨著參數的增大，其正確劃分的社區的精度高的且社區的質量較好。

4.1.2 LFR1網絡結果的分析

在LFR1 網絡中這里分析6 種算法獲得的相應的社區模塊度與NMI值的情況，如表5、6中。

在表5 中，可以看出γ=0.2 對應的網絡中，其IDPSO-RO獲得社區的質量均高于其他算法；在γ=0.35、γ=0.45 的網絡中，DRDPSO 劃分的社區質量最好；在γ=0.4 的網絡中，Louvain算法劃分的社區質量最好。

在表6 中，DRDPSO 算法在0.05 ≤γ≤0.35 對應的網絡中的NMImax=1，并且在0.05 ≤γ≤0.45 對應的網絡中NMImax、NMIavg的值也均高于其他算法，而γ=0.5 的網絡中DRDPSO算法的NMImax、NMIavg的值略優于其他算法。

綜上，DRDPSO 在LFR1上的各個網絡中得到的劃分社區的效果較為穩定，且隨著參數的增大其正確劃分社區的精度較為穩定，社區的質量也比較好，魯棒性較高。

表6 各算法在LFR1網絡上的NMI值Tab.6 NMI values of different algorithms on LFR1 network

4.1.3 LFR2網絡結果的分析

表7 和表8 記錄了6 種算法在LFR2 網絡中獲得的相應社區其模塊度Q與NMI值的情況。在表7中，可以看出DRDPSO在LFR2 的10 個網絡中，獲得Qmax、Qavg值相對較高，在模塊度上獲取的社區結構質量稍高一些。

表8 記錄了各算法在該網絡中得到的指標的情況，可以清晰地發現DRDPSO 算法其劃分的社區的精確率在LFR2 網絡上比其他算法都高，尤其是在0.05 ≤γ≤0.45 的網絡中其均有NMImax=1、NMIavg=1，在γ=0.5 的網絡上其NMI指標值比其他算法都高。

綜上所述，DRDPSO 相較于其他幾種算法能更準確地劃分LFR2網絡。

表7 各算法在LFR2網絡上的Q 值Tab.7 Q values of different algorithms on LFR2 network

表8 各算法在LFR2網絡上的NMI值Tab.8 NMI values of different algorithms on LFR2 network

4.2 真實網絡的實驗結果與分析

4.2.1 真實網絡中Pareto 前沿值

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

4.2.2Q與NMI的實驗結果與分析

表9、10 分別給出了各個算法在Karate、Dolphin 上的各項評價指標數據。通過分析算法在Karate 網絡上得到的實驗結果，可以發現DRDPSO 算法獲得的Qmax，NMImax均優于其他對比算法。

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

表11 中記錄了6 種算法在Football 數據集上的各項評價指標的取值。DRDPSO 在社區劃分的精確度為NMImax=0.962 9，因此可以同樣得出DRDPSO 在Football 網絡中劃分的社區最好。

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

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

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

5 結語

本文提出了一種針對復雜網絡多目標社區發現問題的離散化隨機漂移粒子群（DRDPSO）算法，在多個生成網絡數據集及真實網絡數據集上進行了實驗。實驗結果表明，在兩個最佳社區評價指標下，DRDPSO 算法表現均優于其他對比算法，能夠更好更有效地挖掘網絡社區結構，并能夠在較大規模的網絡中具有更強的社區劃分性能。接下來，我們會對該算法在概率度量空間中進行收斂性及粒子軌跡分析，同時，將利用多目標框架優化拓撲與屬性特征函數改進本文提出的算法，并應用到具有屬性信息的復雜網絡社區中。