巴拉巴西《网络科学》第二章

Albert-László Barabási, Network Science, Chapter 2

第二章介绍图论，明确一些基本概念和方法，如度专题（度、平均度和度分布）、路径专题（最短路径、直径等）、邻接矩阵（很重要）和网络属性（连通性、集聚系数等）。

2.1. 哥尼斯堡七桥问题（The Bridges of Königsberg）

不多说了，很熟悉了，配一张卫星地图，历史上的七桥问题所在的哥尼斯堡现在为俄罗斯加里宁格勒，不是德国的那个。

2.2. 网络和图（Networks and Graphs）

也比较熟悉了，二者有概念称呼上的不同：

Network Science	Graph Theory	GIS
Network	Graph	Polygon
Node	Vertex	Point
Link	Edge	Edge

常见的网络：

Network	Nodes	Links	Directed / Undirected	N	L	‹K›
Internet	Routers	Internet connections	Undirected	192,244	609,066	6.34
WWW	Webpages	Links	Directed	325,729	1,497,134	4.60
Power Grid	Power plants, transformers	Cables	Undirected	4,941	6,594	2.67
Mobile-Phone Calls	Subscribers	Calls	Directed	36,595	91,826	2.51
Email	Email addresses	Emails	Directed	57,194	103,731	1.81
Science Collaboration	Scientists	Co-authorships	Undirected	23,133	93,437	8.08
Actor Network	Actors	Co-acting	Undirected	702,388	29,397,908	83.71
Citation Network	Papers	Citations	Directed	449,673	4,689,479	10.43
E. Coli Metabolism	Metabolites	Chemical reactions	Directed	1,039	5,802	5.58
Protein Interactions	Proteins	Binding interactions	Undirected	2,018	2,930	2.90

2.3. 度、平均度和度分布（Degree, Average Degree and Degree Distribution）

$k_i$为第$i$个节点的度。
连接数：

$$L=\frac12\sum_{i=1}^Nk_i$$

平均度：

$$\langle k \rangle=\frac1N\sum_{i=1}^Nk_i=\frac{2L}{N}$$

对于有向图：

$$\begin{align} k_i=k_i^{in}+k_i^{out}\\ L=\sum_{i=1}^Nk_i^{in}=\sum_{i=1}^Nk_i^{out}\\ \langle k_i^{in} \rangle = \langle k_i^{out} \rangle=\frac L N \end{align}$$

度分布：
$p_k$表示随机在网络中随机选取一个节点，它的度为$k$的概率，则满足：

$$\sum_{k=0}^{\infty}p_k=1$$

则度为$k$的节点个数为：

$$N_k=p_kN$$

平均度可以表示为：

$$\langle k \rangle=\sum_{k=0}^{\infty}kp_k$$

度分布很重要

2.4. 邻接矩阵（Adjacency Matrix）

定义：一个图的邻接矩阵是指这样一个$N\times N$的矩阵$\pmb A$，其元素$A_{ij}$满足：

$$A_{ij}= \left \{ \begin{aligned} 1&, \space if \space there \space is \space a \space link\space pointing\space \pmb{from\space node \space j \space to \space node \space i}.\\ 0&,\space if\space nodes\space i\space and\space j\space are\space not\space connected\space to\space each\space other. \end{aligned} \right.$$

• 无向图的邻接矩阵是对称的；
• 有向图不是对称的；
• 无自环图的邻接矩阵对角线为0。

根据邻接矩阵，我们可以将度的性质表示出来：

• 节点的度：$k_i=\sum_{j=1}^{N}A_{ij}$
  • 对于有向图而言：
    • $k_i^{out}=\sum_{j=1}^{N}A_{ji}$
    • $k_i^{in}=\sum_{j=1}^{N}A_{ij}$
• 总连接数：$2L=2\sum_{i=1}^{N}k_i^{in}=2\sum_{i=1}^{N}k_i^{out}=\sum_{ij}^{N}A_{ij}$

邻接矩阵更重要！

2.5. 真实的网络是稀疏的（Real Networks are Sparse）

对于一个含有$N$个节点的网络来说，如果其有向，则最大连边数为$N(N-1)$，如果其无向，则最大连边数为$\frac{N(N-1)}2$。
对于万维网（WWW）来说，其拥有325,729个页面，完全图需要$10^{12}$个连接，而实际上只有1,497,134个，只有不到0.000001%。

2.6. 加权网络（Weighted Networks）

连边带权：$A_{ij}=w_{ij}$。

麦特卡菲定律（Metcalfe’s Law）：网络构建的成本随着节点的数目线性增长，而收益却是二次曲线。
有一定道理，不过大多数网络是稀疏的，所以收益是线性的；同时网络中并非所有的连接都是等同的，大多数的连接很少被使用，也就是权重较低。

2.7. 二部图（Bipartite Networks）

定义：二部图是指这样的图，可以将其节点集合划分为两个不重叠的非空子集$U$和$V$，其中同一集合内的节点之间没有边相连，只有属于不同集合的节点之间可能存在边相连。

• 二部图的投影：二部图的投影是针对其中的一个集合的一张图，若该集合中的两个点在二部图中有公共的邻居，那么在投影中这两个点相连。
• 
  人类疾病图（Human Disease Network, or deseaseome)：
• 人类疾病图是一个二部图，两个子集分别为疾病和基因，可以投影为两个图：
  • 疾病图：节点为疾病，两个疾病如果有边相连，就说明它们有共同的影响基因。
  • 基因图：节点为基因，如果两个基因与同一个疾病有关，则有边相连。
    
    类似地，可以定义多部图（multipartite networks)，比如“食谱—原料—成分”图。

2.8. 路径和距离

注意区分欧拉路径和哈密顿路径：

• 欧拉路径（Eulerian Path）指的是经过每个边一次；
• 哈密顿路径（Hamiltonian Path）指的是经过每个节点一次。
  最短路径如何计算？
• 路径的计算可以使用BFS广度优先算法计算；
• 路径的数目可以通过对邻接矩阵进行乘方运算：

  命题：从节点$i$到节点$j$的距离为$d$的路径数目为$A^d_{ij}$，表示邻接矩阵$A$的$d$次方的第$ij$元素。
  证明：
  令$N_{ij}^{(d)}$表示从$i$到$j$的长度为$d$的路径数目，只需证明：$N_{ij}^{(d)}=A_{ij}^{d}$。
  对距离$d$采用数学归纳法：
  首先对于$d=1$，$A_{ij}$定义即为证明，固有$N_{ij}^{(1)}=A_{ij}^{1}$。
  以下考虑$d\ge 2$：
  考虑从节点$i$到节点$j$的长度为$d$的路径的最后一步，根据加法原理和乘法原理：
  $N_{ij}^{(d)}=\sum_{k=1}^N N_{ik}^{(d-1)}N_{jk}^{(1)}=\sum_{k=1}^N A_{ik}^{d-1}A_{jk}^{1}=A_{ij}^{d}$
  证毕。

网络的直径（Network Diameter）：网络中两节点最短距离的最大值。
网络的平均距离（Average Path Length）：网络中两两节点最短距离的平均值：$\langle d \rangle=\frac 1 {N(N-1)}\sum_{i,j=1,N;i\neq j}d_{ij}$
网络的距离分布（Distance Distribution）：距离为$d$的点对的概率。

2.9. 连通性（Connectedness）

关注寻找网络连通分支的算法。

2.10. 集聚系数（Clustering Coefficient）

定义：