复杂网络基础理论第六章复杂网络中的搜索.ppt

复杂网络基础理论第六章复杂网络中的搜索.ppt

《复杂网络基础理论第六章复杂网络中的搜索.ppt》由会员分享，可在线阅读，更多相关《复杂网络基础理论第六章复杂网络中的搜索.ppt（68页珍藏版）》请在冰点文库上搜索。

复杂网络,复杂网络中的搜索,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广度优先搜索策略,在许多实际网络中，单个节点无法充分掌握整个网络的全局结构，甚至可能不知道目标节点在网络中的位置。

一个最简单的搜索策略就是广度搜索（broadcastsearch）策略，也就是广度优先搜索（broadthfirstsearch，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）寻找图中所有连通分支（connectedcomponent）。

这里，连通分支是图中的最大连通子图。

（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.4ER随机网络上的随机行走搜索效率6.3.5WS小世界网络上的随机行走搜索效率,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.4ER随机网络上的随机行走搜索效率,1理论分析2仿真验证,6.3.4ER随机网络上的随机行走搜索效率,【例6.2】试分析（6.20）式定义的生成函数G0（x）的导数及其平方特性。

解：

对（6.20）式求m阶导数可得上式中取x=0，可得若对G0（x）求一阶导数再乘以x可得对上述过程执行m次可以得到,6.3.4ER随机网络上的随机行走搜索效率,上式中取x=1，可得下面来看G0（x）的平方，它可以展开如下：

由此可见，上式中xm前面的系数就等于所有满足j+k=m的乘积pjpk的和，它可以准确地反映两个节点度之和为m的概率。

6.3.5WS小世界网络上的随机行走搜索效率,由于在WS小世界网络模型中，当重连概率p0时网络为最近邻耦合网络，而p1时网络为ER随机网络。

因此，当重连概率p从0到1变化时，WS小世界网络模型的平均搜索步数就是从最近邻耦合网络平均搜索步数到ER随机网络平均搜索步数的逐渐过渡。

仿真实验结果证实了这样的一种过渡。

6.4最大度搜索策略,前面提到的两种搜索策略没有考虑复杂网络的度分布。

对于许多实际复杂网络来说，其度分布是一种幂律分布，即呈现无标度特性。

最大度搜索策略（highdegreesearch，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无标度网络的幂律指数与网络均匀性关系2HDS搜索策略与网络均匀性的关系,6.5社会网络的分散式搜索,6.5.1引言6.5.2Kleinberg网格模型的分散式搜索6.5.3层次网络模型上的分散式搜索6.5.4Kleinberg集合模型上的分散式搜索6.5.5基于Kleinberg网格的动态网络模型的快速分散式搜索6.5.6复杂网络的可搜索性,6.5.1引言,在Milgram小世界实验中，人们搜索目标对象时使用的是一种简单的分散式算法，即当前信件的持有者基于局部信息，以最有可能到达目标人的方式来传递信件，也就是说，当前信件的持有者将信件传给他的一个朋友，并且他认为这个朋友在自己所认识的人当中（包括自己）是最接近于目标对象的。

因此，这个算法也称为贪婪算法（greedyalgorithm）。

由于这个算法本身非常简单，没有什么特别的性质，因此有一定数量的信件在较短步数内成功到达了目标这一事实表明，社会网络结构本身一定有其特殊的性质。

为什么如此简单的分散式搜索算法在具有小世界特性的网络中能得到非常有效的结果呢？

6.5.2Kleinberg网格模型的分散式搜索,1Kleinberg网格模型Kleinberg网格模型是指一个含有Nnn个节点的二维网格，它假定节点u和v之间有长程连接的概率puv与它们之间网格距离d（u，v）的某个负指数成正比。

6.5.2Kleinberg网格模型的分散式搜索,2Kleinberg网格模型上的分散式搜索定理定理6.1：

对于0的二维网格NW小世界网络，存在一个与a、b相关但与n无关的常数c0，使得对于任意的分散式算法，平均传递步数都有一个下界c0n2/3。

定理6.2：

当2且ab1时，存在一种分散式算法和一个与n无关常数c2，使得该算法的平均传递步数有一个上界c2（log2n）2。

定理6.3：

对于02，存在一个与a、b、相关但与n无关的常数c，使得对于任意的分散式算法，平均传递步数都有一个下界cn（2-）/3。

定理6.4：

对于2，存在一个与a、b、相关但与n无关的常数c，使得对于任意的分散式算法，平均传递步数都有一个下界cn（-2）/（-1）。

6.5.2Kleinberg网格模型的分散式搜索,【例6.3】证明上面提到的分散式算法的简单规则满足定理6.2。

证明：

因为ab1，网格中的每个节点u都和4个最近的邻居有连接（对网格边缘节点来说可能只有2个或3个）且有1个单一的长程连接v。

因为2，u选择v作为长程连接的概率满足：

当j0，如果当前信件持有者与目标节点之间的网格距离在2j和2j+1之间，那么就称该算法到达阶段j。

我们称算法处于阶段0，如果当前信件持有者与目标节点之间的格点距离最多为2。

因此，j取值最多为log2n。

6.5.2Kleinberg网格模型的分散式搜索,若采用上面提到的分散式算法的简单规则，在每一步操作后信件持有者和目标节点的距离将严格递减。

每个变为信件持有者的节点在此之间从未接触过信件，所以可以假设和信件持有者的长程连接是在这个时刻生成。

现在假设算法处于阶段j且满足而当前信件持有者为u。

那么阶段j结束的概率是多少呢？

这需要信件进入集合Bj，该集合由离目标节点t的网格距离不超过2j的节点组成。

而至少有个个节点在集合Bj中，其中每个节点与信件持有者u的网格距离不超过者u的网格距离不超过因此Bj中的每个节点均至少有的概率作为u的长程连接，由此可以得到信件进入集合Bj的概率为：

6.5.2Kleinberg网格模型的分散式搜索,当时，令Tj代表阶段j花掉的搜索步数，可以求出其期望值为：

对于jlog2n的情况，可得到类似的界，使得结果成立。

而对于0jlog2（log2n），即使只采用短程连接传递信件，算法最多需要log2n步，因此ETj128ln（6n）也成立。

从而，平均搜索总步数可以计算如下：

其中，c2是合理选择的一个正的常数。

证毕。

6.5.2Kleinberg网格模型的分散式搜索,6.5.3层次网络模型上的分散式搜索,1Kleinberg的研究结果Kleinberg设计的层次模型的基本思想如下：

在层次结构中相距越远的节点建立连接的概率越低。

该模型被称为“层次模型”，底层结构是含有N个叶子的完全b叉树（由此可得树的高度为llogbN）。

对于叶子节点v和w，定义它们的距离d（v，w）为最低共同父节点的高度。

之后，以叶子节点集V建立随机有向图G：

对集合V中的每一个节点v加上k条由节点v出发的有向边，另一端节点w按照概率bd（v,w）进行选择。

6.5.3层次网络模型上的分散式搜索,2Watts等人的研究结果与Kleinberg层次模型相比，Watts等人所提出的层次结构模型更加侧重于刻画社会网络的特性。

在他们提出的层次树状结构中，定义节点vi和vj最低的共同父节点所在的层数为它们之间的距离dij；当节点vi和vj在同一个群中时，dij1。

节点vi和vj向上找到的共同祖先的层数越高，他们之间的距离就越大。

个体（用点表示）首先聚集成团体（用椭圆表示），然后小的团体再通过聚集成为更大的团体，这样继续下去就形成了一个层次树结构。

6.5.3层次网络模型上的分散式搜索,2Watts等人的研究结果,6.5.3层次网络模型上的分散式搜索,综上所述，Watts等人提出的模型是关于社会网络中搜索问题的一个模型。

但是这个模型也可以用于其他领域的分散式搜索问题。

比如，在设计数据库时，一个主要的难点就是缺少唯一的分类方案。

这个模型使得该难点转化为一种资源，允许多种分类方案同时存在，同时在多种分类中对相似的文件做优先连接。

这样在只知道局部信息时，简单的贪婪算法也能实现快速搜索。

图6.16Milgram实验和Watts层次模型实验的长为T的完整信件传递链的条数n（T）的分布图对比,6.5.4Kleinberg集合模型上的分散式搜索,定义节点集V和它的子集集合V1，V2，Vm，该集合被称为“组”的集合。

有如下三个性质：

（1）全集V是一个组。

（2）如果Vi是一个包含节点v且规模g2的组，那么存在一个包含v的组VjVi必定严格小于Vi，但规模不小于min（g，g1）。

（3）如果组Vi1，Vi2，含有公共节点v且组的大小至多是g，则它们的并的大小至多是g。

其中，性质（3）可以看作一种“限制增长”的条件，容易证明性质

（1）和性质

（2）对于网格模型的子块和层次模型的生成子树都成立。

6.5.4Kleinberg集合模型上的分散式搜索,定理6.7：

对于满足性质

（1）

（2）（3）的任意集合模型，若1，出度kcln2N，存在分散式算法使得在该模型中的搜索步数是lnN的多项式函数。

定理6.8：

对于满足性质

（1）

（2）（3），且1，出度k是lnN的多项式函数的每个集合模型，不存在分散式算法使得其搜索步数是lnN的多项式函数。

6.5.5基于Kleinberg网格的动态网络模型的快速分散式搜索,Kleinberg以d维网格的小世界网络模型为基础研究了社会网络的快速搜索现象，并推导出当且仅当网络结构化参数d时才可以采用分散式算法实现快速搜索。

但是，Kleinberg网格结构是固定不变的，而社会网络的拓扑结构应该是动态变化的。

如果某个节点发现在网络中难以搜索到另一个节点，那么这个节点就会试图修改它自己的连接，使得以后的搜索变得容易。

也就是说，各个节点可通过动态调节其连接而使得整个网络可以实现快速搜索。

基于Kleinberg网格的动态网络模型,6.5.5基于Kleinberg网格的动态网络模型的快速分散式搜索,6.5.6复杂网络的可搜索性,可搜索性的研究最早由Sneppen等人于2005年提出。

他们基于信息熵的角度对网络进行分析，提出衡量可搜索性的若干参数：

搜索信息S、获取信息A和躲藏信息H。

随后，该研究组的Rosvall等人又将这一工作进行了扩展分别在不同的网络模型中进行对比研究。

定义了搜索信息后，就可以很容易回答一些实际问题1.第一个问题是：

从哪个点开始最有利于搜索全网络？

答案是具有最小获取信息的节点。

2.另一个问题是：

哪个节点是网络中隐藏得最好，最不易被发现的节点呢？

答案是具有最大躲藏信息的节点。

6.5.6复杂网络的可搜索性,【例6.4】基于Rosvall等人的定义，计算图6.19所示网络从节点s到节点t的搜索信息量Su、Sd和S，其中Su的计算以最左边的最短路径为例，并且分别说明它们的含义。

6.5.6复杂网络的可搜索性,解：

从节点s到节点t的搜索信息量Su、Sd和S的求解过程分别如图6.20（a）（b）（c）所示，节点旁边的数字为该节点的信息代价（单位：

比特）。

箭头的粗细表示加权平均求最终搜索信息时，每条最短路径的所占的权重，越粗表示权重大。

箭头旁边的数字表示以多大的概率往该方向走。

6.5.6复杂网络的可搜索性,在图6.20（a）中，对于最左边的路径，ki=2、km=2、kb=2，代入式（6.53），结果为：

这个值表示沿着固定的最短路径走的搜索信息代价，要回答一次yes/no问题。

在图6.20（b）中，为了求Sd，要对三条最短路径加权求和，而在节点vi和vn处需要选择方向，均以均等概率选取方向。

根据式（6.54）可以求得：

于是，根据式（6.55）可以求得：

6.5.6复杂网络的可搜索性,在图6.20（c）中，为了求对S极小化后的S，在分叉vi和vn处不应该采用均等概率来选取方向。

根据（6.56）式可以直接求得：

6.6Internet中的搜索,6.6.1P2P网络6.6.2基于广播方式的Gnutella网络搜索6.6.3基于K-遍历器随机行走的Gnutella网络搜索6.6.4基于度分布的Gnutella网络搜索6.6.5WWW网中的搜索,6.6.1P2P网络,P2P是英文Peer-to-Peer的缩写，P2P可以理解为对等互联网。

国内的媒体一般将P2P翻译成“点对点”或者“端对端”，学术界则统一称为对等计算。

P2P可以定义为：

网络的参与者共享他们所拥有的一部分硬件资源（处理能力、存储能力、网络连接能力、打印机等），这些共享资源通过网络提供服务和内容，能被其它对等节点（Peer）直接访问而无需经过中间实体。

在此网络中的参与者既是资源（服务和内容）提供者（server），又是资源获取者（client）。

从计算模式上来说，P2P打破了传统的ClientServer（CS）模式，在网络中的每个节点的地位都是对等的。

每个节点既充当服务器，为其他节点提供服务，同时也享用其他节点提供的服务,6.6.1P2P网络,P2P技术的特点体现在以下几个方面：

（1）非中心化；

（2）可扩展性；（3）健壮性；（4）高性价比；（5）隐私保护；（6）负载均衡。

根据具体应用不同，可以把P2P大致分为以下这些类型：

（1）文件内容共享和下载；

（2）计算能力和存储共享；（3）基于P2P技术的协同与服务共享平台；（4）即时通讯工具；（5）P2P通讯与信息共享；（6）基于P2P技术的网络电视。

6.6.1P2P网络,目前已有的P2P网络中存在着如下四种不同的拓扑结构1中心化拓扑2全分布式非结构化拓扑3全分布式结构化拓扑4半分布式拓扑、每种拓扑结构的P2P网络的优缺点：

6.6.2基于广播方式的Gnutella网络搜索,1Gnutella网络在Gnutella文件共享网络中，每个节点为一个客户端计算机。

每一个想要加入网络的客户端首先获取另一个已在网络中的客户端的ip地址并尝试与此客户端建立连接来使自己与网络相连。

如果连接成功，他们之间就相当于加上了一条边。

6.6.2基于广播方式的Gnutella网络搜索,2广度优先搜索（BFS）Gnutella网络不设置中心服务器，因而避免了因中心服务器故障而导致的通信错误。

这样一来，一个显而易见的缺点就是用户并不知道所需文件的具体位置。

虽然文件的名字已知，但是用户并不知道每一次信息的传递是接近还是远离了目标节点，即目标节点位置的全局信息是未知的。

Gnutella网络中所有的查询都通过在网络中进行广播的方式进行，使用的是广度优先搜索算法。

广度优先搜索方法是十分高效的，用户可以在很短的时间内找到所需的目标文件。

但是，该方法的缺点是会在网络中产生大量查询数据流量，容易形成网络阻塞，从而影响了Gnutella软件的可使用性。

6.6.2基于广播方式的Gnutella网络搜索,为了减轻Gnutella网络中广度优先搜索方法所带来的大量流量负载，学者们提出了许多改进方法，其中典型的三种方法分别介绍如下：

1有向广度优先搜索（DirectedBFS）2本地索引搜索（LocalIndices）3迭代加深搜索（Iterationdeepening）,6.6.2基于广播方式的Gn