掃一掃
關(guān)注中圖網(wǎng)
官方微博
>
>
復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)理論與應(yīng)用
本類五星書更多>
-
>
全國(guó)計(jì)算機(jī)等級(jí)考試最新真考題庫(kù)模擬考場(chǎng)及詳解·二級(jí)MSOffice高級(jí)應(yīng)用
-
>
決戰(zhàn)行測(cè)5000題(言語(yǔ)理解與表達(dá))
-
>
軟件性能測(cè)試.分析與調(diào)優(yōu)實(shí)踐之路
-
>
第一行代碼Android
-
>
JAVA持續(xù)交付
-
>
EXCEL最強(qiáng)教科書(完全版)(全彩印刷)
-
>
深度學(xué)習(xí)
中圖價(jià):¥101.1
加入購(gòu)物車
復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)理論與應(yīng)用 版權(quán)信息
- ISBN：9787030671790
- 條形碼：9787030671790 ; 978-7-03-067179-0
- 裝幀：一般膠版紙
- 冊(cè)數(shù)：暫無
- 重量：暫無
- 所屬分類：>
復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)理論與應(yīng)用 本書特色
適讀人群 ：計(jì)算機(jī)、自動(dòng)化等專業(yè)高年級(jí)本科生、研究生和相關(guān)研究人員該書的主要內(nèi)容包括了近年來國(guó)內(nèi)外在該領(lǐng)域*重要的研究成果，如社團(tuán)的主要發(fā)現(xiàn)方法、社團(tuán)發(fā)現(xiàn)合理性的評(píng)價(jià)指標(biāo)、社團(tuán)結(jié)構(gòu)的分辨率和視野的局限性、社團(tuán)的層次結(jié)構(gòu)等
復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)理論與應(yīng)用 內(nèi)容簡(jiǎn)介
本書主要介紹復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)理論與應(yīng)用。復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)旨在揭示復(fù)雜網(wǎng)絡(luò)中真實(shí)存在的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。研究復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)，在分析實(shí)體復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、理解現(xiàn)實(shí)復(fù)雜網(wǎng)絡(luò)的功能、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)隱藏的規(guī)律和預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的動(dòng)力學(xué)行為等方面具有重要的現(xiàn)實(shí)意義，并且具有廣泛的應(yīng)用前景。本書首先介紹復(fù)雜網(wǎng)絡(luò)基礎(chǔ)知識(shí)、社團(tuán)定義及相關(guān)基礎(chǔ)和社團(tuán)定量刻畫；其次介紹主流的社團(tuán)發(fā)現(xiàn)方法、算法和社團(tuán)結(jié)構(gòu)的層次性；很后介紹社團(tuán)發(fā)現(xiàn)的應(yīng)用。 本書可供計(jì)算機(jī)、自動(dòng)化等專業(yè)高年級(jí)本科生、研究生和相關(guān)研究人員參考。
復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)理論與應(yīng)用 目錄
目錄
前言
第1章 復(fù)雜網(wǎng)絡(luò)基礎(chǔ)知識(shí) 1
1.1 復(fù)雜網(wǎng)絡(luò)概述 1
1.2 圖論基礎(chǔ) 2
1.2.1 圖的矩陣表示 3
1.2.2 度分布 5
1.3 無標(biāo)度網(wǎng)絡(luò) 7
1.3.1 泊松分布與冪律分布 7
1.3.2 BA模型 9
1.4 小世界網(wǎng)絡(luò) 13
1.4.1 平均路徑長(zhǎng)度與聚類系數(shù) 13
1.4.2 WS模型和NW模型 16
1.5 度相關(guān)性 20
1.6 現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò) 22
參考文獻(xiàn) 24
第2章 社團(tuán)定義及相關(guān)基礎(chǔ) 26
2.1 網(wǎng)絡(luò)的社團(tuán)特性 26
2.1.1 網(wǎng)絡(luò)社團(tuán)的普遍性 26
2.1.2 社團(tuán)定義 34
2.1.3 社團(tuán)內(nèi)部結(jié)構(gòu) 41
2.2 基準(zhǔn)網(wǎng)絡(luò)及其社團(tuán)結(jié)構(gòu) 45
2.2.1 計(jì)算機(jī)生成的基準(zhǔn)網(wǎng)絡(luò) 45
2.2.2 實(shí)際基準(zhǔn)網(wǎng)絡(luò) 47
2.2.3 劃分結(jié)果比較方法 50
參考文獻(xiàn) 52
第3章 社團(tuán)定量刻畫 55
3.1 社團(tuán)分割的合理化指標(biāo) 55
3.2 Newman模塊度 56
3.2.1 配置模型 57
3.2.2 基于Newman模塊度的GN算法 57
3.2.3 Newman模塊度的局限性 60
3.3 基于信息論的社團(tuán)分割合理性度量 68
3.3.1 網(wǎng)絡(luò)中的隨機(jī)行走理論 69
3.3.2 基于隨機(jī)行走理論的模塊度 75
3.3.3 基于編碼的模塊度 76
參考文獻(xiàn) 77
第4章 基于尋優(yōu)的社團(tuán)發(fā)現(xiàn)方法 79
4.1 貪婪算法 79
4.1.1 基于Newman模塊度的尋優(yōu)方法 79
4.1.2 基于編碼模塊度的尋優(yōu)方法 85
4.2 蟻群算法 90
4.2.1 基于Newman模塊度的尋優(yōu)方法 92
4.2.2 基于編碼模塊度的尋優(yōu)方法 94
4.3 模擬退火算法 97
4.3.1 基于Newman模塊度的尋優(yōu)方法 98
4.3.2 基于編碼模塊度的尋優(yōu)方法 101
參考文獻(xiàn) 102
第5章 基于直觀概念的社團(tuán)發(fā)現(xiàn)算法 104
5.1 分裂算法 104
5.2 網(wǎng)絡(luò)合并算法 116
5.2.1 網(wǎng)絡(luò)合并算法概述 116
5.2.2 相似度指標(biāo) 124
5.2.3 基于相似度的網(wǎng)絡(luò)合并 126
5.3 譜分析算法 126
5.3.1 基于譜分析的社團(tuán)劃分算法 129
5.3.2 網(wǎng)絡(luò)矩陣譜分析方法的綜合分析 136
參考文獻(xiàn) 140
第6章 重疊社團(tuán)發(fā)現(xiàn)算法 142
6.1 重疊社團(tuán)的定義 142
6.2 派系過濾算法 144
6.3 基于邊的社團(tuán)發(fā)現(xiàn)算法 150
參考文獻(xiàn) 166
第7章 多尺度社團(tuán)發(fā)現(xiàn)與網(wǎng)絡(luò)的層次結(jié)構(gòu) 168
7.1 社團(tuán)發(fā)現(xiàn)方法的分辨率局限特性 168
7.2 多尺度社團(tuán)發(fā)現(xiàn)方法 172
7.2.1 基于社團(tuán)數(shù)量的多尺度社團(tuán)發(fā)現(xiàn)方法 173
7.2.2 基于參數(shù)化模塊度的多尺度社團(tuán)發(fā)現(xiàn)方法 183
7.2.3 不同尺度社團(tuán)結(jié)構(gòu)之間的嵌套性分析 191
參考文獻(xiàn) 195
第8章 社團(tuán)發(fā)現(xiàn)的應(yīng)用 197
8.1 用戶通話網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu) 197
8.1.1 用戶通話網(wǎng)絡(luò)模型構(gòu)建及拓?fù)浣Y(jié)構(gòu) 197
8.1.2 通話網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)及應(yīng)用分析 203
8.2 BBS用戶網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu) 208
8.2.1 BBS用戶網(wǎng)絡(luò)模型構(gòu)建及拓?fù)浣Y(jié)構(gòu) 208
8.2.2 社團(tuán)發(fā)現(xiàn)與熱點(diǎn)主題 212
8.3 復(fù)雜公交網(wǎng)絡(luò)的性能分析 215
8.3.1 城市公交網(wǎng)絡(luò)模型 216
8.3.2 社團(tuán)劃分及其應(yīng)用 223
8.3.3 公交停靠站點(diǎn)網(wǎng)絡(luò)抗毀性分析和網(wǎng)絡(luò)優(yōu)化 225
參考文獻(xiàn) 227
前言
第1章 復(fù)雜網(wǎng)絡(luò)基礎(chǔ)知識(shí) 1
1.1 復(fù)雜網(wǎng)絡(luò)概述 1
1.2 圖論基礎(chǔ) 2
1.2.1 圖的矩陣表示 3
1.2.2 度分布 5
1.3 無標(biāo)度網(wǎng)絡(luò) 7
1.3.1 泊松分布與冪律分布 7
1.3.2 BA模型 9
1.4 小世界網(wǎng)絡(luò) 13
1.4.1 平均路徑長(zhǎng)度與聚類系數(shù) 13
1.4.2 WS模型和NW模型 16
1.5 度相關(guān)性 20
1.6 現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò) 22
參考文獻(xiàn) 24
第2章 社團(tuán)定義及相關(guān)基礎(chǔ) 26
2.1 網(wǎng)絡(luò)的社團(tuán)特性 26
2.1.1 網(wǎng)絡(luò)社團(tuán)的普遍性 26
2.1.2 社團(tuán)定義 34
2.1.3 社團(tuán)內(nèi)部結(jié)構(gòu) 41
2.2 基準(zhǔn)網(wǎng)絡(luò)及其社團(tuán)結(jié)構(gòu) 45
2.2.1 計(jì)算機(jī)生成的基準(zhǔn)網(wǎng)絡(luò) 45
2.2.2 實(shí)際基準(zhǔn)網(wǎng)絡(luò) 47
2.2.3 劃分結(jié)果比較方法 50
參考文獻(xiàn) 52
第3章 社團(tuán)定量刻畫 55
3.1 社團(tuán)分割的合理化指標(biāo) 55
3.2 Newman模塊度 56
3.2.1 配置模型 57
3.2.2 基于Newman模塊度的GN算法 57
3.2.3 Newman模塊度的局限性 60
3.3 基于信息論的社團(tuán)分割合理性度量 68
3.3.1 網(wǎng)絡(luò)中的隨機(jī)行走理論 69
3.3.2 基于隨機(jī)行走理論的模塊度 75
3.3.3 基于編碼的模塊度 76
參考文獻(xiàn) 77
第4章 基于尋優(yōu)的社團(tuán)發(fā)現(xiàn)方法 79
4.1 貪婪算法 79
4.1.1 基于Newman模塊度的尋優(yōu)方法 79
4.1.2 基于編碼模塊度的尋優(yōu)方法 85
4.2 蟻群算法 90
4.2.1 基于Newman模塊度的尋優(yōu)方法 92
4.2.2 基于編碼模塊度的尋優(yōu)方法 94
4.3 模擬退火算法 97
4.3.1 基于Newman模塊度的尋優(yōu)方法 98
4.3.2 基于編碼模塊度的尋優(yōu)方法 101
參考文獻(xiàn) 102
第5章 基于直觀概念的社團(tuán)發(fā)現(xiàn)算法 104
5.1 分裂算法 104
5.2 網(wǎng)絡(luò)合并算法 116
5.2.1 網(wǎng)絡(luò)合并算法概述 116
5.2.2 相似度指標(biāo) 124
5.2.3 基于相似度的網(wǎng)絡(luò)合并 126
5.3 譜分析算法 126
5.3.1 基于譜分析的社團(tuán)劃分算法 129
5.3.2 網(wǎng)絡(luò)矩陣譜分析方法的綜合分析 136
參考文獻(xiàn) 140
第6章 重疊社團(tuán)發(fā)現(xiàn)算法 142
6.1 重疊社團(tuán)的定義 142
6.2 派系過濾算法 144
6.3 基于邊的社團(tuán)發(fā)現(xiàn)算法 150
參考文獻(xiàn) 166
第7章 多尺度社團(tuán)發(fā)現(xiàn)與網(wǎng)絡(luò)的層次結(jié)構(gòu) 168
7.1 社團(tuán)發(fā)現(xiàn)方法的分辨率局限特性 168
7.2 多尺度社團(tuán)發(fā)現(xiàn)方法 172
7.2.1 基于社團(tuán)數(shù)量的多尺度社團(tuán)發(fā)現(xiàn)方法 173
7.2.2 基于參數(shù)化模塊度的多尺度社團(tuán)發(fā)現(xiàn)方法 183
7.2.3 不同尺度社團(tuán)結(jié)構(gòu)之間的嵌套性分析 191
參考文獻(xiàn) 195
第8章 社團(tuán)發(fā)現(xiàn)的應(yīng)用 197
8.1 用戶通話網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu) 197
8.1.1 用戶通話網(wǎng)絡(luò)模型構(gòu)建及拓?fù)浣Y(jié)構(gòu) 197
8.1.2 通話網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)及應(yīng)用分析 203
8.2 BBS用戶網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu) 208
8.2.1 BBS用戶網(wǎng)絡(luò)模型構(gòu)建及拓?fù)浣Y(jié)構(gòu) 208
8.2.2 社團(tuán)發(fā)現(xiàn)與熱點(diǎn)主題 212
8.3 復(fù)雜公交網(wǎng)絡(luò)的性能分析 215
8.3.1 城市公交網(wǎng)絡(luò)模型 216
8.3.2 社團(tuán)劃分及其應(yīng)用 223
8.3.3 公交停靠站點(diǎn)網(wǎng)絡(luò)抗毀性分析和網(wǎng)絡(luò)優(yōu)化 225
參考文獻(xiàn) 227
展開全部
復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)理論與應(yīng)用 節(jié)選
第1章 復(fù)雜網(wǎng)絡(luò)基礎(chǔ)知識(shí) 網(wǎng)絡(luò)規(guī)模的擴(kuò)大增加了大型復(fù)雜網(wǎng)絡(luò)的研究難度。為了在可接受的計(jì)算成本下發(fā)現(xiàn)并研究網(wǎng)絡(luò)中蘊(yùn)含的規(guī)律，有必要簡(jiǎn)化研究對(duì)象，因而社團(tuán)發(fā)現(xiàn)算法越來越受人們的關(guān)注。在復(fù)雜網(wǎng)絡(luò)中發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)，并以這些社團(tuán)結(jié)構(gòu)為單位形成的網(wǎng)絡(luò)作為研究對(duì)象，能夠大幅減少研究的復(fù)雜度。 本章介紹復(fù)雜網(wǎng)絡(luò)及其在科學(xué)領(lǐng)域和現(xiàn)實(shí)世界中的應(yīng)用，主要介紹與社團(tuán)發(fā)現(xiàn)有關(guān)的復(fù)雜網(wǎng)絡(luò)基礎(chǔ)知識(shí)，包括復(fù)雜網(wǎng)絡(luò)概述、圖論基礎(chǔ)、無標(biāo)度網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)、度相關(guān)性和現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò)等內(nèi)容。 1.1 復(fù)雜網(wǎng)絡(luò)概述 物理學(xué)家霍金認(rèn)為：21世紀(jì)是復(fù)雜性的世紀(jì)。作為研究復(fù)雜性科學(xué)和復(fù)雜系統(tǒng)的有力工具，復(fù)雜網(wǎng)絡(luò)已成為學(xué)術(shù)界研究的一個(gè)熱點(diǎn)，在工程技術(shù)、社會(huì)、政治、醫(yī)藥、經(jīng)濟(jì)和管理領(lǐng)域都有著潛在和廣泛的應(yīng)用。復(fù)雜網(wǎng)絡(luò)借助圖論和統(tǒng)計(jì)物理的方法，可捕捉并描述系統(tǒng)的演化機(jī)制和規(guī)律，同時(shí)也能很好地分析系統(tǒng)的整體行為。復(fù)雜網(wǎng)絡(luò)的復(fù)雜性主要體現(xiàn)在以下幾個(gè)方面。 (1) 結(jié)構(gòu)復(fù)雜性：網(wǎng)絡(luò)結(jié)構(gòu)縱橫交錯(cuò)、復(fù)雜混亂，且連接結(jié)構(gòu)可能隨時(shí)發(fā)生改變。例如，萬(wàn)維網(wǎng)(world wide web， WWW)每天都會(huì)產(chǎn)生和刪除許多網(wǎng)頁(yè)和鏈接。另外，節(jié)點(diǎn)之間的連接可能具有不同的權(quán)重和方向。例如，交通網(wǎng)絡(luò)中每條公路上都有不同數(shù)量和方向的汽車在行駛。 (2) 節(jié)點(diǎn)復(fù)雜性：網(wǎng)絡(luò)中的節(jié)點(diǎn)可能是具有分岔和混沌等復(fù)雜非線性行為的動(dòng)力系統(tǒng)。例如，基因網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都具有復(fù)雜的時(shí)間演化行為。一個(gè)網(wǎng)絡(luò)中還可能存在多種不同類型的節(jié)點(diǎn)。例如，控制哺乳動(dòng)物細(xì)胞分裂的生化網(wǎng)絡(luò)包含各種各樣的蛋白質(zhì)和酶。 (3) 各種復(fù)雜性因素的相互影響：現(xiàn)實(shí)中的復(fù)雜網(wǎng)絡(luò)每時(shí)每刻都會(huì)受到各種因素的影響。例如，如果耦合神經(jīng)元同時(shí)被重復(fù)激活，它們之間的連接就會(huì)加強(qiáng)，這也是記憶和學(xué)習(xí)的基礎(chǔ)。另外，各種不同類型的網(wǎng)絡(luò)之間也存在密切的聯(lián)系，從而相互影響，如電力網(wǎng)絡(luò)的故障可能會(huì)導(dǎo)致網(wǎng)絡(luò)流量變慢、金融機(jī)構(gòu)關(guān)閉、運(yùn)輸系統(tǒng)失去控制等一系列連鎖反應(yīng)。 由于真實(shí)網(wǎng)絡(luò)的規(guī)模龐大、結(jié)構(gòu)復(fù)雜，其拓?fù)浣Y(jié)構(gòu)在21世紀(jì)初才得到廣泛的研究。人們對(duì)真實(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究大致經(jīng)歷了以下過程：*初，研究者們認(rèn)為真實(shí)網(wǎng)絡(luò)各要素之間的關(guān)系可以用一些規(guī)則的結(jié)構(gòu)表示，如二維平面上的網(wǎng)格；20世紀(jì)50～90年代末，人們主要用隨機(jī)網(wǎng)絡(luò)描述沒有明確設(shè)計(jì)原則的大規(guī)模網(wǎng)絡(luò)；近年來，研究者們發(fā)現(xiàn)大量的真實(shí)網(wǎng)絡(luò)既不是隨機(jī)網(wǎng)絡(luò)，也不是規(guī)則網(wǎng)絡(luò)，而是統(tǒng)計(jì)特性與前兩者都不同的網(wǎng)絡(luò)，其中*有影響的復(fù)雜網(wǎng)絡(luò)模型是小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)。下文將介紹復(fù)雜網(wǎng)絡(luò)中需要用到的基本概念。 網(wǎng)絡(luò)可以抽象為一個(gè)由節(jié)點(diǎn)集V和邊集E組成的圖，節(jié)點(diǎn)數(shù)記為，邊數(shù)記為。網(wǎng)絡(luò)中節(jié)點(diǎn)和邊與具體研究對(duì)象緊密相關(guān)。例如，在生命系統(tǒng)的巨型遺傳網(wǎng)絡(luò)中，節(jié)點(diǎn)表示蛋白質(zhì)，邊表示蛋白質(zhì)之間的相互作用；在WWW中，節(jié)點(diǎn)表示各個(gè)不同的頁(yè)面，邊表示頁(yè)面之間的鏈接。節(jié)點(diǎn)數(shù)和邊數(shù)均有限的圖稱為有限圖，否則稱為無限圖。由于研究的網(wǎng)絡(luò)都是真實(shí)網(wǎng)絡(luò)的模型，一般為有限圖。如果網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)對(duì)與對(duì)應(yīng)同一條邊，則稱該網(wǎng)絡(luò)為無向網(wǎng)絡(luò)，否則稱為有向網(wǎng)絡(luò)。兩個(gè)端點(diǎn)相同的邊稱為環(huán)(loop)，有公共起點(diǎn)并且同時(shí)具有公共終點(diǎn)的兩條邊稱為平行邊或重邊。無環(huán)并且沒有重邊的圖稱為簡(jiǎn)單圖，任何兩個(gè)節(jié)點(diǎn)之間都有邊相連的簡(jiǎn)單無向圖稱為完全圖。現(xiàn)實(shí)世界中的網(wǎng)絡(luò)往往需要根據(jù)某種度量標(biāo)準(zhǔn)，為網(wǎng)絡(luò)上的每個(gè)點(diǎn)和每條邊都賦予相應(yīng)的權(quán)值，這種網(wǎng)絡(luò)稱為加權(quán)網(wǎng)絡(luò)[1，2]。例如，在交通網(wǎng)中，每?jī)蓚(gè)站點(diǎn)之間的距離不同，而且每條線路上的車流量往往也不同，即每條邊具有不同的權(quán)值。沒有賦予權(quán)重的網(wǎng)絡(luò)稱為無權(quán)網(wǎng)絡(luò)，無權(quán)網(wǎng)絡(luò)也可以看作是每條邊的權(quán)值都是1的網(wǎng)絡(luò)。點(diǎn)和邊的權(quán)值通常用和表示。無向網(wǎng)絡(luò)中，一個(gè)點(diǎn)的權(quán)值是與之相連的所有邊的權(quán)值總和，即。 介數(shù)分為節(jié)點(diǎn)介數(shù)和邊介數(shù)。節(jié)點(diǎn)介數(shù)為網(wǎng)絡(luò)中所有*短路徑中經(jīng)過該節(jié)點(diǎn)的數(shù)目比例，邊介數(shù)的含義和節(jié)點(diǎn)介數(shù)相似。介數(shù)反映了節(jié)點(diǎn)和邊在整個(gè)網(wǎng)絡(luò)中的地位和作用，有很具體的現(xiàn)實(shí)意義。在社會(huì)關(guān)系網(wǎng)絡(luò)或技術(shù)網(wǎng)絡(luò)中，介數(shù)的分布特征反映了不同人員、資源、技術(shù)等因素在生產(chǎn)關(guān)系中的地位，對(duì)在網(wǎng)絡(luò)中發(fā)現(xiàn)和保護(hù)關(guān)鍵資源和技術(shù)具有非常重要的意義。 1.2 圖論基礎(chǔ) 圖論*早起源于1736年歐拉(Euler)所解決的哥尼斯堡(Konigsberg)七橋問題，現(xiàn)已廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、商業(yè)、心理學(xué)等領(lǐng)域。本節(jié)介紹圖的矩陣表示和度分布。 1.2.1 圖的矩陣表示 任何復(fù)雜的網(wǎng)絡(luò)都可以表示為圖，借助矩陣對(duì)圖進(jìn)行研究，可以大大簡(jiǎn)化和促進(jìn)對(duì)圖的分析。 1. 鄰接矩陣 每一個(gè)圖都是由節(jié)點(diǎn)和連接一對(duì)節(jié)點(diǎn)之間的連線組成，其中連線的長(zhǎng)度和節(jié)點(diǎn)的位置無關(guān)緊要。圖1-1是同一個(gè)圖的兩種表示。 圖1-1 同一個(gè)圖的兩種表示 定義1-1 設(shè)是一個(gè)簡(jiǎn)單圖，它有個(gè)節(jié)點(diǎn)，則階方陣稱為圖的鄰接矩陣。 圖1-2 5個(gè)節(jié)點(diǎn)的簡(jiǎn)單無向圖 其中，表示節(jié)點(diǎn)相鄰，表示節(jié)點(diǎn)不相鄰。例如，5個(gè)節(jié)點(diǎn)的簡(jiǎn)單無向圖(圖1-2)的鄰接矩陣為 當(dāng)給定的簡(jiǎn)單圖是無向圖時(shí)(圖1-2)，鄰接矩陣對(duì)稱；當(dāng)給定的簡(jiǎn)單圖是有向圖時(shí)，鄰接矩陣不一定對(duì)稱。 2. 關(guān)聯(lián)矩陣 定義1-2 設(shè)圖有個(gè)節(jié)點(diǎn)和條邊，和。的關(guān)聯(lián)矩陣定義為的二進(jìn)制矩陣，其中若與關(guān)聯(lián)，則；否則。 容易看出，矩陣的行對(duì)應(yīng)個(gè)節(jié)點(diǎn)，列對(duì)應(yīng)條邊。例如，圖1-3為6個(gè)節(jié)點(diǎn)8條邊的簡(jiǎn)單無向圖，關(guān)聯(lián)矩陣為 圖1-3 6個(gè)節(jié)點(diǎn)8條邊的簡(jiǎn)單無向圖 的第行元素的和為deg()，這對(duì)鄰接矩陣顯然也成立，而且每一列的和都是2，這是由于每條邊都與且僅與兩個(gè)節(jié)點(diǎn)關(guān)聯(lián)。令為的對(duì)角矩陣(所有的非對(duì)角線元素都為0)，滿足。 容易驗(yàn)證，對(duì)于鄰接矩陣、關(guān)聯(lián)矩陣和對(duì)角矩陣，存在。無論是鄰接矩陣還是關(guān)聯(lián)矩陣都可以確定一個(gè)唯一的圖；反過來，一個(gè)圖可以有多個(gè)鄰接矩陣和關(guān)聯(lián)矩陣。這是由于對(duì)于鄰接矩陣，可以改變節(jié)點(diǎn)的標(biāo)記序列；對(duì)于關(guān)聯(lián)矩陣，可以改變節(jié)點(diǎn)和邊的標(biāo)記序列。 3. 距離矩陣 顧名思義，距離矩陣存儲(chǔ)的是節(jié)點(diǎn)間的距離。 對(duì)于圖，定義的距離矩陣的元素。顯然。另外，根據(jù)距離的對(duì)稱性，有，即圖的距離矩陣為對(duì)稱矩陣。例如，圖1-4的距離矩陣為 圖1-4 6個(gè)節(jié)點(diǎn)的簡(jiǎn)單無向圖 1.2.2 度分布 度是節(jié)點(diǎn)屬性中簡(jiǎn)單而又重要的概念，是網(wǎng)絡(luò)的一個(gè)重要統(tǒng)計(jì)特征。與節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的數(shù)目，或者連接到該節(jié)點(diǎn)的邊的條數(shù)稱為節(jié)點(diǎn)的度。節(jié)點(diǎn)的度有兩個(gè)延伸概念，一個(gè)是*小度；另一個(gè)是平均度。*小度是指網(wǎng)絡(luò)中度*小的節(jié)點(diǎn)的度。平均度是指網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度的算術(shù)平均值，即 (1-1) 在任意圖中，因?yàn)槊織l邊必關(guān)聯(lián)兩個(gè)節(jié)點(diǎn)，而一條邊給予每個(gè)關(guān)聯(lián)節(jié)點(diǎn)的度值貢獻(xiàn)為1，所以圖中節(jié)點(diǎn)度值的總和等于邊數(shù)的兩倍： (1-2) 在有向網(wǎng)絡(luò)中，度分為入度和出度。節(jié)點(diǎn)的入度是從其他節(jié)點(diǎn)指向該節(jié)點(diǎn)的邊的數(shù)目，記為： (1-3) 出度是從該節(jié)點(diǎn)指向其他節(jié)點(diǎn)的邊的數(shù)目，記為： (1-4) 在無向圖中，可以看成是將每個(gè)節(jié)點(diǎn)映射到一個(gè)非負(fù)整數(shù)的函數(shù)，即()。在圖1-2的鄰接矩陣(G)中，可以看到，第行元素由節(jié)點(diǎn)出發(fā)的邊決定，第行中值為1的元素?cái)?shù)目等于的出度。同理，在第列中值為1的元素?cái)?shù)目是的入度。不難發(fā)現(xiàn)，一個(gè)節(jié)點(diǎn)的度越大，說明它在網(wǎng)絡(luò)中的地位越重要。 網(wǎng)絡(luò)中節(jié)點(diǎn)度的分布情況可用分布函數(shù)描述，表示一個(gè)隨機(jī)選定節(jié)點(diǎn)的度恰好為的概率。在實(shí)證研究中，經(jīng)常以頻率代替概率的模擬統(tǒng)計(jì)方法計(jì)算度分布，即取網(wǎng)絡(luò)中度值為的節(jié)點(diǎn)數(shù)與節(jié)點(diǎn)總數(shù)的比值，網(wǎng)絡(luò)中所有節(jié)點(diǎn)度的平均值稱為網(wǎng)絡(luò)的平均度，記為，。圖1-5中共有10個(gè)節(jié)點(diǎn)，其中度值為3的節(jié)點(diǎn)有6個(gè)，度值為4的節(jié)點(diǎn)有3個(gè)，度值為6的節(jié)點(diǎn)有1個(gè)，因此該圖的度分布為。 圖1-5 由10個(gè)節(jié)點(diǎn)構(gòu)成的簡(jiǎn)單無向圖 度分布是區(qū)分不同結(jié)構(gòu)復(fù)雜網(wǎng)絡(luò)的一個(gè)重要指標(biāo)。例如，階完全圖所有節(jié)點(diǎn)都與其他任意節(jié)點(diǎn)相連，因此它的節(jié)點(diǎn)度值都是，度分布是。星形網(wǎng)絡(luò)的度分布是兩點(diǎn)分布，而規(guī)則網(wǎng)絡(luò)的度分布是單點(diǎn)分布。 根據(jù)不同類型的度分布，可以將網(wǎng)絡(luò)分為均勻網(wǎng)絡(luò)和非均勻網(wǎng)絡(luò)。規(guī)則格子網(wǎng)絡(luò)和完全隨機(jī)網(wǎng)絡(luò)都屬于均勻網(wǎng)絡(luò)，前者有簡(jiǎn)單的度序列，是由于所有節(jié)點(diǎn)具有相同的度，度分布為Delta分布，函數(shù)圖形為單個(gè)尖峰的形狀。后者的
書友推薦
- >
名家?guī)阕x魯迅:故事新編
- >
龍榆生：詞曲概論/大家小書
- >
史學(xué)評(píng)論
- >
朝聞道
- >
伊索寓言-世界文學(xué)名著典藏-全譯本
- >
羅曼·羅蘭讀書隨筆-精裝
- >
羅庸西南聯(lián)大授課錄
- >
新文學(xué)天穹兩巨星--魯迅與胡適/紅燭學(xué)術(shù)叢書(紅燭學(xué)術(shù)叢書)
本類暢銷
