復(fù)雜網(wǎng)絡(luò)社團(tuán)智能檢測算法及中心性度量.pdf

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

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

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

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

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

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