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

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

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

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

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