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

作者简介

内容简介

第1章 绪论
　　现实世界中的很多复杂系统都可以描述为实体及实体之间的关系，这样一种认识世界的方式使图或网络成为广泛应用的一种数据建模方法。图或网络的普适性使利用网络来研究现实系统的功能与性质成为可能。基于这一事实，一个新兴交叉研究领域在过去十年取得了飞速发展：复杂网络。与传统图论侧重于理想图的性质不同，复杂网络以真实世界网络的统计特性和动力学特征为主要研究对象。然而一直以来，网络的一个重要特性——对称性被忽视了。网络对称性不仅提供了新的考察复杂网络的视角，也提供了相应的方法论（置换群论）支持，从这一新的角度考察真实网络将为人们展示真实网络系统新的景象。
　　图或网络的普适性也使图数据管理成为近年来数据管理领域最为热门的研究主题之一。虽然在图数据管理领域，已有大量工作致力于解决各类图数据管理问题。但是，现有工作多是将面向关系或树结构（如可扩展标记语言（extensible markup language，XML））的数据库技术向图数据管理问题的简单移植。而事实上，当尝试把这些方法移植到面向图数据的真实应用中时，我们发现图数据管理的基本问题——图对称问题被刻意回避了。
　　本书将针对真实网络对称性的若干具体理论问题以及应用问题展开研究。
　　1.1 概述
　　图或网络被广泛应用于描述现实世界中实体及实体之间的关系，这样一种认识世界的方式使图或网络成为广泛应用的一种数据建模方法。图或网络的普适性使利用网络来研究现实系统的功能与性质成为近年来的研究热点，也使图数据管理成为近年来数据管理领域最为热门的研究主题之一。虽然真实网络性质的研究以及图数据管理领域的研究已经取得很大进展，但是图数据的一个重要性质——图对称，一直没有得到充分研究。本书以图对称理论及其在数据管理问题中的应用为研究内容。
　　本节以社会网络分析与计算为例，介绍本书的主要研究思路和主要的研究内容。
　　一个社会网络通常表达的是实体（人或组织）以及实体之间的社会关系。给定一个社会网络，给定网络中的两个实体，查询它们之间的最短路径是进行社会网络分析的一项基本的查询问题。为了实时回答面向较大社会网络的最短路径查询，可以物化以每个顶点为根的宽度优先搜索（breadth-first search，BFS）树，树中的每一条从根出发的路径都表达了图中相应的最短路径[1]。然而，直接实现这一物化方法需要消耗O（N2）的存储空间。
　　为了方便描述，本节以如图1.1所示的一个简单的社会网络为例。通过对图1.1 的观察，我们发现顶点v1和顶点v2具有如下性质：对于任意顶点v∈（V（G）-{v1，v2}），v1到v的最短路径和v2到v的最短路径几乎完全相同，除了边（v1，v3）和边（v2，v3）不同。事实上，在后面我们会介绍v1和v 2之间的这种等价性的实质是自映射等价。当顶点自映射等价时，它们的很多结构特征是相同的。这个例子说明的是它们的BFS 树的等价性。事实上，在后面的章节中我们会说明在图1.1中，自映射等价关系还存在于v5，v6之间以及v7，v8，v9，v10之间。它们的BFS 树之间也存在着类似的等价性。
　　直观地来讲，在一个图中如果能找到自映射等价关系，那么这个图就是对称的；并且如果找到的自映射等价关系越多，图越对称。那么能否利用图对称性，具体来说自映射等价的顶点在BFS 树上的等价性，降低最短路径查询所需的BFS 树索引空间消耗，这成为本书第6章的主要研究内容。
　　在社会网络中，结构等价的顶点通常扮演着相同的社会角色，因而这些等价的顶点之间通常是可以互相替换的，因此结构等价性可以理解为一种结构上的冗余。那么一个很自然的想法就是，我们能够从原网络中约简掉这些冗余信息而不损失网络必要的结构信息。寻找这样一种能够保持原网络重要性质的骨架在很多问题中有着实际需求。社会网络隐私保护的可用性问题就是其中之一。本书第5章将对基于对称的网络约简及其在社会网络隐私保护中的应用展开研究。
　　当我们发布一个社会网络时，通常需要对网络中的顶点进行匿名化处理。然而，攻击者仍然可以根据顶点的结构特征识别出那些结构特征独特的个人（这种攻击称作结构再识别（structural re-identification）[2]）。例如，如果知道Bob 的邻居数目为5，那么在图1.1 中，v3 必定就是Bob，因为图中仅有v3 拥有5个邻居。因此，发布社会网络数据时，人们自然地想知道，在结构再识别这种攻击下，网络实体隐私泄露的风险有多大。显然，网络实体隐私泄露的风险与网络的结构异构性有着直接关系。因此，网络隐私泄露风险的度量就可以转换为网络结构异构性度量问题。现有的基于顶点度的网络异构性度量不能很好地刻画网络隐私泄露风险。例如，在图1.1 中顶点v1 和v7 的度都为1，但是它们的邻居的度不一样，攻击者仍然可以利用这一信息进行攻击。而利用自映射等价关系可以很自然地将网络顶点划分为结构特征不同的等价类，因而成为度量网络的结构异构性的理想方法。这构成了本书第4章的研究内容之一。
　　图1.1 一个简单的社会网络
　　在对社会网络中的顶点进行角色分析时，通常需要评价两个顶点在网络中是否扮演着相同或者相似的角色，其中角色相似性判定的一个重要的依据是顶点的邻居图（neighbor graph）[3]（由某个顶点的邻居集导出的子图）在结构上的相近程度。这其中的关键问题是如何度量两个顶点邻居图的相似程度或者它们之间的距离。相同规模的图，由于对称性的不同，其子结构的模式也就是不同构的子结构数量也不相同。通过对比图中蕴含的子结构模式来计算图的相似程度，不仅可以提高图距离度量精度，同时在生物网络分析中能够较好地体现生物学含义（如某个子结构模式通常可以理解为某种生物功能模块）。基于这些事实，本书第4章提出了一个子结构信息的图距离度量。
　　本书研究的另一个基本问题是对称网络生成模型，这是研究网络对称的首要问题。给定一个对称的社会网络，如何生成一个对称性接近真实社会网络的模拟网络，是将网络对称性理论进一步应用的基础问题。而为了生成对称网络，必须探索真实网络的对称产生机制，并提出相应的网络生成算法。这些研究构成了本书第3章的研究内容。
　　在深入介绍这些内容之前，必须在数学层面理解网络对称性的精确含义，了解网络对称性的基本性质。这构成了本书第2章的主要内容。
　　需要指出的是，上述网络对称性相关问题的研究不局限于社会网络，在一般网络上也存在着同样的问题。虽然上述很多问题是从社会网络分析的角度引入的，但事实上，这些问题有其独立的研究价值。例如，图距离度量就是一个在多个学科如模式识别、图数据管理、化学信息学中都有着重要研究价值的基础问题。
　　概括来讲，本书的研究内容为：以真实网络数据，如生物网络、社会网络数据为研究对象；从网络结构对称性角度研究网络的基本性质，提出对称网络生成模型；并将网络对称性理论应用于具体问题，包括网络度量（网络异构性度量和图距离度量）、网络结构约简以及降低最短路径索引空间等。本书的研究框架如图1.2所示。
　　本书的主要贡献可以概括如下。
　　（1） 系统地综述了（图）对称性研究的理论及实践意义；结合图数据管理问题，对于图论领域、代数领域的重要理论结果进行了系统的评述。
　　（2） 首次针对存在于真实网络中的对称性，阐述了网络对称性的产生机制，并提出了相应的对称网络生成模型。该模型可以广泛用于改善现有的真实网络模拟以及基于此的一系列实际应用问题。
　　图1.2 研究框架
　　（3） 首次提出了结构异构性概念，并基于网络对称性，提出了能够较为合理地度量网络异构性的新的结构熵度量。这一新的度量，可以应用于刻画社会网络隐私泄露风险，刻画网络复杂性等一系列问题。基于子结构丰富性，提出了泛化的基于结构的图距离度量，提高了图距离度量的精度。
　　（4） 首次提出了通过约简对称性所刻画的网络结构冗余提取网络骨架的方法；通过实证证实，所得到的网络骨架在规模上显著小于原网络，且能够保持原网络的通信性质以及复杂性等重要性质。将网络商应用于社会网络隐私保护问题，提出了网络商的一个改进版本——B-骨架，并成功利用B-骨架保持了k-对称匿名模型的可用性。网络商的研究还可以广泛应用于图数据管理各类问题，如网络的精简存储与表达等，也可以应用于各类物理系统、生物系统结构的优化设计等。
　　（5） 首次将网络对称性理论应用到图数据管理问题。发展了局部对称理论、轨道邻接性理论，探索了子结构在自映射作用下的性质。针对最短路径索引开销较大问题，基于网络对称性理论，提出了基于压缩BFS 树的索引结构，大量实验和理论分析说明基于对称的方法在实现实时最短路径查询的同时，有效地压缩了最短路径索引所需要的空间开销。此项成果为图对称技术在其他图数据管理问题中的应用奠定了基础，具有示范意义。
　　本章剩余内容的安排如下。图结构对称是对称性的一种，1.2节将详细阐述对称性基本内涵、对称变换以及对称性基本原则。1.3节将主要从复杂网络研究和图数据管理研究两个角度阐述图对称研究的背景，论述网络对称性研究的价值。
　　1.2 一般对称性
　　1.2.1 对称性基本内涵
　　对称（symmetry）这个词源自希腊语sun（相同的）和metron（尺寸），最初用来表示相同的尺寸。德国数学家Weyl[4]曾对对称性作了如下定义：如果一个操作能使某系统从一个状态变换到另一个与之等价的状态，即系统的状态在此操作下保持不变，则该系统对这一操作对称，这一操作称为该系统的一个对称操作。简而言之：对称刻画了系统在一组变换下的不变性。现实生活中普遍存在着对称性，如人和一些动物的形体，建筑物的结构，各种花瓶、花边等是对称的典型例子。对称性自从被提出，就成为很多自然学科包括生物学、物理学、化学等的重要研究内容。
　　近年来，对称性的研究日益成为自然科学领域的研究热点。在自然科学哲学领域，先后出版了好几部专著讨论广泛存在于生活以及自然学科中的对称性现象以及基本原则。其中，德国哲学家Mainzer 于2005年出版了Symmetry and Complexity：The Spirit and Beauty of Nonlinear Science[5]一书，系统综述了存在于文化、经济、社会、物理、化学、数学以及信息科学领域中的对称性现象。2007年，Springer-Verlag 出版的自然科学前沿系列丛书，其中有两本都是关于对称的，包括Muller 编著的Asymmetry: The Foundation of Information[6]和Rosen 编著的Symmetry Rules: How Science and Nature are Foundedon Symmetry[7]。Muller 的书从对称角度向人们揭示了信息的本质是非对称。Rosen 的书详细阐述了自然科学与对称之间的紧密关系，向人们展示了自然科学是如何建立在对称基础之上的。无独有偶，2008年诺贝尔物理学奖，授予了发现亚原子物理学中自发对称性破缺机制的南部阳一郎和发现有关对称性破缺的起源的小林诚、益川敏英。此外，2003年来自全世界的一些知名科学家包括数学家、物理学家、化学家、生物学家以及人文社会科学领域的专家共同发起成立了国际对称协会（International Symmetry Association），并发行了专刊Symmetry，每年组织召开学术年会（称为Symmetry Festival），旨在推动在自然科学、工程、人文、社会等领域的对称性研究。
　　对称性受到如此广泛的重视不是偶然的。对称性研究的重要意义可以归纳为以下几点。
　　（1） 对称性是普遍存在的现象。对称性是复杂系统包括生物系统、社会系统、经济系统、技术系统中普遍存在的现象[4，5，8，9]。对称现象在日常生活中也是随处可见的。
　　（2） 事物的演化