第4章 图论

4.1 概述

开放知识网络由不同类型的点和边组成，其结构可以抽象成一张图，因此，在对开放知识网络的计算及对其结构特征的探究和利用中，往往会用到图论的基础理论。例如，在开放知识网络的计算中被广泛研究的关系推断技术，旨在根据现有的网络，实现对隐含关系的推测，其中，由已知关系组成的关系路径往往预示着隐含关系，因此是推断隐含关系的重要特征，比如，巴拉克·奥巴马米歇尔·奥巴马萨沙·奥巴马，可以推断出巴拉克·奥巴马萨沙·奥巴马，可以看出，已知关系路径，对关系的推断有帮助作用。而对关系路径的建模、对关系路径的随机游走等，图论都是其重要的理论研究基础。

因此，本章对图论的基础理论进行了简单的介绍，首先介绍了图的基础概念，阐述了图的常见基本结构，这些结构在不同的知识网络中都有体现，例如有些关系是无向的，有些关系是有向的，因此对开放知识网络的建模是以图的概念为基础的；并对更为特殊的结构“树”进行了详细介绍，开放知识网络中常见的层次结构，就是以树为基础定义的；接着介绍了路径、连通性等图在开放知识网络中常用的结构特征；然后介绍了图的表示，即如何将图数字化；最后，介绍了图的遍历算法，其在开放知识网络的研究过程中，如关系路径的随机游走算法等都有重要应用。