復雜網絡重要節(jié)點識別方法研究.pdf

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

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

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

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