最近《复杂网络建模》这门课要考试了,正好也在跟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] 《图论概念梳理》