Basic Knowledge to Graph

呀，自己看会计的文献看着看着突然对于图结构又感兴趣了，果然自己对会计不是真爱啊，所以又回到了这儿写关于图模型的一些事情。PGM那些文章之中对于图的结构的介绍似乎也并不多，知识一些简单的所必须的知识，似乎在那儿的图的本身的结构并非是那么强调的重点内容，而关注点在于概率是如何传播的过程，但是在这里我们对于整个图的结构要更加重视一些，所以需要对于图的结构有更加明确的了解。本节属于基础知识模块，大家可以略过的看。

Directed and Undirected Graph

有向图和无向图，这个在PGM之中也有涉及，Bayes网络就是一个有向图，而Markov Network就是一个无向图，但是我们在这里需要对于一些性质进行更加深入的了解。比如说度(Degree)这个概念

简单的说，也就是与该节点所连接的边的数量

嘿想不到两边的图可以混用，上面就是每一个节点的度都是2，因为其中的每一个节点仅仅是与两个节点相连接。那么这是无向图，有向图也是使用度这个概念，不过这里的度会分得更加细致一些，为出度(Out – Degree)以及入度(In – Degree).

这个图之中的Grade的出度就是1，而入度就是2，这个也非常的好理解吧。而出度为0的我们称之为是Sink，有点像决策树之中的叶子节点。而入度为0的我们称之为是Source，有点像决策树之中的Root节点。

Bipartite Graph

还有一种图叫做二分图，这个图的结构非常的好玩，其图的结构可以分成是两边，一边是$U$一边是$V$，其中$U$和$V$之内相互独立，而他们之间产生关系。有的Markov Network就可以看成是一种二分图

在我们之前写的那篇论文之中也使用到了二分图这样的一个概念，左边是Relationship而右边是Entity。对于二分图我们可以将其”Fold”，也就是为在原图之中不存在关系的节点之间创造关系。具体创造关系的方法也很简单，就是对于两个节点如果都连接到同一个节点，我们就认为他们存在关系，这个还是非常的直观的手段。

Adjacent Matrix

连接矩阵在自然语言处理之中好像也是一个被广泛的运用的方法吧，如果两个节点之间有连接的话，那么在一个$n\times n$的矩阵之中，在对应的位置上就设置为1，而如果不存在连接就设置为0.对应Direct Graph也是如此

而如果有了邻接矩阵的话，图的度也就顺水推舟的出来了，对于无向图的度，直接对于节点对应的行或者是列求和就行了。而对于有向图，其出度是对于列求和，而入度是对于行求和。

$$K_{i}^{out} = \sum_{j=1}^{N}A_{ij}$$

$$K_{j}^{in} = \sum_{i=1}^{N}A_{ij}$$

Other

当然在这里也会有其他的奇奇怪怪的知识，大家可以看看然后体验一下奇怪的知识增加了的感觉

Weight Graph

也就是在边上进行加权了，对于某两个特定的节点之间如果有什么特殊的权重比如说距离之类的特征，就可以在矩阵之中对于这个特定的元素进行修改。记得在计算最短距离的时候就也用过这个加权的矩阵。

Self Edge

也就是自己和自己有联系，形成了一个Self Loop，具体的应用自己暂时一下想不起来了。

MultiGraph

也就是允许两个边之间产生多种不同的联系，这样的关系应该在现实生活之中也是很常见了，但是在这里的Course Note上对于这种情况就是再加了一，其实感觉这样有点不严谨吧，毕竟这多种不同的关系是不是可以使用同样的计量标准都是一个值得思索的问题。

 

How to Measure A network

如何对于网络进行表达呢？毕竟一个网络动辄几十万个点，我们需要一个有效的标准对于整个网络进行评价。这里给出四个最重要的标准，分别是

1. Degree Distribution :$P(k)$
2. Path Length : $h$
3. Clustering Coefficient : $C$
4. Connected Components :$s$

Degree Distribution

所谓的Degree Distribution也就是整个网络之中的每一个节点会连接的其他的点的分布的情况，如果分布所呈现的情况是所有的点的Degree都非常的高，那么整个网络就更加的紧凑，而如果Degree都不高，整个网络就更加的稀疏。

如果对于MSN上面的用户看成一个点，而其交流的对象的个数是Degree，可以发现图像所呈现出的情况就是这样的，但是如果取对数的话，可以发现就漂亮了许多

而通过这样的方法，我们可以发现绝大多数的用户的Degree都集中在了右下角的那一个部分之中，而对于那些连接节点多的用户往往是少数的，并由此可以看出大概的分布的情况。其实这里也可以人为的设置阈值，将上面的那张图分成不同的Part，不过下面的还会更加直观吧。

Path in a Graph

Path也就是一系列的相互连接的节点，比如说从节点$A$到节点$G$

其Path就是ACDEG,当然在这个Path之中并不限定是最短路径甚至可以是含有Loop的，比如说ACDBCDEG,打了个圈也没有关系。

而事实上我们往往只是想要最短路径而已，也就是两个节点之间所通过的其他的中介节点越短越好。当然这种情况是假设所有的节点的成本都是相同的，而事实上，现实中的问题往往是不同的，所以我们就引入了Weight Graph来解决这个问题，那么这时候的最短路径就是使得Sum最小。

而网络之中的最大的最短路径称之为网络的Diameter，自己的理解是类似于极差之类的概念。

而还有一个概念就是Average Path Length，也就是在网络之中的两个点之间的平均的最短的距离。

在MSN网络之中，每两个随机的人之间的平均的距离是6.6，百分之九十的人之间可以通过8个人就被Reach到，这也就是经典的六度分隔理论的一个现实证明吧。

Clustering Coefficient

这个概念不是对于Node $i$而言的，而是对于Node的邻居而言的，什么意思呢？这个是一个度量节点的周围的Neighbors的连接的紧密程度的一个指标，先给出公式

$$C_{i} = \frac{2e_{i}}{k_{i}k_{i}-1}$$

那么$k_{i}$大家都知道是节点的Degree，那么$e_{i}$是什么呢？有点绕，就是节点$i$的邻居的相连接的边的数量。

上图之中第一个的邻居节点全都连接在一起了，所以他的Clustering Coefficient是1，其他的大家自己类推一下。

而平均的Clustering Coefficient就是在整个网络之中的平均的CC

$$C = \frac{1}{N}\sum_{i}^{N}C_{i}$$

Connectivity

原文的定义就是Size of the largest connected component,怎么说呢？网络之中不一定任意的两个点之间都可以通过有限次步数达到，如果达到不了的话，那么就可以知道整个图并非是连接的而是在中间出现了断点。

而我们如何寻找到最大的连接的Component呢？有一个算法叫做是BFS算法就是执行这样的功能的，不过我们在这就不赘述了，以后有空补坑

好了之后就是正式的进入图机器学习的领域之中了。