基于粒子群優化的復雜網絡社區挖掘

白 云,任國霞

(西北農林科技大學信息工程學院,西安712100)

基于粒子群優化的復雜網絡社區挖掘

白 云,任國霞

(西北農林科技大學信息工程學院,西安712100)

為解決復雜網絡社區結構挖掘的優化問題,根據復雜網絡拓撲結構的先驗知識,提出一種基于離散粒子群優化的社區結構挖掘算法。將粒子的位置和速度定義在離散環境下,設計粒子的更新規則,在不需要事先指定社區個數的前提下自動判斷網絡的最佳社區個數,給出局部搜索算子,該算子可以幫助算法跳出局部最優解,提高算法的收斂速度和全局尋優能力。實驗結果表明,與iMeme-net算法相比,該算法能夠準確地挖掘出復雜網絡中隱藏的社區結構,且執行速度較快。

粒子群優化;復雜網絡;社區結構;社區挖掘;局部搜索;模塊密度

1 概述

網絡存在于人們生活中的每一個角落,如社交網絡、通信網絡、金融網絡、生物網絡等。現實中絕大多數復雜系統如電力系統、科學引文系統、航線運輸系統、移動通信系統等,都可以建模成由節點和邊組成的復雜網絡。目前,網絡在以空前的廣度、深度和速度改變人們的日常生活方式和交流方式,同時,網絡也影響著社會的政治、經濟和文化的發展。

文獻［1］提出社會計算的概念,掀起了學術界研究的新高潮。社會計算是一種新的計算模式,計算對象是社會媒體數據,其典型的處理思路是將媒體數據建模成復雜網絡數據然后對復雜網絡進行分析。復雜網絡有很多特性,如小世界性［2］、無標度特性等［3］,其中,社區特性［4］近年來被證明是復雜網絡最具典型的一個特性。所謂網絡社區指的是網絡的一些子塊,這些子塊內部的連接比較密集而子塊與子塊之間的連接則比較稀疏。挖掘復雜網絡中隱藏的社區結構特性對于復雜網絡分析具有及其重要的意義,目前已經有大量的社區結構挖掘算法被提出［5］。

在現存網絡社區挖掘算法里,優化算法的核心

思想是將網絡社區挖掘看成一種優化問題,然后采用啟發式優化算法對該問題進行求解。在啟發式算法中,粒子群優化算法［6］以其原理簡明、操作簡單、參數少、收斂快等特點而聞名,被廣泛應用于求解各種優化問題。粒子群優化算法是受群居生物捕食和躲避捕食者行為的啟發而人工建模的優化算法。然而,經典粒子群優化算法是為連續優化問題設計的,對于離散優化問題,經典粒子群優化算法無法求解。為此,本文提出一種離散粒子群優化算法,并將其應用于復雜網絡社區挖掘。粒子的位置和速度被定義為離散形式,粒子的狀態更新方程被重新設計,并充分利用了網絡的先驗知識。為提高算法的全局搜索能力和收斂速度,設計局部搜索策略,該搜索策略較為充分地挖掘了網絡可以利用的信息,并在計算機模擬網絡數據和真實網絡數據上進行實驗。

2 網絡社區挖掘及粒子群優化

在對復雜網絡進行分析時,通常是將其建模成由節點和邊相互連接的圖,然后再對圖進行分析。網絡社區挖掘就是要挖掘網絡中潛在的社區結構,所挖掘的社區結構必須滿足社區內部連接緊密,而社區與社區之間的連接則相對稀疏。網絡與社區挖掘示意圖如圖1所示。

圖1 網絡與社區挖掘示意圖

從圖1可以看出,網絡社區挖掘的本質是圖的分割問題,其可以轉化成數學優化問題,進而可以采用優化算法進行求解。然而,很多圖的優化問題建模出來的數學函數都不具有可導性,甚至不具備連續性,因此,傳統數學方法很難求解這類問題。為了求解這類優化問題,啟發式優化算法被學者們提出。在啟發式優化算法中,粒子群優化算法脫穎而出并得到廣泛應用［7-8］。粒子群優化算法通過一組粒子來優化一個問題,每個粒子代表問題的一個解,每個粒子通過自身的學習根據一些簡單的規則來調整自己的飛行狀態,從而使粒子向問題的全局最好解靠近。

粒子i根據式(1)調整自己的飛行速度,再根據新的速度來調整自己的飛行軌跡,從而使粒子向最優解區域靠近。

3 基于粒子群優化的網絡社區挖掘算法

經典粒子群優化算法都是為連續優化問題而設計的,其狀態更新式(1)和式(2)無法直接應用于離散問題的求解。本文重新定義了粒子的狀態及其更新公式,提出一種離散粒子群優化算法框架,并將其成功運用于復雜網絡社區挖掘。

3.1 粒子的編碼與解碼

編碼與解碼是將優化問題與優化算法建立連接的橋梁。針對社區挖掘這個問題,文獻［9］提出一種基于連接的編解碼方式,文獻［10］提出字符串的編解碼方式。

本文采用的編解碼方式為基于字符串的編碼,因為這種編碼操作簡單而且解碼方便。本文采用的粒子編解碼方式如圖2所示。

圖2 粒子的編解碼示意圖

由圖2可見,粒子的位置是一個整數序列,序列的每一位數字代表對應位置節點的社區分類標號,在解碼時,具有相同社區標號的節點被劃分到同一個社區中。由此可見,該編碼可以自動判斷網絡到底劃分成幾個社區,而不需要人工事先指定社區個數。

3.2 粒子的狀態更新方程

為了將粒子群優化算法和社區挖掘相結合,本文重新定義粒子的狀態更新方程如下:

其中,ω是慣性權值常數;符號⊕表示異或操作;函數ζ(x)是一個限界函數,其目的是將變量x變為離散的二進制形式,以便于其與位置向量進行式(4)的操作,其具體定義如下:

式(4)中的?操作是粒子狀態更新的核心操作,該操作定義的好壞直接影響算法挖掘社區的性能以及算法的收斂情況。

對于一個網絡而言,2個沒有連接的節點屬于同一個社區的概率要小于2個有連接的節點的概率,基于該事實,本文定義的?操作如下:

3.3 粒子的適應度函數

適應度函數是用來評價粒子狀態好壞的,對于復雜網絡社區挖掘問題而言,適應度函數評價的是網絡社區劃分的好壞。本文采用的適應度函數為文獻［11］提出的模塊密度函數。

令Ω={c1,c2,…,ck}為網絡的一個劃分,1≤k≤N,N是網絡的節點個數,定義L(c1,c2)=∑i∈c1,j∈c2aij,其中,aij為網絡的鄰接矩陣A′的元素,模塊密度定義如下:

其中,α是分辨率控制參數,其范圍為［0,1］;ci′=Ω-ci,|ci|表示社區ci的節點個數。

3.4 粒子的局部搜索策略

由于粒子群優化算法也是一種隨機搜索算法,因此也避免不了陷入局部最優的情況,另外,由于現實的網絡都比較大,算法處理起來可能收斂很慢,為了提高算法的全局尋優能力和收斂速度,本文設計了一種粒子局部搜索策略。該局部搜索策略是對文獻［12］提出的搜索策略的一種改進。本文局部搜索策略的核心思想如圖3所示。

圖3 粒子的局部搜索策略示意圖

從圖3可以看出,本文局部搜索策略的核心思想是對被選擇進行搜索的節點A分配到能夠使目標函數增量最大的鄰居節點的社區中。文獻［12］的搜索策略是將節點A分配到能使目標函數增量最大的其他社區中,而本文的做法則可以大大節省搜索空間,因為本文的搜索是基于節點的連接的,而對于一個大規模網絡而言,社區數目通常很大,但節點的平均度卻很小,即節點的連接是很稀疏的。

4 實驗結果與分析

為了測試所提算法的社區挖掘性能,本節將對算法進行對比實驗測試。實驗中采用了計算機模擬網絡數據和真實網絡數據。實驗采用了文獻［12］的算法iMeme-net作為對比算法。本文算法參數設置為:分辨率控制參數α取值范圍為［0.2,1.0］;間隔為0.1;粒子群大小為50;迭代次數為50;社會系數和認真系數均設置為1.494;慣性權值設為0.792。為了公平起見,算法iMeme-net的種群大小和迭代次數都設為50,其他參數采用原文設置。

計算機模擬網絡數據來源于文獻［13］,該數據被稱為GN擴展基準網絡數據,該網絡數據包含128個節點,被平均分成4個社區,網絡通過一個混合參數γ來控制社區內部以及社區之間邊的連接。

對于網絡的真實社區劃分存在的情況下,為了評價算法挖掘出來的社區的好壞,本文采用文獻［14］提出的互信息指標NMI來進行評價。

給定網絡的2個社區劃分A和B,令C′為一個混淆矩陣,矩陣C′的元素Cij為劃分A中社區i和劃分B中社區j共同擁有的節點個數,則劃分A和B之間的歸一化互信息NMI(A,B)的計算方式可以表示為:

其中,CA(CB)表示劃分A(B)中的社區個數;Ci(Cj)表示矩陣C′的第i行(第j列)的元素之和;N為網絡節點個數。

實驗中,在每個網絡數據上每個算法獨立運行30次。圖4和圖5記錄了算法在計算機模擬網絡上的實驗結果。從圖4和圖5可以看出,本文算法在基準網絡混合參數γ不大于0.35的情況下,可以較好地挖掘網絡的真實社區結構,和iMeme-net算法相比,在參數α=0.9時,本文算法得到的NMI值明顯高于iMeme-net算法。表1記錄了本文算法和對比算法iMeme-net在真實網絡上進行測試時得到的實驗結果,其中,括號里面的為本文算法得到的結果;空手道網絡和海豚網絡的真實社區都為2個。

圖4 本文算法在模擬網絡上的實驗結果

圖5 本文算法與iMeme-net算法的實驗結果對比

表1 真實網絡數據上的實驗結果對比

從表1的實驗數據可以看出,本文算法相對iMeme-net算法在目標函數方面有明顯的提高。在分辨率控制參數α=0.3時,本文算法得到了NMI為1的網絡劃分,即本文算法找到了網絡的真實社區結構。本文算法在α=0.3時得到的空手道網絡和海豚網絡的社區結構如圖6和圖7所示,其中,圓形和四方形分別表示不同的社區劃分。在科學家合作網上本文算法得到的目標函數值明顯高于對比算法。可以看出,本文算法在挖掘網絡的社區結構時是有效的,通過調節目標函數中的分辨率控制參數可以得到不同的網絡社區劃分。

圖6 本文算法得到的空手道網絡社區結構劃分

圖7 本文算法得到的海豚網絡社區結構劃分

5 結束語

復雜網絡社區挖掘對研究網絡隱藏的知識和運行機制具有極其重要的作用。為此,本文提出一種離散粒子群優化算法,并將其運用于社區挖掘。從優化的角度著手挖掘復雜網絡中的社區結構,通過粒子群優化算法優化性能指標,從而尋找該指標最優時對應的網絡社區結構,并給出一種改進的局部搜索策略。實驗結果證明了其有效性。今后將研究如何提高粒子群優化算法在大數據處理上的性能,以及多目標粒子群優化算法的設計。

［1]Lazer D,Pentland A S,Adamic L,et al.Life in the Network:The Coming Age of Computational Social Science［J］.Science,2009,323(5915):721-723.

［2]Watts D J,Strogatz S H.Collective Dynamics of‘Smallworld’Networks［J］.Nature,1998,393(6684):440-442.

［3]Barabási A L,AlbertR.EmergenceofScalingin Random Networks［J］.Science,1999,286(5439): 509-512.

［4]Girvan M,Newman M E J.Community Structure in Social and Biological Networks［J］.Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

［5]Fortunato S.CommunityDetectioninGraphs［J］.Physics Reports,2010,486(3):75-174.

［6]Kennedy J,Eberhart R.Particle Swarm Optimization［C］// Proceedings of IEEE International Conference on Neural Networks.Washington D.C.,USA:IEEE Press,1995, 1942-1948.

［7]鄔開俊,魯懷偉.云環境下基于DPSO的任務調度算法［J］.計算機工程,2014,40(1):59-62.

［8]徐從東,陳 春.一種自適應動態控制參數的粒子群優化算法［J］.計算機工程,2013,39(10):203-207.

［9]Pizzuti C.A Multiobjective Genetic Algorithm to Find Communities in Complex Networks［J］.IEEE Transactions on Evolutionary Computation,2012,16(3):418-430.

［10]Gong Maoguo,Cai Qing,Chen Xiaowei,et al.Complex Network Clustering by Multiobjective Discrete Particle Swarm Optimization Based on Decomposition［J］.IEEE Transactions on Evolutionary Computation,2014,18(1): 82-97.

［11]Li Zhenping,Zhang Shihua,Wang Ruisheng,et al.Quantitative Function for Community Detection［J］.Physical Review E,2008,77(3).

［12]Gong Maoguo,Cai Qing,Li Yangyang,et al.An Improved Memetic Algorithm for Community Detection in Complex Networks［C］//ProceedingsofIEEECongresson Evolutionary Computation.Washington D.C.,USA:IEEE Press,2012:1-8.

［13]Lancichinetti A,FortunatoS,RadicchiF.Benchmark Graphs for Testing Community Detection Algorithms［J］.Physical Review E,2008,78(4).

［14]Huberman B A.Finding Communities in Linear Time: A PhysicsApproach［J］.TheEuropeanPhysical Journal B——Condensed Matter and Complex Systems, 2004,38(2):331-338.

編輯 劉 冰

Complex Network Community Mining Based on Particle Swarm Optimization

BAI Yun,REN Guoxia
(College of Information Engineering,Northwest A&F University,Xi’an 712100,China)

In order to solve the problem of community mining optimization from complex network,according to the prior knowledge of the topology structure of complex network,a complex network community mining algorithm based on Particle Swarm Optimization(PSO)is proposed.In the proposed algorithm,particle’s position and velocity are redefined in discrete case,particle’s update principles is redesigned,the proposed algorithm can automatically determine the best community numbers without knowing it in advance.In order to improve the global search ability of the proposed algorithm,a local search operator is designed,and this operator can help the algorithm to jump out of local optimum and improves the convergence speed.Experimental results demonstrate that the proposed algorithm can efficiently dig out the community structures hidden behind complex networks,and the execution speed is much faster than that of iMeme-net algorithm.

Particle Swarm Optimization(PSO);complex network;community structure;community mining;local search;modularity density

白 云,任國霞.基于粒子群優化的復雜網絡社區挖掘［J］.計算機工程,2015,41(3):177-181.

英文引用格式:Bai Yun,Ren Guoxia.Complex Network Community Mining Based on Particle Swarm Optimization［J］.Computer Engineering,2015,41(3):177-181.

1000-3428(2015)03-0177-05

:A

:TP18

10.3969/j.issn.1000-3428.2015.03.034

白 云(1982-),女,碩士研究生,主研方向:數據挖掘,進化計算;任國霞(通訊作者),副教授。

2014-04-08

:2014-05-16E-mail:rgx@nwsuaf.edu.cn