復(fù)雜網(wǎng)絡(luò)特征結(jié)構(gòu)的挖掘方法研究.pdf

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

2、互關(guān)聯(lián)而組成，如果將個(gè)體單元抽象為網(wǎng)絡(luò)中的頂點(diǎn)，單元間的交互關(guān)系抽象為網(wǎng)絡(luò)的邊，那么我們就可以通過研究抽象生成的網(wǎng)絡(luò)結(jié)構(gòu)來分析原系統(tǒng)的功能和性質(zhì)。
　　 面對(duì)錯(cuò)綜復(fù)雜的現(xiàn)實(shí)網(wǎng)絡(luò)結(jié)構(gòu)，研究者使用統(tǒng)計(jì)的方法分析網(wǎng)絡(luò)拓?fù)?。?duì)網(wǎng)絡(luò)的整體屬性提出了許多新的網(wǎng)絡(luò)拓?fù)涠攘糠椒ǎ⒔⑿碌木W(wǎng)絡(luò)模型來模擬現(xiàn)實(shí)網(wǎng)絡(luò)數(shù)據(jù)，希望能夠進(jìn)一步預(yù)測網(wǎng)絡(luò)上的傳播動(dòng)力學(xué)現(xiàn)象。近十年來，復(fù)雜網(wǎng)絡(luò)研究者在這些方向上取得了重大的進(jìn)展。
　　 復(fù)雜網(wǎng)絡(luò)研究是在建

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

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

5、構(gòu)分析問題。
　　 本文將上述思路應(yīng)用在三個(gè)網(wǎng)絡(luò)分析問題上，分別為“網(wǎng)絡(luò)拓?fù)浞治觥薄ⅰ熬W(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)”和“網(wǎng)絡(luò)結(jié)構(gòu)比較”。
　　 第一，網(wǎng)絡(luò)拓?fù)浞治?。我們將待研究的網(wǎng)絡(luò)依據(jù)一定的準(zhǔn)則投影到測量空間，并且將網(wǎng)絡(luò)中相似的節(jié)點(diǎn)投影在相近的位置，這樣原網(wǎng)絡(luò)的拓?fù)涮卣骶涂梢詮耐队暗臄?shù)據(jù)點(diǎn)集中涌現(xiàn)出來。我們用該網(wǎng)絡(luò)投影方法分析了隨機(jī)圖、規(guī)則圖、小世界網(wǎng)和無標(biāo)度網(wǎng)，四個(gè)網(wǎng)絡(luò)模型的各自結(jié)構(gòu)特征可以很好地被顯示出來。我們進(jìn)一步使用網(wǎng)絡(luò)投影方

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

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