目錄
序
前言
第1章 緒論 1
1.1 概述 1
1.2 一般對(duì)稱性 5
1.2.1 對(duì)稱性基本內(nèi)涵 5
1.2.2 對(duì)稱性的類別 6
1.3 研究背景 8
1.3.1 作為真實(shí)網(wǎng)絡(luò)的重要性質(zhì)之一的對(duì)稱性 8
1.3.2 作為圖數(shù)據(jù)管理重要問題之一的對(duì)稱性 10
1.3.3 作為一種技術(shù)手段的圖對(duì)稱 13
第2章 網(wǎng)絡(luò)對(duì)稱性 14
2.1 圖論基礎(chǔ) 14
2.1.1 圖的基本概念 14
2.1.2 圖之間的關(guān)系 18
2.2 代數(shù)基礎(chǔ) 24
2.2.1 集合和群 24
2.2.2 置換以及置換群 25
2.2.3 自映射 27
2.2.4 軌道與自映射等價(jià)性 28
2.2.5 置換群及其子群 29
2.2.6 群的生成集 30
2.3 圖結(jié)構(gòu)對(duì)稱 31
2.3.1 圖對(duì)稱的概念 31
2.3.2 基本的變換操作 32
2.3.3 對(duì)稱性度量 33
2.4 本章小結(jié) 35
第3章 對(duì)稱網(wǎng)絡(luò)模型 36
3.1 概述 36
3.2 相似鏈接模式 37
3.2.1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集介紹 37
3.2.2 對(duì)稱二分子團(tuán) 37
3.2.3 精確相似鏈接模式 39
3.2.4 非精確相似鏈接模式 43
3.3 對(duì)稱網(wǎng)絡(luò)生成模型 45
3.3.1 基于相似鏈接模式的擇優(yōu)鏈接 45
3.3.2 服從特定分布的初始度 46
3.3.3 基于相似鏈接模式的網(wǎng)絡(luò)模型 47
3.4 實(shí)證分析 47
3.4.1 相似鏈接模式與網(wǎng)絡(luò)對(duì)稱性 47
3.4.2 沒有相似鏈接模式時(shí)的網(wǎng)絡(luò)對(duì)稱性 50
3.4.3 SLP模型的進(jìn)一步討論 53
3.5 本章小結(jié) 55
第4章 基于對(duì)稱的網(wǎng)絡(luò)度量 56
4.1 基于對(duì)稱的網(wǎng)絡(luò)結(jié)構(gòu)熵 56
4.1.1 結(jié)構(gòu)異構(gòu)性 56
4.1.2 基于自映射分區(qū)的結(jié)構(gòu)熵 58
4.1.3 結(jié)構(gòu)熵分析 61
4.1.4 基于對(duì)稱的結(jié)構(gòu)熵小結(jié) 65
4.2 基于對(duì)稱的圖距離度量 65
4.2.1 基于結(jié)構(gòu)的圖距離度量 66
4.2.2 子結(jié)構(gòu)豐富性向量 68
4.2.3 基于SAV的圖距離度量 69
4.2.4 基于子結(jié)構(gòu)豐富性的圖距離度量的變種 71
4.2.5 在人群結(jié)構(gòu)分析中的應(yīng)用 72
4.2.6 基于對(duì)稱的圖距離度量小結(jié) 74
4.3 本章小結(jié) 75
第5章 基于對(duì)稱的網(wǎng)絡(luò)結(jié)構(gòu)約簡(jiǎn) 76
5.1 概述 76
5.2 基本概念 77
5.2.1 網(wǎng)絡(luò)商 77
5.2.2 s-商 78
5.3 網(wǎng)絡(luò)商的性質(zhì) 79
5.3.1 網(wǎng)絡(luò)商的規(guī)模 80
5.3.2 異構(gòu)性 81
5.3.3 度分布 82
5.3.4 通信性質(zhì) 84
5.4 網(wǎng)絡(luò)商在社會(huì)網(wǎng)絡(luò)隱私保護(hù)中的應(yīng)用 86
5.4.1 k-對(duì)稱 86
5.4.2 基于B-骨架的可用性 88
5.5 網(wǎng)絡(luò)商的其他應(yīng)用 91
5.6 本章小結(jié) 92
第6章 利用圖的對(duì)稱性有效索引最短路徑 93
6.1 概述 93
6.2 背景知識(shí) 95
6.3 算法框架 97
6.4 基于軌道的壓縮 98
6.4.1 自映射作用下的子圖 98
6.4.2 為每個(gè)軌道生成BFS樹 101
6.5 壓縮的BFS樹 105
6.5.1 軌道鄰接性和可達(dá)性 106
6.5.2 壓縮的BFS樹 110
6.5.3 基于壓縮的BFS樹的最短路徑查詢回答 112
6.6 實(shí)驗(yàn)結(jié)果 114
6.6.1 真實(shí)網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果 114
6.6.2 模擬數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果 116
6.7 相關(guān)工作 119
6.8 本章小結(jié) 120
第7章 總結(jié)與展望 121
7.1 總結(jié) 121
7.2 對(duì)稱技術(shù)應(yīng)用局限性評(píng)述 121
7.3 進(jìn)一步的研究工作 122
7.3.1 非精確對(duì)稱理論及其應(yīng)用研究 123
7.3.2 局部對(duì)稱理論及實(shí)踐研究 123
7.3.3 圖穩(wěn)定化過程研究 123
7.3.4 對(duì)稱性在圖查詢中應(yīng)用研究 124
參考文獻(xiàn) 125
彩圖