網絡社區檢測的一種新型混合算法

路 延

（陜西職業技術學院,710100）

網絡社區檢測的一種新型混合算法

路 延

（陜西職業技術學院,710100）

本文中介紹結合粒子群優化算法和非負矩陣分解算法，得到了一種新型社區檢測的譜聚類算法PNMF-Net。這個算法將模塊度作為目標函數。由于PSO算法容易陷入局部最優，對粒子群算法中個體歷史最優粒子使用NMF搜索。同時NMF算法可以減小搜索空間，自動找到網絡社區數。最后使用人工合成網絡和四組真實網絡對PNMF-Net進行測試，結果證明提出的譜聚類算法可以有效地檢測出網絡中固有的社區。

社區檢測;譜聚類;粒子群優化

0 引言

社區檢測是識別出網絡中存在的社區結構或者層次結構，即按照節點之間的連接關系將節點劃分為若干群簇，其中群簇內部的邊連接稠密，不同群簇之間連接稀疏。目前被用于社會網絡分析、蛋白質功能網絡分析、及Web網絡挖掘、Web文本聚類等領域。本文提出了一種改進的PSO算法用于社區檢測，對粒子個體歷史最優值使用NMF搜索增強了粒子搜索能力。

1 新型社區檢測算法PNMF-Net步驟

新型社區檢測算法PNMF-Net通過NMF算法的搜索性能來增強PSO算法搜索能力。

先給出算法的基本框架，算法步驟如下：

輸入：網絡鄰接矩陣V

輸出：節點所在的社區向量，社區分類數c，NMI值

步驟（1）根據網絡節點數隨機產生節點的社區號向量x，作為PSO算法中粒子的位置，并多次產生粒子得到粒子種群，令s=1；

步驟（2）重復以下步驟，直到滿足約束條件，①根據節點數隨機初始化粒子種群中的粒子初始速度，計算每個粒子的適應度值，并將最優粒子作為個gbest，將當前粒子的位置賦給pbest；②根據標準粒子群算法更新粒子種群的速度和位置；③更新粒子種群的pbest和gbest；

步驟（3）保留上述最優的1/5的pbest的粒子；

步驟（4）對上述保留的粒子使用NMF搜索；

步驟（5）若滿足終止條件則輸出最優粒子；

步驟（6）減小搜索范圍，求出NMF搜索后粒子的最大社區數作為后面社區的數量；

步驟（7）隨機產生4/5的粒子種群數的粒子，與上面優化后的1/5個粒子組成新的粒子種群；

步驟（8）令s=s+1，返回步驟（2）。

1.1 粒子表示

本方法中對粒子的編碼采用最簡單的編碼，即隨機初始化每個粒子的社區號作為PSO的初始粒子。假設社區數量為k，網絡節點為n，則每個粒子的大小為，社區號小于k。

1.2 初始化

對于粒子群初始化，采用1.1中粒子表示方法隨機產生一定

數量的粒子得到粒子群。對于粒子速度，隨機選取在[1,c/2]之間的整數。鑒于使用的NMF算法具有自適應性，即算法在計算過程中排除無意義的社區劃分，得到最佳社區數量。因此不需要事先定義好社區具體的數量。當初始社區定義過大則需要浪費許多無意義的操作，如果小于真實社區數量，結果將不正確。在此，初始社區數設為。

1.3 NMF局部搜索算子

由于PSO算法容易陷入局部最優，對于PSO中較好的pbest使用NMF搜索來改善搜索結果。首先將pbest轉換成一個0,1矩陣，為了保證隨機性，對上述矩陣加上一個隨機產生的相同大小的隨機矩陣，然后對其進行歸一化作為NMF的初始化。使用的是無方向網絡，使用。

當優化完保留的粒子個體最優時，減小粒子的搜索空間。對優化后的粒子，求出每個粒子的社區數c，然后使用[1,c]之間的整數取代每個粒子對應的社區號。最后對整體的社區數k選取優化后粒子最大的c。

下面給出NMF搜索步驟算法：NMF搜索算子

輸入：網絡的鄰接矩陣V，需要優化的粒子pbest，參數：迭代次數iter，a，b

輸出：自適應得到的社區數k，網絡隸屬度矩陣W

步驟（2）For i=1:iter do

步驟（3）end for

步驟（4）去掉W全零行，并對W歸一化；

步驟（5）求得W非零行數k；

步驟（6）將隸屬度矩陣轉換成對應的社區號；

2 實驗結果及對比

2.1 實驗設計與評價指標

使用本算法對合成的數據進行測試來證明提出的新算法在社區檢測中的有效性。實驗結果表明新算法可以正確的檢測出網絡的固有結構。

算法是使用matlab程序進行編寫，實驗平臺為core i3，內存為3.05GB，操作系統為windows XP，軟件版本為MATLAB2010a的hp計算機。

參數的選取如下：整個程序運行代數s=5,粒子群個體為20，PSO迭代代數為20，慣性系數w=0.729，常數c1=c2=1.49445， NMF迭代次數為10。

給定同一網絡的兩種不同分割A和B，假設C是一個模糊矩陣，其中元素cij是存在網絡劃分A中社區i，同時也存在于網絡劃分B中社區j的中節點數量。評價社區檢測結果正確性的函數NMI值定義為

2.2 人工合成網絡測試

使用benchmark網絡，這個benchmark網絡有128個節點，分為4個社區，每個社區有32個節點，節點的平均度為16。為了測試結果的正確性，使用NMI值（Normalized Mutual Information）作為標準。

選取GN算法、PSO算法、NMF算法和Meme-Net作為對比算法。NMF算法使用貝葉斯非負矩陣分解算法，PSO算法中使用帶慣性常數的更新規則，粒子數設為200，迭代次數為100，其余參數使用PNMF-Net中相同的參數。Meme-Net在此使用。對每種算法運行30次求的平均值作為結果。圖1是不同的算法在測試這個網絡得到的NMI值折線圖。從圖上可以看到隨著k-out的增大，所有算法的NMI值都會減小，即隨著k-out的增加，算法正確檢測出社區結構越困難。因此可以看出新算法檢測這個數據網絡社區的效果是可靠的。

圖1 不同的算法在處理GNbenchmark數據得到的NMI值比較圖。

3 結論

本文利用了PSO算法全局搜索能力和NMF在結果上可解釋性、可自適應決定分解后特征矩陣的維數等優勢。算法的創新點

可概括為以下兩點：

（1）認為PSO算法容易陷入局部最優和初始化有著密不可分的關系。基于此對第二次開始的迭代使用的粒子為NMF搜索得到的粒子和隨機初始化得到的粒子，豐富了粒子的多樣性。

（2）分析表明PSO算法雖然是全搜索算法，但其搜索范圍往往不能再全局進行搜索。對PSO搜索得到的個體歷史最優進行NMF搜索得到較好的粒子，一定程度上增大了PSO在整個搜索范圍搜索的概率。

[1] Girvan M,Newman MEJ.Community structure in social and biological networks.Proc.Natl.Acad. Sci.USA . 2002,99(12).7821-7826.

[2] 雷德明，嚴新平.多目標智能優化算法及其應用.北京:科學出版社.2009年3月. 10-12

[3] Pizzuti C.A multi-objective genetic algorithm for community detection in networks,in:Proceedings of the 21st IEEE International Conference on Tools with Artificial Intelligence,Newark,New Jersey, USA.2009.397-386

路延，（1985-），女，陜西職業技術學院助教，主要研究方向為計算機應用、圖像識別。

A network of community testing new hybrid algorithm

Lu Yan
(shaanxi vocational & technical college,710100)

In this paper,a novel spectral algorithm(PNMF-Net)to detect communities by combining the algorithms of Particle Swarm Optimization(PSO)and Nonnegative Matrix Factorization(NMF)is proposed.The proposed method optimizes a quality function known as modularity.As PSO may prematurely converge on local optimal solutions,NMF is applied for exploitation by locally modified some better particles resulted by PSO.Meanwhile,NMF narrow the searching space and automatically detect the number of communities of networks.Finally experiments on artificial and real world networks are presented to show the effectiveness of the proposed method.

Community detection;spectral clustering;particle swarm optimization