復雜網(wǎng)絡社團智能檢測算法及中心性度量.pdf

1、人類已經(jīng)生活在一個包含各種各樣的復雜網(wǎng)絡的世界中,自然界中許多相互作用的復雜系統(tǒng),如互聯(lián)網(wǎng)、電力系統(tǒng)、生物分子系統(tǒng)等,皆可抽象成復雜網(wǎng)絡。迅速發(fā)展的計算機處理能力和海量數(shù)據(jù)存儲能力使得科學家越來越容易地在現(xiàn)實世界中收集海量的網(wǎng)絡數(shù)據(jù),研究其內(nèi)在規(guī)律。除了小世界特性、無標度特性,社團結構特性被認為是復雜網(wǎng)絡中最重要的統(tǒng)計特性之一。揭示網(wǎng)絡的內(nèi)在社團結構對理解結構與功能關系、發(fā)現(xiàn)其演化規(guī)律、監(jiān)控與預測其演變行為具有重要的理論意義和廣泛的應用

2、前景,已成為近幾年來學術界的研究熱點。本文對復雜網(wǎng)絡中社團智能檢測算法及中心性度量進行了探索和研究,主要工作和創(chuàng)新成果分為如下五個方面:
　　1.分析了基于優(yōu)化模塊度檢測復雜網(wǎng)絡社團結構的算法存在解的限制問題,該類算法不能檢測出小于一定內(nèi)在尺度的社團,并提出了基于極值優(yōu)化模塊密度來檢測復雜網(wǎng)絡社團結構的一種新的啟發(fā)式算法,通過調(diào)整局部極值來優(yōu)化全局的變量,使算法具有更好的持續(xù)搜索和跳出局優(yōu)解的能力。通過人工網(wǎng)絡和現(xiàn)實網(wǎng)絡實驗分析表

3、明,所提算法在檢測網(wǎng)絡社團時,具有較高的正確率和效率,即使在網(wǎng)絡結構變得很模糊時,算法也能很好地工作。
　　2.通過分析復雜網(wǎng)絡重疊社團檢測問題,提出了衡量重疊社團劃分優(yōu)劣的評判函數(shù),并基于該函數(shù)提出一種基于混沌量子粒子群優(yōu)化的復雜網(wǎng)絡重疊社團檢測算法,并證明了該算法以概率1收斂。所提算法采用量子編碼,利用Logistic映射初始化粒子種群,以粒子群速度改變方式更新轉角的大小。利用計算機生成的網(wǎng)絡和實際網(wǎng)絡進行了仿真實驗,比較了所

4、提算法與經(jīng)典算法的性能,結果表明,所提算法所得檢測結果具有較高的檢測正確率,能更好地反映實際社團劃分情況。
　　3.提出一種基于分解多目標優(yōu)化的復雜網(wǎng)絡社團檢測新算法。新算法將社團檢測問題構造成多目標優(yōu)化問題,通過在多個目標之間權衡折衷,實現(xiàn)在更廣泛的空間進行社團結構檢測,克服了傳統(tǒng)單目標優(yōu)化存在解單一的缺陷。算法采用MOEA/D框架,運用Tchebycheff分解技術,引入基于加權法的模擬退火局部搜索算子,擴大了搜索范圍,使算法

5、不易陷入局部最優(yōu)解。最后,在計算機生成的網(wǎng)絡數(shù)據(jù)集以及真實網(wǎng)絡數(shù)據(jù)集上對算法進行了仿真實驗。結果表明,該算法與已有算法相比,具有較高的檢測正確率,計算量較小。同時,獲得的多個 Pareto最優(yōu)解有助于揭示復雜網(wǎng)絡社團的層次結構。
　　4.提出一種新的動態(tài)網(wǎng)絡社團檢測的多目標進化算法,算法以快照質(zhì)量和時序價值為優(yōu)化目標構成多目標優(yōu)化模型。分別選擇模塊密度度量快照價值,標準互信息來度量時序價值。采用NSGA-II框架,結合問題特征,設

6、計新的遺傳算子。針對問題特定領域知識,設計了一個局部搜索算子來提高社團檢測性能。對合成數(shù)據(jù)和真實數(shù)據(jù)進行實驗,實驗結果表明所提算法比對比算法可以更精確地檢測動態(tài)網(wǎng)絡社團結構,真實反映社團的演化。
　　5.提出一種基于信息流的復雜網(wǎng)絡中心性測度,并將其擴展到組中心性,用來度量一組節(jié)點的中心性。所提測度克服了傳統(tǒng)中心性測度的缺點,不僅適用于連通網(wǎng)絡,也適用于非連通網(wǎng)絡。利用標準測試集對所提測度與傳統(tǒng)中心性測度進行了比較試驗,結果表明所