【文章內(nèi)容簡介】 ...... 32 各種網(wǎng)絡(luò)探測算法處理后的網(wǎng)絡(luò)效果 .................................................................. 35 合而聚之 ............................................................................................................................ 36 模塊度 ..................................................................................................................... 36 小社團(tuán)合并算法 ...................................................................................................... 37 社團(tuán)劃分比較 ................................................................................................................... 40 東北大學(xué)碩士學(xué)位論文 目 錄 VII 對于全球 IPV6 拓?fù)涞膭澐直容^ .................................................................................. 41 105 算法在其它網(wǎng)絡(luò)上的測試 ......................................................................................... 43 Karate 俱樂部 ....................................................................................................... 43 東北大學(xué)嵌入式實(shí)驗(yàn)室 聊天網(wǎng)絡(luò) — 網(wǎng)絡(luò)的共產(chǎn)主義 .................................. 45 東大嵌入式實(shí)驗(yàn)室日常人際交流網(wǎng)絡(luò) — 地理位置隔離的社團(tuán)結(jié)構(gòu) ............... 46 新的衡量社團(tuán)劃分質(zhì)量方法的探討 ............................................................................... 48 新的社團(tuán)發(fā)現(xiàn)思路 ............................................................................................... 48 新的求解最短路徑的算法 ...................................................................................... 49 本章小結(jié) .................................................................................................................... 49 第 4 章 一種新的面向社團(tuán)的網(wǎng)絡(luò)拓?fù)淇梢暬惴? ......................................................................................... 51 可視化算法綜述 ............................................................................................................... 51 面向社團(tuán)結(jié)構(gòu)特征的可視化 ........................................................................................... 53 所用開發(fā)工具 .......................................................................................................... 53 算法思想 ................................................................................................................. 54 算法設(shè)計與實(shí)現(xiàn) ...................................................................................................... 54 本章小結(jié) ........................................................................................................................... 59 第 5 章 總結(jié)與展望 .......................................................................................................................................................... 60 本文所做的工作 ............................................................................................................... 60 不足及展望 ....................................................................................................................... 61 參考文獻(xiàn) ................................................................................................................................................................................ 62 致 謝 ..................................................................................................................................................................................... 66 攻讀碩士期間發(fā)表的論文 ............................................................................................................................................. 68 東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 1 第 1 章 緒 論 課題研究的背景與意義 互聯(lián)網(wǎng)的社 團(tuán)結(jié)構(gòu)研究現(xiàn)狀 近年來 ,隨著信息系統(tǒng)（如 WWW、 電信網(wǎng)、 廣播電視網(wǎng) 、移動網(wǎng)絡(luò)等 ）的迅猛發(fā)展，網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)的規(guī)?？焖僭龃? ，以致人們不能通過傳統(tǒng)技術(shù)和方式來管理和運(yùn)作這些復(fù)雜網(wǎng)絡(luò)。人們通過對生物網(wǎng)絡(luò)、 社會關(guān)系網(wǎng)、 Web 網(wǎng)等的研究 ,發(fā)現(xiàn)這些網(wǎng)絡(luò)都具有某些共同特點(diǎn)，包括：整體相對稀疏 ，局部比較密集；頂點(diǎn)度值服從冪率分布，也被稱為無標(biāo)度特性 [1]；整體分布具有高聚集度、 低平均最短路徑 (平均最短路徑為 O (loglog N) ) 的小世界特性 [2]。具有以上性質(zhì)（無標(biāo)度性、小世界性）的網(wǎng)絡(luò)被稱為復(fù)雜網(wǎng)絡(luò) ?；ヂ?lián)網(wǎng)具有典型的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)，本文后續(xù)的研究手段都是以復(fù)雜網(wǎng)絡(luò)理論為基礎(chǔ)。 在現(xiàn)實(shí)世界中，存在大量復(fù)雜系統(tǒng)，可把這些復(fù)雜系統(tǒng)看作各種網(wǎng)絡(luò)來研究。一個典型的網(wǎng)絡(luò)是由若干節(jié)點(diǎn) iv ( ivV? )以及連接任意兩個在實(shí)際拓?fù)渲杏羞B接關(guān)系的節(jié)點(diǎn)jv 和 kv ( ,jkv v V? )的邊 jke ( jk Ee ? .)組成。網(wǎng)絡(luò)的研究最早可追溯到 18 世紀(jì)，數(shù)學(xué)家歐拉在對“ Konigsberg 七橋問題”的研究時提出的一個數(shù)學(xué)分支 —— 圖論，圖論在較長的時間內(nèi)一直未能有突破性進(jìn)展。上世紀(jì) 60 年代， Erd?s 和 R233。nyi 建立了隨機(jī)圖理論[3](Random Graph Theory)，開創(chuàng)了復(fù)雜網(wǎng)路理論系統(tǒng)性研究。自此以后的很長時間內(nèi)隨機(jī)圖理論一直是復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)研究的基本理論 [4]。隨機(jī)圖理論有明顯的缺點(diǎn)，它不能很好的描述 很多實(shí)際網(wǎng)絡(luò)，因?yàn)榇蟛糠謱?shí)際網(wǎng)絡(luò)并不是完全隨機(jī)的。例如 Inter 上的兩個站點(diǎn)之間是否有超文本鏈接， Inter 中的兩個 AS 域之間是否有直接聯(lián)系，兩個作者之間是否有合作，這些都不能由隨機(jī)選擇來決定。 從 20 世紀(jì)末開始，復(fù)雜網(wǎng)絡(luò)理論的研究已經(jīng)拓展到了從物理學(xué)到社會學(xué)等眾多學(xué)科中，其中 Watts 和 Strogatz 在 Nature 雜志上發(fā)表的文獻(xiàn) [5]探討了復(fù)雜網(wǎng)絡(luò)中存在“小世界” 錯誤 !未指定書簽。 現(xiàn)象， Barab225。si 和 Albert 在 Science 雜志上發(fā)表的文獻(xiàn) [6]探討了隨機(jī)網(wǎng)絡(luò)中“無標(biāo)度”現(xiàn)象，這兩篇文獻(xiàn)被認(rèn)為是復(fù)雜網(wǎng)絡(luò)研究新紀(jì)元的標(biāo)志。目前對于復(fù)雜網(wǎng)絡(luò)的研究主要包括網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)、網(wǎng)絡(luò)拓?fù)浣?、網(wǎng)絡(luò)特性分析及控制 (穩(wěn)定性、數(shù)據(jù)流通等 )等幾個方面。在利用復(fù)雜網(wǎng)絡(luò)理論對實(shí)際網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行研究時，用來刻畫其宏觀拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)特征量主要有度分布，平均路徑長度、聚類系數(shù)、介數(shù)等等 。隨著對網(wǎng)絡(luò)性質(zhì)的物理意義及數(shù)學(xué)特性的研究分析，人們發(fā)現(xiàn)包括 Inter 在內(nèi)的許多網(wǎng)絡(luò)有一個共同的性質(zhì)，即社團(tuán)特性或者稱為群聚現(xiàn)象。也就是說網(wǎng)絡(luò)是由若干東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 2 個“群 (group)” 或“模塊 (module)“， 在群內(nèi)部節(jié)點(diǎn)的連接非常緊密，而相對的在各個群組之間的連接則較為稀疏。如圖 所示為一個具有明顯社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)，虛線圓中包含的部分就代表了網(wǎng)絡(luò)的三個子團(tuán)。 圖 社團(tuán)結(jié)構(gòu)劃分示意圖 the illustration of munity structure 一般而言，社團(tuán)包含 模塊、類、群、組等各種含義。例如 由大量網(wǎng)站社團(tuán)社團(tuán)組成，同一社團(tuán)的各站點(diǎn)涉及的都是一些共同話題（見文獻(xiàn) [7~9]）。在電信網(wǎng)絡(luò)或生物網(wǎng)絡(luò)中，也可以根據(jù)不同的性質(zhì)將各節(jié)點(diǎn)化為不同的社團(tuán)（見文獻(xiàn) [10~12]）。提出網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，對于分析網(wǎng)絡(luò)結(jié)構(gòu)和特性至關(guān)重要。社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)在很多領(lǐng)域都有廣泛應(yīng)用，比如生物學(xué)、物理學(xué)、計算機(jī)圖形學(xué)、社會學(xué)（見文獻(xiàn) [13~14]）等。 社團(tuán)特性作為復(fù)雜網(wǎng)絡(luò)的一個普遍現(xiàn)象已經(jīng)在很多實(shí)際網(wǎng)絡(luò)中得到了證實(shí)：文獻(xiàn)[15]根據(jù)爵士樂音樂家是否曾在一個樂隊演奏作為二者有聯(lián)系的邊，構(gòu)造了一個由 jazz音樂家組成的網(wǎng)絡(luò)，并發(fā)現(xiàn)在此網(wǎng)絡(luò)中存在著明顯的社團(tuán)現(xiàn)象；文獻(xiàn) [16]揭示了 Inter AS 級拓?fù)渲械纳鐖F(tuán)結(jié)構(gòu)與 AS 地理分布之間的關(guān)系。目前對于復(fù)雜網(wǎng)絡(luò)中的社團(tuán)特性的研究主要集中在社團(tuán)劃分算法、社團(tuán)結(jié)構(gòu)研究及基于社團(tuán)結(jié)構(gòu)的建模：例如文獻(xiàn) [17]提出了一種基于信息編碼為標(biāo)準(zhǔn)的社團(tuán)劃分算法，擴(kuò)展了之前通常是基于模塊度 [18,19]或是特征向量 [20]的社團(tuán)劃分算法；文獻(xiàn) [21]則將社團(tuán)劃分算法又?jǐn)U展到了加權(quán)網(wǎng)絡(luò)中。文獻(xiàn) [22]發(fā)現(xiàn)了在很多實(shí)際網(wǎng)絡(luò)中的社團(tuán) 結(jié)構(gòu)存在著疊加性和層次性；文獻(xiàn) [23]提出了一種基于社團(tuán)的網(wǎng)絡(luò)演化模型。 目前對于復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的研究在國際上已經(jīng)相對成熟，可是針對以互聯(lián)網(wǎng)拓?fù)涮卣鳛榛A(chǔ)的社團(tuán)結(jié)構(gòu)研究還相對不足，傳統(tǒng)社團(tuán)發(fā)現(xiàn)算法并不能很好的反應(yīng)互聯(lián)網(wǎng)特有的拓?fù)涮卣?。本文將根?jù)這些不足展開對互聯(lián)網(wǎng)特有的社團(tuán)結(jié)構(gòu)特征的研究。 互聯(lián)網(wǎng)可視化研究現(xiàn)狀 互聯(lián)網(wǎng)的結(jié)構(gòu)非常復(fù)雜，如果僅用數(shù)據(jù)表格或文字的形式來表示網(wǎng)絡(luò)，理解起來非東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 3 常 困難 ， 導(dǎo)致網(wǎng)絡(luò)所包含的信息無從體現(xiàn)。將復(fù)雜網(wǎng)絡(luò)方便、直觀地表示出來的最好方法是將其進(jìn)行可視化