摘要：许多复杂网络中，单个节点无法充分掌握整个网络的全局信息与目标节点的具体位置。因为复杂网络具有不断变化的动态性，准确地确定网络的全局行为是非常困难的。一般在搜索算法中，我们从一个给定的源节点开始查询所需要的目标节点上的文件，按照某一种规则向源节点的某一个或是多个邻居节点发送查询消息，寻找符合目标状态节点的过程。搜索算法的有效性将直接影响到复杂网络的卓越性能。目前复杂搜索策略中有广度优先搜索算法（BFS）、最大度搜索算法（MD）与随机游走搜索算法（RW）等比较经典及常用的算法。除了这三种算法外，其他算法大都是由这三种算法改进而来。本文上述前三种搜索算法的性能进行逻辑分析与比较。
　　关键词：复杂网络；网络模型；网络特性
　　中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）04-0169-02
　　许多复杂网络中，单个节点无法充分掌握整个网络的全局信息与目标节点的具体位置。因为复杂网络具有不断变化的动态性，准确地确定网络的全局行为是非常困难的。一般在搜索算法中，我们从一个给定的源节点开始查询所需要的目标节点上的文件，按照某一种规则向源节点的某一个或是多个邻居节点发送查询消息，寻找符合目标状态节点的过程。搜索算法的有效性将直接影响到复杂网络的卓越性能。鉴于搜索问题的重要地位和实际价值，人们会从不同的角度对搜索问题进行分析研究。我们在这里提出了一种新的基于幂律度分布的搜索算法DBM，它引用BFS与MD的各种优点进行搜索。DBM算法小范围引用BFS搜索算法，大范围引用MD搜索算法，更进一步基于知识进行搜索，提高搜索的效率。为了更可靠地分析并解释，我们选择无标度（BA）网络模型来验证DBM搜索算法的有效性与可行性。
　　1 逻辑分析
　　以下我们将对复杂网络中基本搜索方式广度优先搜索算法（BFS）与最大度搜索算法（MD）进行比较与分析。首先，BFS是一種经典的复杂网络基本搜索算法，它在Internet中获得了比较广泛的应用。事实上，复杂网络中的单个节点往往难以全面反映整个网络的信息，甚至无法明确复杂网络中目标节点的所在位置。在这种情况下我们可以应用的最简单地搜索策略就是广度优先搜索算法（BFS）。BFS搜索算法的工作原理如下：当源节点开始在复杂网络中寻找目标文件时，S先查询所有邻居节点，并向邻居阶段询问是否拥有目标文件，假设S的某个邻居节点上发现目标文件，目标节点即将目标文件反馈给源节点；假设S的邻居节点都不拥有目标文件，S的邻居节点则将查询信息向各自的邻居节点传递查询信息，直到发现目标节点和产讯到目标文件。广度优先搜索算法BFS示例如图1所示：
　　在图中没有搜索过的路径用虚线表示，已经搜索过的路径用实线表示。在这里我们根据最大度算法的搜索思路分析，在最大度搜索（MD）方式中，搜索过程如下：最大搜索策略的应用前提为每个节点都了解其邻居节点度。详细搜索流程为：源节点先查询其度最大的邻居节点，假设此邻居节点为目标节点，则将目标文件反馈回源节点，假设非目标节点，则继续挑选度最大的邻居节点查询，截止到发现目标节点[9]。在这种最大度搜索MD搜索方式中，虽然搜索效率一般，但其产生的搜索消息流量非常小。最大度搜索MD搜索算法过程示例如图2所示：
　　通过比较以上两种搜索方式，我们得到以下结论：选用广度优先搜索算法，可以得到比较小的搜索步数，即可以最快捷地搜索到目标节点，但是查询消息流量特别多。最大度搜索算法获得的查询消息流量比较小的，其搜索步数介于随机游走搜索（MD）和广度优先搜索（BFS）之间。随机游走搜索算法的查找速度最慢，而产生的查询信息流量在其他两种搜索策略之间。具体关系如表1所示：
　　表1 搜索算法比较
　　[搜索算法方式＼