復雜網(wǎng)絡特征結構的挖掘方法研究.pdf

1、在過去的十年中，信息技術的迅速發(fā)展大大地提高了人類的計算能力，同時也積累了大量的觀測數(shù)據(jù)有待研究者們分析，這些都鼓勵著科技工作者對身邊的世界作進一步的探索。將復雜的現(xiàn)實系統(tǒng)看作是互相關聯(lián)的復雜網(wǎng)絡，正是最近時期所興起的一種通用的研究模式，這種研究模式為多個領域的研究者提供了一個系統(tǒng)層次的觀察視角。
　　 復雜網(wǎng)絡，也被稱為“網(wǎng)絡新科學”研究學派，認為世界是由多種多樣的系統(tǒng)組成，而現(xiàn)實世界中的復雜系統(tǒng)又是由成千上萬個個體單元互相交

2、互關聯(lián)而組成，如果將個體單元抽象為網(wǎng)絡中的頂點，單元間的交互關系抽象為網(wǎng)絡的邊，那么我們就可以通過研究抽象生成的網(wǎng)絡結構來分析原系統(tǒng)的功能和性質。
　　 面對錯綜復雜的現(xiàn)實網(wǎng)絡結構，研究者使用統(tǒng)計的方法分析網(wǎng)絡拓撲。對網(wǎng)絡的整體屬性提出了許多新的網(wǎng)絡拓撲度量方法，并建立新的網(wǎng)絡模型來模擬現(xiàn)實網(wǎng)絡數(shù)據(jù)，希望能夠進一步預測網(wǎng)絡上的傳播動力學現(xiàn)象。近十年來，復雜網(wǎng)絡研究者在這些方向上取得了重大的進展。
　　 復雜網(wǎng)絡研究是在建

3、立在圖論和社會網(wǎng)絡分析的基礎上，并以新近獲得的實證網(wǎng)絡數(shù)據(jù)為研究對象，為解決實際問題而發(fā)展起來。伴隨著研究的深入，人們需要對網(wǎng)絡作更深層的分析，想了解網(wǎng)絡更多的細節(jié)信息，而傳統(tǒng)的網(wǎng)絡分析理論工具往往難以處理近期獲得的大數(shù)據(jù)集。面對這樣的困難，網(wǎng)絡分析中的方法論研究就顯得十分迫切。
　　 針對該問題，本文嘗試從一個新的角度思考網(wǎng)絡分析問題?？紤]到網(wǎng)絡中的特征結構，如社團、層次等，通常是由具有某種相似性的網(wǎng)絡頂點所構成，而統(tǒng)計數(shù)據(jù)分

4、析領域的理論工具恰恰可以分析數(shù)據(jù)分布中數(shù)據(jù)點間的相似關系，抽取數(shù)據(jù)分布中的結構。如果能夠將網(wǎng)絡問題轉化成數(shù)據(jù)分析問題，那么就可以利用數(shù)據(jù)分析工具來處理網(wǎng)絡問題。本文主要工作即是首先通過一定的測量方法將網(wǎng)絡投影到高維測量空間，再應用信號處理和統(tǒng)計模式識別領域中的數(shù)學工具來深層挖掘由網(wǎng)絡生成的點分布，進而依據(jù)挖掘得到的點分布結構特征來反推原網(wǎng)絡的結構特征。讀者將從文章中的實驗看到，運用該思路分析處理實際網(wǎng)絡時，可以便利地解決許多困難的網(wǎng)絡結

5、構分析問題。
　　 本文將上述思路應用在三個網(wǎng)絡分析問題上，分別為“網(wǎng)絡拓撲分析”、“網(wǎng)絡社團發(fā)現(xiàn)”和“網(wǎng)絡結構比較”。
　　 第一，網(wǎng)絡拓撲分析。我們將待研究的網(wǎng)絡依據(jù)一定的準則投影到測量空間，并且將網(wǎng)絡中相似的節(jié)點投影在相近的位置，這樣原網(wǎng)絡的拓撲特征就可以從投影的數(shù)據(jù)點集中涌現(xiàn)出來。我們用該網(wǎng)絡投影方法分析了隨機圖、規(guī)則圖、小世界網(wǎng)和無標度網(wǎng)，四個網(wǎng)絡模型的各自結構特征可以很好地被顯示出來。我們進一步使用網(wǎng)絡投影方

6、法分析了現(xiàn)實的Internet自治域數(shù)據(jù)，Internet的層次結構和水母模型也得到了驗證。繼而我們借用數(shù)據(jù)分布的度最作為網(wǎng)絡的結構度量，并依據(jù)該度量作實際網(wǎng)絡的相似性分析，結果表明同類網(wǎng)絡的呈現(xiàn)出相似的度量值。實驗表明了“網(wǎng)絡投影”方法的有效性。
　　 第二，網(wǎng)絡社團發(fā)現(xiàn)。社團結構是現(xiàn)實網(wǎng)絡中普遍存在的一種基本結構，與網(wǎng)絡的功能和性質關系緊密。分析網(wǎng)絡的社團結構具有重要的理論實踐意義。本文提出將網(wǎng)絡的社團結構對應為信號處理領域

7、的獨立成分，基于頂點的相似性，從而從信號數(shù)據(jù)分析的角度來探討網(wǎng)絡的社團發(fā)現(xiàn)問題。首先將網(wǎng)絡投影成測量空間的點分布，再使用經典的聚類方法尋找相似的點組成的點群，最后將根據(jù)在測量空間中找到的點群結構來確定網(wǎng)絡中的社團結構。通過分析Zachary柔道俱樂部網(wǎng)絡和南方女士網(wǎng)絡，我們驗證了本方法可以有效地發(fā)現(xiàn)社團結構。
　　 第三，網(wǎng)絡結構比較。對網(wǎng)絡進行適當?shù)臏y量，生成的點分布可以反映網(wǎng)絡許多基本結構特征，根據(jù)該點，我們用的數(shù)據(jù)分析方法