復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)中心性多元評(píng)估與社團(tuán)探測(cè)新算法研究.pdf

1、對(duì)復(fù)雜網(wǎng)絡(luò)的定性和定量特征進(jìn)行研究，有助于揭示復(fù)雜網(wǎng)絡(luò)的普遍規(guī)律和未知信息，在計(jì)算機(jī)科學(xué)、物理科學(xué)、生物科學(xué)、社會(huì)科學(xué)、數(shù)學(xué)等諸多學(xué)科中具有重要意義。復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)中心性評(píng)估及其對(duì)社團(tuán)探測(cè)影響等問(wèn)題一直是復(fù)雜網(wǎng)絡(luò)研究的熱點(diǎn)，系統(tǒng)研究這些問(wèn)題有利于解釋網(wǎng)絡(luò)成因，理解網(wǎng)絡(luò)結(jié)構(gòu)，指導(dǎo)網(wǎng)絡(luò)行為和提高人類對(duì)復(fù)雜網(wǎng)絡(luò)的認(rèn)知。
　　本論文主要研究復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)中心性多元評(píng)估與基于節(jié)點(diǎn)中心性的社團(tuán)探測(cè)算法，主要工作與創(chuàng)新點(diǎn)如下：
　　針對(duì)復(fù)雜網(wǎng)

2、絡(luò)節(jié)點(diǎn)中心性單指標(biāo)評(píng)估的片面性和不穩(wěn)定性等問(wèn)題，以及多指標(biāo)評(píng)估算法計(jì)算時(shí)間復(fù)雜度高和不精確等問(wèn)題。對(duì)特征向量中心性、中介中心性、緊密中心性、點(diǎn)度中心性、互信息中心性等指標(biāo)向量進(jìn)行深入研究，同時(shí)，對(duì)主流數(shù)據(jù)降維算法進(jìn)行對(duì)比分析，提出了一種節(jié)點(diǎn)中心性多元評(píng)估算法(MI-LDA)。該算法將高維模式樣本投影到最佳鑒別矢量空間，將特征空間維數(shù)進(jìn)行壓縮。仿真結(jié)果表明，該算法能夠更高效地找到網(wǎng)絡(luò)的中心節(jié)點(diǎn)，相比其他的主流數(shù)據(jù)降維算法，MI-LDA時(shí)間

3、復(fù)雜度更低。
　　為進(jìn)一步提高節(jié)點(diǎn)中心性評(píng)估的精確度，提出另外一種節(jié)點(diǎn)中心性多元評(píng)估算法（MI-LLE）。該算法將各項(xiàng)指標(biāo)值作為初始數(shù)據(jù)輸入，在保留鄰居節(jié)點(diǎn)的情況下，最小化代價(jià)函數(shù)，將數(shù)據(jù)降維轉(zhuǎn)化為特征分解的問(wèn)題，然后將高維樣本投影到低維樣本空間實(shí)現(xiàn)數(shù)據(jù)維數(shù)的壓縮，從而識(shí)別出中心節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，相比其他主流數(shù)據(jù)降維算法，此算法計(jì)算精確度更高。
　　由于大部分網(wǎng)絡(luò)的中心節(jié)點(diǎn)即為社團(tuán)的中心，提出一種基于節(jié)點(diǎn)中心性的社團(tuán)探測(cè)算

4、法Infomap-SA，該算法首先利用LDA算法識(shí)別出中心節(jié)點(diǎn)，并按降序排列。隨后利用基于隨機(jī)行走編碼的Infomap算法，同時(shí)引入模擬退火思想優(yōu)化模塊度函數(shù)。仿真結(jié)果表明Infomap-SA算法能夠?qū)ι鐖F(tuán)進(jìn)行準(zhǔn)確檢測(cè)、高效劃分，比Infomap算法具有更高的模塊度和連接密度，更低的時(shí)間復(fù)雜度，并且更適用于大規(guī)模網(wǎng)絡(luò)的社團(tuán)探測(cè)。
　　充分利用CNM算法全局性層次聚類的優(yōu)點(diǎn)，同時(shí)結(jié)合節(jié)點(diǎn)中心性的思想，提出一種新型的基于節(jié)點(diǎn)中心性的社

5、團(tuán)探測(cè)算法CNM-Centrality，該算法基于快速貪婪聚類算法CNM，應(yīng)用PageRank算法進(jìn)行中心節(jié)點(diǎn)識(shí)別，然后對(duì)中心節(jié)點(diǎn)與其臨近節(jié)點(diǎn)進(jìn)行優(yōu)化劃分。實(shí)驗(yàn)結(jié)果表明CNM-Centrality算法能夠?qū)ι鐖F(tuán)進(jìn)行準(zhǔn)確探測(cè)、高效劃分，比CNM、Infomap、Walktrap等算法具有更高的模塊度值和歸一化互信息(NMI)值。
　　本論文研究并實(shí)現(xiàn)了節(jié)點(diǎn)中心性多元評(píng)估算法MI-LDA和MI-LLE，以及基于節(jié)點(diǎn)中心性的社團(tuán)探測(cè)算法