图数据挖掘(一)：网络的基本概念和表示方法

网络(network)是一些通过链接(links)连接起来的对象集合，它包含以下成分：对象：节点(nodes)/顶点(vertices)， 用N表示；交互：链接(links)/边(edges)，用E表示；对象和交互组成的系统我们就称为网络(或图，graph)，用G(N,E)表示。

最近《复杂网络建模》这门课要考试了，正好也在跟Stanford的《CS224W：Machine Learning With Graphs》这门课，这里就一边整理笔记一边复习了。

1. 网络的定义

网络(network)是一些通过链接(links)连接起来的对象集合，它包含以下成分：

• 对象：节点(nodes)/顶点(vertices)， 用\(N\)表示；
• 交互：链接(links)/边(edges)，用\(E\)表示；

对象和交互组成的系统我们就称为网络(或图，graph)，用\(G(N,E)\)表示。

一般而言，我们用术语网络来称呼一个真实的系统，如Web、社交网络、代谢网络等，此时伴随着术语节点和链接进行使用；而相对应地，我们用术语图来称呼一个网络的数学表示，如web图、社交图等，此时伴随着术语顶点和边来使用。当然，大多数情况下我们会互换使用这两个术语。

2. 常见网络类型及表示

2.1 有向图和无向图

无向图
无向图的链接是无方向(undirected)的，也对称(symmetrical)、互反的(reciprocal), 常见的例子包括合作网络、Facebook上的朋友关系等。

有向图
有向图的链接是有方向(directed)的，此时的有向边也称为弧(arcs)，常见的例子包括打电话网络、Twitter上的关注网络等。

2.2 节点的度

对于无向图而言，节点\(i\)的度(degree)\(k_i\)是指和节点\(i\)相邻的边数。如下图所示\(k_A=4\)。

无向图的平均度定义为：

\[\bar{k}=\langle k\rangle=\frac{1}{N} \sum_{i=1}^N k_i=\frac{2 E}{N}
\]

（这里用到握手定理：无向图中节点的度之和等于边数的两倍）
而对于有向图而言，我们定义节点的出度为“离开”该节点的边数，入度为“进入”该顶点的边数。有向图中节点的度定义为其初度和入度的和。如对下面这个图我们有：\(k_C^{\text {in }}=2,k_C^{\text {out }}=1, k_C=3\)，有向图的平均度定义为：

\[\bar{k}=\frac{E}{N}
\]

在有向图中，我们有总入度等于总出度之和，即\(\overline{k^{\text {in }}}=\overline{k^{\text {out }}}\)。此外，我们将入度\(k^{in}=0\)的节点称为源节点(source)，将出度\(k^{out}=0\)的节点称为汇点(slink)。

2.2 完全图

一个有\(N\)个节点的无向图所拥有的最大边数为：

\[E_{\max }=\left(\begin{array}{c}
N \\
2
\end{array}\right)=\frac{N(N-1)}{2}
\]

边数\(E=E_{max}\)的无向图称为完全图(complete graph)，其平均度为\(N-1\)。下图展示了一个完全图：

2.3 二分图

二分图的节点可以被分为两个不相交的子集\(U\)和\(V\)，使得每条边都连接着\(U\)中的一个顶点和\(V\)中的一个顶点。也就是说，\(U\)和\(V\)是独立集(independent sets)。

常见的二分图包括：作者和其撰写的论文构成的网络、演员和其出演的电影构成的网络、用户和其打分的电影构成的网络。

对于上面这个二分图，我们还可以画出其对应的“折叠”（folded）网络如下：

“折叠”网络可以用来表示作者之间的合作关系和电影合作网络。

2.4 图的表示

邻接矩阵(adjacency matrix)

我们可以用邻接矩阵\(A\)来表示图，其中当节点\(i\)和\(j\)之间存在链接时\(A_{ij}=1\)，否则\(A_{ij}=0\)。注意有向图的邻接矩阵不是对称的。如对于下列的两个图

其邻接矩阵分别为

\[A=\left(\begin{array}{llll}
0 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 \\
1 & 1 & 1 & 0
\end{array}\right), \quad A=\left(\begin{array}{llll}
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0
\end{array}\right)
\]

边表(edge list)
我们也可以用边组成的集合来表示图，如图

就可以表示为

\[[(2, 3), (2, 4), (3, 2), (3, 4), (4, 5), (5, 2), (5, 1)]
\]

邻接表(adjacency list)
邻接表一般用于网络大而稀疏的情况，它可以让我们快速地检索到给定节点的邻居。上面这张图的邻接表表示为：

\[\begin{aligned}
& □\space 1: \\
&□\space 2: 3,4 \\
&□\space 3: 2,4 \\
&□\space 4: 5 \\
&□\space 5: 1,2
\end{aligned}
\]

现实世界中的网络常常是稀疏的，即\(E\ll E_{max}\)(或\(\bar{k}\ll N - 1\))，比如下面就列出了几种现实世界网络的属性：

网络名称	节点数\(N\)	平均度\(\bar{k}\)
WWW(Stanford-Berkeley)	319,717	9.65
Social networks(LinkedIn):	6,946,668	8.87
Communication(MSN IM):	242,720,596	11.1
Coauthorships (DBLP):	317,080	6.62
Internet (AS-Skitter):	1,719,037	14.91
Roads (California):	1,957,027	2.82
Proteins(S. Cerevisiae):	1,870	2.39

这样用邻接矩阵进行存储的话就会有大量的0导致存储空间浪费（邻居矩阵密度(\(E/N^2\))：\(\text{WWW}=1.51\times 10^{-5}\), \(\text{MSN IM}=2.27\times 10^{-8}\)）。此时邻接表就有了用武之地。

关于边属性(edge attributes)
图的边可能还自带有属性，包括：

• 权重： 如通信频率
• 排名： 如最好的朋友、第二好的朋友
• 类型： 如朋友、亲属、同事
• 符号： 如朋友vs陌生人、信任vs不信任
• 一些依赖于图其余部分结构的属性：如共同朋友的数量

2.5 更多图的类型

无权图(unweighted graph)

上面这个无权图的邻接矩阵为：

\[A_{i j}=\left(\begin{array}{cccc}
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
0 & 1 & 0 & 0
\end{array}\right)
\]

这里\(A_{ii} = 0\)，\(A_{ij}=A_{ji}\)。

其边数\(E=\frac{1}{2} \sum_{i, j=1}^N A_{i j}\)，平均度\(\bar{k}=\frac{2 E}{N}\)。

常见的无权图例子包括朋友网络，超链接网络。

带权图(weighted graph)

带权图就是指图中的每一条边都有对应的一个数值权重。

上面这个带权图的邻接矩阵为：

\[A_{i j}=\left(\begin{array}{cccc}
0 & 2 & 0.5 & 0 \\
2 & 0 & 1 & 4 \\
0.5 & 1 & 0 & 0 \\
0 & 4 & 0 & 0
\end{array}\right)
\]

这里\(A_{ii}=0\)，\(A_{ij}=A_{ji}\)。
其边数\(E=\frac{1}{2} \sum_{i, j=1}^N \operatorname{nonzero}\left(A_{i j}\right)\)，平均度\(\bar{k}=\frac{2 E}{N}\)。

常见的带权图例子包括合作网络、英特网、公路网络。

带自环(self-loops/self-edges)的图

对\(E\)中的边\(e=(u, v)\)，若\(u=v\)，则\(e\)被称为一个自环。

上面这个带自环图的邻接矩阵为：

\[A_{i j}=\left(\begin{array}{cccc}
1 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1
\end{array}\right)
\]

这里\(A_{ii}\neq 0\)，\(A_{ij}=A_{ji}\)。

其边数\(E=\frac{1}{2} \sum_{i, j=1, i \neq j}^N A_{i j}+\sum_{i=1}^N A_{i i}\)。

常见的带自环的图包括蛋白质网络，超链接网络等。

多重图(multigraph)
多重图是一个允许有重边（也称多重边，平行边）的图，重边即两个顶点之间可能存在多条边。在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为重边；在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(也就是他们的方向相同)，称这些边为重边。这也就是说在无向图中\((u, v)\)和\((v, u)\)算一组重边，而在有向图中，\(u\rightarrow v\)和\(v\rightarrow u\)不为重边。

上面这个多重图的邻接矩阵为：

\[A_{i j}=\left(\begin{array}{llll}
0 & \underline{2} & 1 & 0 \\
\underline{2} & 0 & 1 & \underline{3} \\
1 & 1 & 0 & 0 \\
0 & \underline{3} & 0 & 0
\end{array}\right)
\]

这里\(A_{ii}=0\)，\(A_{ij}=A_{ji}\)。

其边数\(E=\frac{1}{2} \sum_{i, j=1}^N \text { nonzero }\left(A_{i j}\right)\)，平均度\(\bar{k}=\frac{2 E}{N}\)。

常见的多重图例子包括通信网络，合作网络等。

3. 图的连通性

无向图的连通性
对于无向图，若任意两个顶点都能够通过一条路径连接，则我们称其为连通的。

一个不连通的图由两个或多个连通的分量（connected components）组成（也称为连通块）。其中巨大的连通分量我们将其称为gaint component，如下图所示就有3个连通分量：

图中的节点\(H\)的度\(d(H)=0\)，我们将其称为孤立点(isolated node)。

我们有以下定义

• 桥边(bridge edge)/割边(cut edge)：如果将该边去除，则图变得不连通。可以发现，一条边\(e\)是桥边当且仅当\(G /\{e\}\)的连通分量个数大于\(G\)的连通分量个数。
• 关节点(Articulation node)/割点(cut vertex)：如果将该点去除，则图变得不连通。一个点\(v\)是割点当且仅当\(G /\{v\}\)的连通分量个数大于\(G\)的连通分量个数。

有向图的连通性
对于有向图，若图中每个节点都有一条到其它节点的路径（反之亦然），如A-B路径和B-A路径，我们就称它是强连通的；如果只有在我们忽视了边的方向的条件下才是连通的，则称它为弱连通的。

上面这个有向图是连通的，但不是强连通的（比如不存在按照边的方向从\(F\)到\(G\)的路径）。

4. 现实世界中的常见网络类型

• Email网络： 有自环的有向多重图
• Facebook朋友关系网络：无向、无权图
• 引用网络：有向、无权、无环（acyclic）的图（无环是因为较早发表的文章不能引用较晚发表的文章）
• 合作网络：无向（带权？）多重图
• 打电话网络：有向（带权？）多重图
• 蛋白质相互作用网络：无向、无权、有自环的图（蛋白质可以自我相互作用）

参考

[1] http://web.stanford.edu/class/cs224w/
[2] Easley D, Kleinberg J. Networks, crowds, and markets: Reasoning about a highly connected world[M]. Cambridge university press, 2010.
[3] Barabási A L. Network science[J]. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013, 371(1987): 20120375.
[4] 《图论概念梳理》