图对称性理论及其在数据管理中的应用

本书系统地介绍了图对称性基础理论，包括基于图对称的复杂性度量模型与图距离度量模型、复杂对称网络生成模型以及基于图对称的网络约简理论等，介绍了一系列基于图对称性的应用方法，包括利用图对称实现社交网络隐私保护、利用图对称实现高效的最短路径索引与查询等。

序
前言
第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
彩图