图论简介

目录

本文非常简单的介绍一下与图有关的知识。在以后做贝叶斯网络，置信网络和马尔科夫网络分析的时候这些基本的概念将会被赋予具体的意义。图在机器学习里最重要的应用可能就是其矩阵表示。另外赋予了特殊意义的图在解决问题的时候抽象问题图形化，也方便分析问题，编写代码实现解决方案。对我而言，目前基于消息传递算法的LDPC译码，基于BCJR的Turbo码译码都用到了图这个强有力的工具。

1 图

图由节点和边构成。图的边可以是有向的也可以是无向的。有向的图叫做有向图，反之无向图。为图的边赋值一个权重可以用来建模网络流量或者城市之间的距离。在概率模型中我们赋予图一种概率的解释。无向图在推断和建模中发挥着重要的作用，比如构建马尔科夫网络或者其他概率模型。

一条从 A↦B的路径是从A到B的一系列连接A和B的节点。也就是说一条路径可以是A0,A1,…,An，其中A0=A,An=B，其中每两个相邻的节点之间有一条边Ak,Ak+1相连。一个有向路径是指存在A↦B而不存在B↦A的路径。在A↦B中B叫做A的后裔。

20170315fig2dot2.png

Figure 1: 有向图和无向图

一个有向环是指从一个节点出发经过若干条有向路径后又回到该点的路径，比如a↦b↦…↦z↦a. 一个无向环则是不考虑方向的环。例如图1 中图b的1−2−4−3−1只能构成一个无向环，但不能构成有向环。弦是一个无向环中链接两个不相邻点的边，比如图1 图a的2−3构成了1−2−4−3−2−1的一条弦。

有向无环图(Directed Acyclic Graph,DAG) 是一个由有向边构成的图，但是没有环。在DAG中，节点B的祖先是所有能够连接到该节点的点。

20170315DAG.png

Figure 2: 有向无环图

在图2 中， x4的父节点是pa(x4)={x1,x2,x3}，x4的子节点ch(x4)={x5,x6}，一个点的family包含这个点本身和它的parents。一个点的Markov blanket包含它的parents，children以及children的parents，比如x4的Markov blanket是x1,x2,x3,x5,x6,x7

DAG在有大量随机变量建模的场景中广泛使用，特别是置信网络(belief networks).

给定一个无向图，一个clique是一个全连接的节点子集，即一个clique中的所有节点都是邻居。

20170315clique.png

Figure 3: clique

比如图3中有两个最大clique C1={A,B,C,D},C2={B,C,E} 尽管A,B,C是全连接的但是这个集合不是最大clique,因为有更大的clique包含它。不是最大的clique又叫做cliquo

在推断模型中，一个clique表示相互依赖的随机变量。在推断过程中一个clique中的变量结构无法更进一步的简化。

2 用矩阵表示图

机器学习的实质是实现概率推断，在这个过程中概率图模型是一个有力的工具。我们要对图进行数学表示，一种方便的表示方法是矩阵。矩阵是一种方便计算机操作的数学模型。比如图1a中的矩阵就可以表示为：

A=[0110101111010110]

其中Aij=1表示第i个节点和第j个节点直接有一条边。0表示第i个节点和第j个节点之间没有边。一个有向图1b的矩阵表示为：

T=[0110001100010000]

我们发现一个无向图的矩阵是对称的，一个有向图的矩阵是三角阵。

矩阵A看起来比较浪费，因为有很多0存在，但是这个矩阵却有一个重要的性质。那就是对于N×N的矩阵 A的幂次[Ak]ij表示从i 跳k步到j的路径一共有多少条。如果我们在A的对角线上放1则如果有从i到j的路径时[AN−1]ij是非零的。如果A是DAG，则[AN−1]的第j行表示节点j的孩子。