复杂网络基础理论 作者 郭世泽 陆哲明课件第六章

复杂网络复杂网络复杂网络中的搜索复杂网络中的搜索6.1 引言 搜索算法的研究是复杂网络研究中的一项重要内容。复杂网络中的搜索有着大量的实际应用：包括社会网络中两个人之间的最短关系链寻找、WWW 中网页的搜索、P2P（Peer-to-Peer）网络中指定文件或数据的搜索及任意两个城市之间的最短路径的寻找等等。本章首先介绍三种经典的搜索策略，即广度优先搜索算法、随机行走搜索算法和最大度搜索算法，然后介绍社会网络的快速分散式搜索问题，最后介绍 P2P 网络和 WWW 网络的搜索问题。6.2 广度优先搜索算法6.2.1 复杂网络搜索问题6.2.2 广度优先搜索策略 6.2.3 广度优先搜索算法实现6.2.4 广度优先搜索算法的应用和特性 6.2.1 复杂网络搜索问题复杂网络搜索策略通常用一个消息传递的过程来描述。从一个给定的源节点开始，为了寻找所需要的信息，按照一定的规则向它的一个或多个邻居传递查询消息。如果收到查询的邻居节点上不含有源节点所需的信息，那么这些邻居节点再将查询传递给它们各自的邻居，重复这个过程直到存储着指定信息的目标节点被寻找到为止，然后目标节点将信息传递给源节点。一般而言，网络的小世界特性并不一定意味着网络是可以快速搜索的。在一个大规模的网络中，连接两个节点之间的路径可能有很多条，网络中的一个节点是否能找到它与任一其它节点之间的较短甚至最短的路径，依赖于节点所了解的网络结构信息、节点所使用的搜索算法和整个网络的实际结构。6.2.2 广度优先搜索策略 在许多实际网络中，单个节点无法充分掌握整个网络的全局结构，甚至可能不知道目标节点在网络中的位置。一个最简单的搜索策略就是广度搜索（broadcast search）策略，也就是广度优先搜索（broadth first search，BFS）算法，也叫宽度优先搜索，或横向优先搜索。简单的说，BFS 是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。6.2.2 广度优先搜索策略 当源节点s应用 BFS 策略在网络中的节点上寻找指定的文件时，s首先查询其所有的邻居节点，询问是否含有目标文件，如果s的邻居中有某个节点存储了目标文件，则将目标文件返回给源节点；如果任何邻居都没有含有目标文件，则所有的邻居将查询继续传递给各自的邻居节点，一直到搜索到目标文件为止。当源节点 s 利用 BFS 策略搜索目标节点t时，s首先判断自己的邻居节点中有无目标节点。若有，则中止搜索；若无，则向每个邻居查询它们的邻居节点中有无目标节点。重复这个过程一直到寻找到目标节点的任一个邻居为止。6.2.3 广度优先搜索算法实现已知图G（V，E）和一个源节点s，广度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有节点，并计算s到所有这些节点的距离（最少边数），该算法同时能生成一棵根为s且包括所有可达节点的广度优先树。对从s可达的任意节点v，广度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。之所以称之为广度优先算法，是因为算法自始至终一直通过已找到节点和未找到节点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所节点，然后再去搜索和s距离为k+1的其他节点。6.2.3 广度优先搜索算法实现为了保持搜索的轨迹，广度优先搜索算法将每个节点着色为白色、灰色或黑色。算法开始前所有节点都是白色，随着搜索的进行，各节点会逐渐变成灰色，然后成为黑色。在搜索中第一次碰到某一节点时，我们说该节点被发现，此时该节点变为非白色节点。因此，灰色和黑色节点都是已被发现的节点。但是，广度优先搜索算法还需对它们加以区分以保证搜索以广度优先的方式执行。若（u，v）E 且节点 u 为黑色，那么节点 v要么是灰色，要么是黑色，也就是说，所有和黑色节点邻接的节点都已被发现。灰色节点可以与一些白色节点相邻接，它们代表着已找到和未找到节点之间的边界。6.2.3 广度优先搜索算法实现在广度优先搜索过程中建立了一棵广度优先树，起始时只包含根节点，即源节点s。在扫描已发现节点 u 的邻接表的过程中每发现一个白色节点 v，该节点 v 及边（u，v）就被添加到树中。在广度优先树中，称节点 u 是节点 v 的父母节点。因为一个节点至多只能被发现一次，因此它最多只能有一个父母节点。相对根节点来说祖先和后裔关系的定义如下：若 u 处于树中从根 s 到节点 v 的路径中，那么 u 为v 的祖先，v 是u 的后裔。6.2.3 广度优先搜索算法实现【例6.1】用图6.2 来解释BFS 的处理过程，标明du 以及队列Q 的变化。6.2.3 广度优先搜索算法实现解：图6.3 显示了用BFS 在例图6.2 上的搜索过程。黑色边是由BFS 产生的树枝。每个节点u内的值为du，图中所示的队列Q是while循环中每次迭代起始时的队列。队列中每个节点下面是该节点与源节点的距离。6.2.4 广度优先搜索算法的应用和特性 1 应用 广度优先搜索算法可以用来解决图论中的许多问题，例如：（1）寻找图中所有连通分支（connected component）。这里，连通分支是图中的最大连通子图。（2）寻找连通分支中的所有节点。（3）寻找非加权图中任两点的最短路径。（4）测试一个图是否为二分图（所谓二分图，是指节点可以分成两个不相交的集合使得在同一个集内的节点不相邻（没有共同边）的图）。此外，BFS 还可用来解决电脑游戏（如即时策略游戏）中找寻路径的问题。6.2.4 广度优先搜索算法的应用和特性 2 特性 BFS 的空间复杂度为O（MN）或为O（BD），由于对空间的大量需求，因此 BFS 并不适合求解网络规模非常大的问题。广度优先搜索算法具有完全性。若所有边的权值相等，广度优先搜索算法能找到最佳解亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS 并不一定回传最佳解。这是因为当图形为加权图（亦即各边加权不同）时，BFS 仍然回传从根节点开始，经过边数目最少的解；而这个解离根节点的距离不一定最短。这个问题可以使用考虑各边权值的 BFS 改良算法成本一致搜寻法来解决。6.3 随机行走搜索策略 6.3.1 随机行走搜索策略简介 6.3.2 网络随机行走的基础理论 6.3.3 最近邻耦合网络上的随机行走搜索效率 6.3.4 ER随机网络上的随机行走搜索效率 6.3.5 WS小世界网络上的随机行走搜索效率6.3.1 随机行走搜索策略简介 利用该策略，当源节点s搜索目标节点t时，s首先判断自己的邻居节点中有无目标节点t。如果有，则中止搜索；否则，向其任一个邻居查询它的邻居节点中是否有目标节点。重复该过程直到找到目标节点 t 的任一个邻居为止。与 BFS 策略相比，随机行走的搜索步数要大很多，但由于每一步只前传一个查询消息，从而大大减少了网络中的消息流量。6.3.1 随机行走搜索策略简介 在网络搜索中，人们通常假设每个节点只认识自己的邻居节点，且源节点在网络中寻找目标节点时，可以应用如下三种不同的行走策略：无限制的随机行走搜索策略；不走回头路的随机行走搜索策略；节点不重复访问的随机行走搜索策略。6.3.2 网络随机行走的基础理论 网络上的随机行走跟图论的其它分支有着密切的关系，网络上的随机行走的基本性质由网络的谱所决定。目前，对规则点阵和规则树（树中的节点具有同样的度）上的随机行走已有大量的理论结果。然而，现实世界的网络往往具有比规则点阵和经典的随机网络更复杂的网络拓扑结构，如小世界网络和无标度网络。这些网络与现实网络的重要性质相符合，比如，大的集聚程度、短的平均路径和很广的度分布。网络的搜索效率与搜索策略和网络拓扑结构密切相关。某种搜索策略的搜索效率通常可以用平均搜索步数来表征。6.3.2 网络随机行走的基础理论 对于一个规模为N的网络，某种搜索策略的平均搜索步数定义如下：重复随机选择N个不同的源节点。对每一个选择的源节点vi，应用该搜索策略得到源节点到其他所有N1个节点的搜索步数之和为Ti。由此得到任意两个节点之间的平均搜索步数为：研究发现，随着网络拓扑结构的不同，搜索策略的效率有着很大的区别，也就是说，所得到平均搜索步数变化很大。6.3.3 最近邻耦合网络上的随机行走搜索效率1 理论分析2 仿真验证6.3.4 ER随机网络上的随机行走搜索效率 1 理论分析2 仿真验证6.3.4 ER随机网络上的随机行走搜索效率【例6.2】试分析（6.20）式定义的生成函数G0（x）的导数及其平方特性。解：对（6.20）式求m阶导数可得上式中取x=0，可得 若对 G0（x）求一阶导数再乘以x可得对上述过程执行m次可以得到 6.3.4 ER随机网络上的随机行走搜索效率 上式中取x=1，可得下面来看G0（x）的平方，它可以展开如下：由此可见，上式中xm前面的系数就等于所有满足j+k=m的乘积pjpk的和，它可以准确地反映两个节点度之和为m的概率。6.3.5 WS小世界网络上的随机行走搜索效率由于在WS小世界网络模型中，当重连概率p0时网络为最近邻耦合网络，而p1时网络为ER随机网络。因此，当重连概率p从0到1变化时，WS小世界网络模型的平均搜索步数就是从最近邻耦合网络平均搜索步数到ER随机网络平均搜索步数的逐渐过渡。仿真实验结果证实了这样的一种过渡。6.4 最大度搜索策略 前面提到的两种搜索策略没有考虑复杂网络的度分布。对于许多实际复杂网络来说，其度分布是一种幂律分布，即呈现无标度特性。最大度搜索策略（high degree search，HDS）正是利用节点度的幂律分布特性来搜索的，它最初由Adamic 等人提出。该策略的基本出发点是：邻居的熟人越多，他认识的人越多，则目标有更大的概率被找到。下面首先介绍最大度搜索的策略及其算法，然后利用仿真实验来分析无标度网络幂律指数（反映了网络的均匀性）与最大度搜索效率的关系。6.4.1 最大度搜索策略 6.4.2 最大度搜索策略的效率与网络均匀性关系 6.4.1 最大度搜索策略 应用最大度 搜索策略在网络中的节点上寻找指定的文件或数据的过程可以简要描述如下：源节点s首先查询其度最大的邻居节点，询问是否含有目标文件或数据。如果此邻居节点上存储了目标文件或数据，则它将目标文件或数据返回给源节点；如果此邻居节点上不含有目标文件或数据，则它将选择度最大的邻居将查询传递过去，一直到搜索到目标文件或数据为止。6.4.1 最大度搜索策略 假定每个节点仅仅知道自己邻居节点的信息，即每个邻居节点的度的大小，则使用HDS 策略寻找两个节点之间的路径的步骤可以描述如下：步骤 1：初始时选取源节点 vi与目标节点 vj；步骤 2：从节点vi出发，判断自己的邻居节点中有无目标节点vj：如无，则将其中度最大的邻居节点设为当前节点；如有，则中止搜索；步骤 3：可以多次访问同一个节点，但是同一条边只能被访问一次，如果与当前节点相连的所有的边都被访问过，则返回到上一个节点；步骤4：重复 2 和3 两个步骤，直到当前节点为目标节点的任一个邻居节点，目标节点即被找到，搜索完成。6.4.2 最大度搜索策略的效率与网络均匀性关系 1 无标度网络的幂律指数与网络均匀性关系2 HDS搜索策略与网络均匀性的关系6.5 社会网络的分散式搜索 6.5.1 引言 6.5.2 Kleinberg网格模型的分散式搜索 6.5.3 层次网络模型上的分散式搜索 6.5.4 Kleinberg集合模型上的分散式搜索 6.5.5 基于 Kleinberg网格的动态网络模型的快速分 散式搜索 6.5.6 复杂网络的可搜索性 6.5.1 引言 在 Milgram小世界实验中，人们搜索目标对象时使用的是一种简单的分散式算法，即当前信件的持有者基于局部信息，以最有可能到达目标人的方式来传递信件，也就是说，当前信件的持有者将信件传给他的一个朋友，并且他认为这个朋友在自己所认识的人当中（包括自己）是最接近于目标对象的。因此，这个算法也称为贪婪算法（greedy algorithm）。由于这个算法本身非常简单，没有什么特别