復(fù)雜網(wǎng)絡(luò)重要節(jié)點識別方法研究.pdf

1、I!lllllfrlll／llllJl／lllfllfJIJIIIllllrlJJIIllllf單位代碼10476學(xué)號∞1830091分類號TP39河南衙瓢大孳碩士學(xué)位論文復(fù)雜網(wǎng)絡(luò)重要節(jié)點識別方法研究學(xué)科、專業(yè)研究方向申請學(xué)位類別申請人指導(dǎo)教師：計算機科學(xué)與技術(shù)：復(fù)雜網(wǎng)絡(luò)：理學(xué)碩士：荊云：劉棟副教授二。一七年五月摘要復(fù)雜網(wǎng)絡(luò)是一門新興的交叉學(xué)科，近年來一直活躍在科研的各個領(lǐng)域。在自然界中，絕大多數(shù)復(fù)雜系統(tǒng)都可以抽象成網(wǎng)絡(luò)，一般由節(jié)點、邊

2、、權(quán)重等基本單元構(gòu)成。在復(fù)雜網(wǎng)絡(luò)中能夠從很大程度上影響網(wǎng)絡(luò)的抗毀性和傳播、同步、控制等功能的節(jié)點被稱為重要節(jié)點。隨著網(wǎng)絡(luò)規(guī)模的增大和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)日趨復(fù)雜，合理且精準(zhǔn)地評價節(jié)點重要性是復(fù)雜網(wǎng)絡(luò)研究中的一個重要問題。本文主要對復(fù)雜網(wǎng)絡(luò)節(jié)點重要性排序和重要節(jié)點挖掘兩部分內(nèi)容開展研究：1針對現(xiàn)有節(jié)點重要性排序算法時間復(fù)雜度較高，排序機理比較單一的問題，提出了一種基于膨脹率抽樣的節(jié)點重要性排序算法，該算法能夠發(fā)現(xiàn)網(wǎng)絡(luò)中度中心性較小但位于不同社區(qū)之

3、間的橋接節(jié)點，此類節(jié)點在信息傳播的速度和擴散范圍上具備獨有的位置優(yōu)勢。仿真實驗表明，排序結(jié)果具有較高的識別精度，算法時間復(fù)雜度較低，而且能夠發(fā)現(xiàn)一些被其他算法同時忽略掉的重要節(jié)點。2針對信息傳播最大化的Topk節(jié)點挖掘算法時間復(fù)雜度高，傳播范圍重疊的問題，提出了一種基于節(jié)點局部信息指數(shù)的挖掘算法，將初始種子節(jié)點分布在合理位置，使其在傳播過程中規(guī)避富人俱樂部現(xiàn)象，降低重疊傳播的損耗。仿真實驗表明，挖掘出的種子節(jié)點組合傳播力較強，且算法時間

4、復(fù)雜度為線性，運算時間非常短。本文致力于重要節(jié)點識別方法的研究，提出了基于膨脹率的節(jié)點排序算法和基于局部信息的Topk節(jié)點挖掘算法。較現(xiàn)有算法運算速度更快，且排序和挖掘精度能夠達到或超過同類算法水平。補充和完善了重要節(jié)點識別算法研究體系，提升了算法性能。本研究在網(wǎng)絡(luò)信息挖掘方面具備積極的理論研究意義，且研究成果可以較好地應(yīng)用于社交網(wǎng)絡(luò)、生物信息、電力網(wǎng)絡(luò)等實際應(yīng)用領(lǐng)域，有較高的應(yīng)用價值。關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)，重要節(jié)點，社區(qū)結(jié)構(gòu)，膨脹率，局部