【正文】 整體上，根據(jù)復(fù)雜網(wǎng)絡(luò)理論，互聯(lián)網(wǎng)的結(jié)構(gòu)應(yīng)該具有分形特征。 圖 最大子圖 Fig biggest subgraph 相關(guān)特征量 定義 k核： 拓?fù)鋱D的 k核是指“在圖中反復(fù)去掉度小于等于 k 的節(jié)點(diǎn)及其連接所余下的子圖”。算法目標(biāo)是提取出最大子圖 C。“ traceroute from sourceIP to targetIP”中的 sourceIP、 targetIP 分別表示源 IP 和目的 IP，而“ *”表示這條探測鏈路上的設(shè)備不能及時(shí) 地 向源設(shè)備返回 ICMP TTL 到期消息的響應(yīng)。 表 Ark 位于亞洲的監(jiān)測點(diǎn) Ark monitors in Asia Name City Country Continent Organization Organization classification cjjkr Daejeon KR Asia KREONet1 research work mnlph Quezon City PH Asia ASTI research nrtjp Tokyo JP Asia APAN research work she Shenyang CN Asia Northeastern University university tpetw Hsinchu TW Asia TWAREN research work CAIDA 的測量源點(diǎn)分布在世界幾大洲內(nèi)，從不同的視角對互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)進(jìn)行全面的測量與分析。 定義 IP 級拓?fù)洌?traceroute 機(jī)制測量得到的選路路徑是 IP 地址級的路徑，除最后一跳之外，其它地址各對應(yīng)一個(gè)路由器接口地址。 如今，許多科學(xué)研究者都開始應(yīng)用復(fù)雜網(wǎng)絡(luò)理論和數(shù)據(jù)挖掘方法去分 析各種現(xiàn)象，解決實(shí)際的問題。將復(fù)雜網(wǎng)絡(luò)方便、直觀地表示出來的最好方法是將其進(jìn)行可視化。目前對于復(fù)雜網(wǎng)絡(luò)的研究主要包括網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)、網(wǎng)絡(luò)拓?fù)浣?、網(wǎng)絡(luò)特性分析及控制 (穩(wěn)定性、數(shù)據(jù)流通等 )等幾個(gè)方面。 東北大學(xué)碩士學(xué)位論文 錯(cuò)誤 !未找到引用源。 對于互聯(lián)網(wǎng)的社團(tuán)可視化問題，傳統(tǒng)的一些可視化算法僅僅只能做到整個(gè)網(wǎng)絡(luò)拓?fù)浼墑e的可視化，社團(tuán)結(jié)構(gòu)的可視化特點(diǎn)并不明晰，針對這種問題，本文在參考傳統(tǒng)節(jié)點(diǎn)布局方式的基礎(chǔ)上全新構(gòu)建節(jié)點(diǎn)布局，這種布局分為兩個(gè)層次：整個(gè)網(wǎng)絡(luò)的社團(tuán)之間位置布局、每個(gè)社團(tuán)的內(nèi)部節(jié)點(diǎn)位置布局。 分類號 密級 U D C 學(xué) 位 論 文 基于互聯(lián)網(wǎng)拓?fù)涮卣鞯亩嗔６壬鐖F(tuán)發(fā)現(xiàn)算法及其可視化 作 者 姓 名 ： 于群 指 導(dǎo) 教 師 ： 徐久強(qiáng) 教授 東北大學(xué)信息科學(xué)與工程學(xué)院 申請學(xué)位級別： 碩士 學(xué) 科 類 別 ： 工學(xué) 學(xué)科專業(yè)名稱： 計(jì)算機(jī) 軟件理論 論文提交日期： 20xx 年 6 月 論文答辯日期： 20xx 年 6 月 學(xué)位授予日期： 20xx 年 7 月 答辯委員會主席： 評 閱 人 ： 東 北 大 學(xué) 20xx 年 6 月 A Thesis for the Degree of Master in Computer Software and Theory Community Structure Detecting and Visualization of Multiple Granularity Based on Inter Network Topology By Yu Qun Supervisor: Professor Xu jiuqiang Northeastern University June 20xx I 獨(dú)創(chuàng)性聲明 本人聲明 ， 所呈交的學(xué)位論文是在導(dǎo)師的指導(dǎo)下完成的。其中，第一個(gè)層次又分兩個(gè)小層次：其一，根據(jù)物理類比法，模擬物理系統(tǒng)環(huán)境，全自動布局社團(tuán)節(jié)點(diǎn)；其二，在第一步完成之后，采用動態(tài)交互布局模式，如果第一步布局有不合理的地方 ，可手動調(diào)節(jié)社團(tuán)節(jié)點(diǎn)位置。 V 東北大學(xué)碩士學(xué)位論文 目 錄 VI 目 錄 獨(dú)創(chuàng)性聲明 .............................................................................................................................................................................. I 摘 要 .......................................................................................................................................................................................... II Abstract ....................................................................................................................................................................................III 第 1 章 緒 論 ........................................................................................................................................................................ 1 課題研究的背景與意義 ..................................................................................................... 1 互聯(lián)網(wǎng)的社團(tuán)結(jié)構(gòu)研究現(xiàn)狀 .................................................................................... 1 互聯(lián)網(wǎng)可視化研究現(xiàn)狀 ........................................................................................... 2 本文研究的意義 ....................................................................................................... 3 本文組織結(jié)構(gòu) ..................................................................................................................... 4 第 2 章 互聯(lián)網(wǎng)網(wǎng)絡(luò)數(shù)據(jù)來源及處理 ......................................................................................................................... 6 互聯(lián)網(wǎng)網(wǎng)絡(luò)數(shù)據(jù)來源 ......................................................................................................... 6 原始網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理 ......................................................................................................... 8 數(shù)據(jù)格式的處理 ....................................................................................................... 8 原始網(wǎng)絡(luò)拓?fù)? ........................................................................................................... 9 最大子圖的獲取 ..................................................................................................... 10 相關(guān)特征量 ....................................................................................................................... 12 本章小結(jié) ........................................................................................................................... 13 第 3 章 互聯(lián)網(wǎng)拓?fù)浠咎卣鞣治雠c多粒度社團(tuán)發(fā)現(xiàn)算法設(shè)計(jì) ................................................................ 14 互聯(lián)網(wǎng)拓?fù)浠咎卣鞣治? ............................................................................................... 14 多粒度社團(tuán)發(fā)現(xiàn)算法設(shè)計(jì)的總體思想 ........................................................................... 17 分而劃之 ......................................................................................................................... 19 層次折疊收縮算法 .................................................................................................. 19 鏈狀探測算法 .......................................................................................................... 24 高核數(shù)節(jié)點(diǎn)聚合探測算法 ...................................................................................... 26 中心節(jié)點(diǎn)組織探測算法 ......................................................................................... 32 各種網(wǎng)絡(luò)探測算法處理后的網(wǎng)絡(luò)效果 .................................................................. 35 合而聚之 ............................................................................................................................ 36 模塊度 ..................................................................................................................... 36 小社團(tuán)合并算法 .............................................................................