最近《复杂网络建模》这门课要考试了,正好也在跟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\)。
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101134059_%E6%97%A0%E5%90%91%E5%9B%BE%E5%BA%A6.png)
无向图的平均度定义为:
\[\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\),有向图的平均度定义为:
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101134050_%E6%9C%89%E5%90%91%E5%9B%BE%E5%BA%A6.png)
在有向图中,我们有总入度等于总出度之和,即\(\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)。
常见的二分图包括:作者和其撰写的论文构成的网络、演员和其出演的电影构成的网络、用户和其打分的电影构成的网络。
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101154403_%E4%BA%8C%E5%88%86%E5%9B%BE.png)
对于上面这个二分图,我们还可以画出其对应的“折叠”(folded)网络如下:
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101154423_%E4%BA%8C%E5%88%86%E5%9B%BE%E6%8A%98%E5%8F%A0.png)
“折叠”网络可以用来表示作者之间的合作关系和电影合作网络。
2.4 图的表示
邻接矩阵(adjacency matrix)
我们可以用邻接矩阵\(A\)来表示图,其中当节点\(i\)和\(j\)之间存在链接时\(A_{ij}=1\),否则\(A_{ij}=0\)。注意有向图的邻接矩阵不是对称的。如对于下列的两个图
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101154942_%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E7%A4%BA%E6%84%8F%E5%9B%BE.png)
其邻接矩阵分别为
\[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)
我们也可以用边组成的集合来表示图,如图
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101155147_edge_list.png)
就可以表示为
\[[(2, 3), (2, 4), (3, 2), (3, 4), (4, 5), (5, 2), (5, 1)] \]邻接表(adjacency list)
邻接表一般用于网络大而稀疏的情况,它可以让我们快速地检索到给定节点的邻居。上面这张图的邻接表表示为:
现实世界中的网络常常是稀疏的,即\(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)
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101160856_无权图.png)
上面这个无权图的邻接矩阵为:
\[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)
带权图就是指图中的每一条边都有对应的一个数值权重。
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101160914_带权图.png)
上面这个带权图的邻接矩阵为:
\[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\)被称为一个自环。
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101161003_自环图.png)
上面这个带自环图的邻接矩阵为:
\[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\)不为重边。
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101161022_多重图.png)
上面这个多重图的邻接矩阵为:
\[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. 图的连通性
无向图的连通性
对于无向图,若任意两个顶点都能够通过一条路径连接,则我们称其为连通的。
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101161554_连通图.png)
一个不连通的图由两个或多个连通的分量(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路径,我们就称它是强连通的;如果只有在我们忽视了边的方向的条件下才是连通的,则称它为弱连通的。
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221101161628_强连通和弱连通.png)
上面这个有向图是连通的,但不是强连通的(比如不存在按照边的方向从\(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] 《图论概念梳理》