1.8 路径和距离

物理距离在物理系统各组成部分间的交互中起着关键作用。例如，晶体中两个原子间的距离、宇宙中两个星系间的距离决定着它们之间作用力的大小。

网络距离是一个比较难理解的概念。什么是两个网页之间的距离？互不相识的两个人之间的距离是多少？物理距离在这里不再适用：两个网页可能放置在位于地球上位置不同、方向相反的两台电脑上，但它们之间有一个链接使彼此相连。同时，生活在同一栋楼上的两个人可能互不认识。

网络中，物理距离被路径长度取代了。路径是指沿着网络中的链接行走经过的线路。路径的长度表示其包含的链接个数（图1-12a）。注意，有些情况下会要求一条路径经过每个节点不能超过一次。

图1-12 路径

（a）节点i0和节点in之间的一条路径是包含n个链接的一个有序列表P={(i0,i1),(i1,i2),(i2,i3),…,(in-1,in)}。路径的长度为n。图a中的橙色路径对应的线路为1→2→5→7→4→6，路径长度为n=5。

（b）节点1和节点7之间的最短路径对应着连接节点1和节点7的、包含最少链接数的路径。如图中的橙色路径和灰色路径所示，存在多条长度相同的路径。网络直径是网络中所有节点对之间的最大距离，这里的网络直径为dmax=3。

在网络科学中，路径扮演着核心角色。接下来，我们将探讨一些关于路径的重要性质（更多介绍参见图1-13）。

图1-13 路径学

最短路径

节点i和节点j之间的最短路径是指包含链接数最少的路径（图1-12b）。最短路径的长度通常被称为节点i和节点j之间的距离，记为dij或简略记为d。同一对节点之间可能有多条长度相同的最短路径（图1-12b）。注意，最短路径不会包含环或自环。

在无向网络中，我们有dij=dji，即节点i和节点j之间的距离等于节点j和节点i之间的距离。在有向网络中，通常情况下dij≠dji。另外，有向网络中，存在节点i到节点j的路径并不意味着存在节点j到节点i的路径。

在真实网络中，我们通常需要确定两个节点之间的距离。对于小网络而言，譬如图1-12所示的网络，这是一件容易的事情。不过，对于有数百万个节点的网络而言，找出两个节点之间的最短路径就相当费时了。最短路径的长度和最短路径的个数可以从邻接矩阵得到（边栏1.4）。实际上，我们通常采用边栏1.5中讨论的广度优先搜索算法来实现。

边栏1.4

两个节点间的最短路径数

节点i和节点j之间的距离dij和最短路径数Nij可以从邻接矩阵Aij直接计算得到。

dij=1：如果节点i和节点j之间有直接链接（Aij=1），则dij=1。

dij=2：如果节点i和节点j之间存在长度为2的路径，假如该路径经过的中间节点为k，则有AikAkj=1；否则AikAkj=0。因此，节点i和节点j之间长度为2的路径数为

这里[…]ij表示矩阵第i行第j列的元素。

dij=d：如果节点i和节点j之间存在长度为d的路径，则该路径包含的链接所对应的邻接矩阵元素相乘为1，即Aik…Alj=1；否则Aik…Alj=0。因此，节点i和节点j之间长度为d的路径数为：

上述公式对于有向网络和无向网络都适用。节点i和节点j之间的距离是满足的最小的d（注意，这里的路径不能包含环或自环）。虽然该方法很简洁，但对于大的网络，更高效的方法是边栏1.5描述的广度优先搜索算法。

网络直径

网络直径，记为dmax，是指网络中所有最短路径的最大长度。换句话说，网络直径是指网络中所有节点对之间的最大距离。图1-13所示的网络，其直径为dmax=3。对于较大的网络，网络直径可以使用边栏1.5中讨论的广度优先搜索算法计算得到。

平均路径长度

平均路径长度，表示为，是指网络中所有节点对之间的平均距离。对于包含N个节点的有向网络，我们有

注意，公式1.14只测量出现在同一个网络连通分支中的节点对（1.9节）。我们可以使用广度优先搜索算法来计算一个大网络的平均路径长度。为此，首先使用边栏1.5中的算法计算第一个节点和其他所有节点的距离，再计算第二个节点和其他所有节点（对于无向网络，第一个节点除外）的距离，然后再对其他所有节点重复该过程。

边栏1.5

广度优先搜索算法

广度优先搜索（BFS）算法是网络科学中经常使用的一个算法。向池塘里扔一块石头，然后观察扩散开的涟漪，这就是BFS算法的思想。BFS算法从一个源节点出发，标记其邻居（第一个涟漪），然后是邻居的邻居（第二个涟漪），直到到达目标节点。到达目标节点之前需要的“涟漪”数就是源节点和目标节点间的距离。

寻找节点i和节点j之间最短路径的步骤如下（图1-14）：

图1-14 广度优先搜索算法示例

（a）从标记为0的橙色节点出发，找出其所有邻居节点，并标记为1。

（b）~（d）接下来，对于标记为1的节点，找出其所有未标记的邻居节点，将其标记为2。在随后的迭代中，逐渐增加标记数，直到所有节点都被标记完为止。算法结束后，节点0和任意其他节点i之间的最短路径长度或者距离d0i为节点i的标记。例如，节点0和距离其最远的节点之间的距离为d=3。

（1）从节点i出发，将其标记为0；

（2）找出与节点i直接相连的节点，标记为距离1，然后将它们放到一个队列中；

（3）从队列中取出最前面的节点（其距离标记假设为n），找出和该节点相连且尚未被标记的节点，将它们标记为n+1，然后把它们放在队列的后面；

（4）重复步骤3，直到碰到目标节点j或者队列中没有节点了；

（5）节点i和节点j之间的距离为节点j的标记。如果节点j没有标记，则dij=∞

对于有N个节点和L个链接的网络而言，BFS算法的计算复杂度（即计算机计算dij所需要的步数）为O(N+L)。计算复杂度和N、L是线性关系，因为每个节点需要进入和离开队列各一次，而每个链接需要被检测一次。