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

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

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

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

4、提算法與經(jīng)典算法的性能,結(jié)果表明,所提算法所得檢測(cè)結(jié)果具有較高的檢測(cè)正確率,能更好地反映實(shí)際社團(tuán)劃分情況。
　　3.提出一種基于分解多目標(biāo)優(yōu)化的復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測(cè)新算法。新算法將社團(tuán)檢測(cè)問(wèn)題構(gòu)造成多目標(biāo)優(yōu)化問(wèn)題,通過(guò)在多個(gè)目標(biāo)之間權(quán)衡折衷,實(shí)現(xiàn)在更廣泛的空間進(jìn)行社團(tuán)結(jié)構(gòu)檢測(cè),克服了傳統(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ù)集上對(duì)算法進(jìn)行了仿真實(shí)驗(yàn)。結(jié)果表明,該算法與已有算法相比,具有較高的檢測(cè)正確率,計(jì)算量較小。同時(shí),獲得的多個(gè) Pareto最優(yōu)解有助于揭示復(fù)雜網(wǎng)絡(luò)社團(tuán)的層次結(jié)構(gòu)。
　　4.提出一種新的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)檢測(cè)的多目標(biāo)進(jìn)化算法,算法以快照質(zhì)量和時(shí)序價(jià)值為優(yōu)化目標(biāo)構(gòu)成多目標(biāo)優(yōu)化模型。分別選擇模塊密度度量快照價(jià)值,標(biāo)準(zhǔn)互信息來(lái)度量時(shí)序價(jià)值。采用NSGA-II框架,結(jié)合問(wèn)題特征,設(shè)

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