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