圖對稱性理論及其在數(shù)據管理中的應用

目錄
序
前言
第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 作為圖數(shù)據管理重要問題之一的對稱性 10
1.3.3 作為一種技術手段的圖對稱 13
第2章 網絡對稱性 14
2.1 圖論基礎 14
2.1.1 圖的基本概念 14
2.1.2 圖之間的關系 18
2.2 代數(shù)基礎 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 真實網絡數(shù)據集介紹 37
3.2.2 對稱二分子團 37
3.2.3 精確相似鏈接模式 39
3.2.4 非精確相似鏈接模式 43
3.3 對稱網絡生成模型 45
3.3.1 基于相似鏈接模式的擇優(yōu)鏈接 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 基于自映射分區(qū)的結構熵 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 網絡商的規(guī)模 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 模擬數(shù)據集上的實驗結果 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 圖穩(wěn)定化過程研究 123
7.3.4 對稱性在圖查詢中應用研究 124
參考文獻 125
彩圖