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

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

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

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

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

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