论文部分内容阅读
20世纪90年代以来,以Internet为代表的信息技术的迅猛发展使人类社会大步迈入了网络时代,使得复杂网络成为目前研究的热点,而搜索算法的研究又是其中的一个重要内容。
在Internet等各种网络中,常常需要对网络中的资源进行搜索,因而网络搜索算法的有效性显得非常重要,它直接影响了能否搜索到所需要的资源以及能否快速有效地搜索到所需要的资源。现有多种搜索算法,比如广度优先搜索算法(BFS)、随机游走搜索算法(RWS)、最大度搜索算法(DS)。然而,这些搜索策略是有其缺点的。广度优先搜索算法是搜索与该节点相连的所有路径,随着搜索的逐步扩散便形成了广播,造成大量的通信流量,增大了网络拥塞的可能性。而随机游走搜索算法和最大度搜索算法在每次搜索中只选取与该节点相连的一条路径进行搜索,这样又降低了搜索算法的效率和性能。
本文首先介绍了复杂网络的基本概念,各种网络模型,介绍了现有的几种搜索策略。然后针对现有搜索策略的缺点,根据很多现实网络中的度分布并不是均匀的,而是服从幂律分布的,提出了新的搜索策略,即基于幂律度分布的二支路最大度搜索算法。该搜索算法研究了介于广度优先搜索算法和最大度搜索算法这两种方法之间的情况,使搜索过程中搜索速度和搜索代价这两个性能指标取得平衡,提高了搜索的综合性能。最后通过仿真对二支路最大度搜索算法、BFS和DS这三种搜索算法的性能进行了对比,仿真结果表明,二支路最大度搜索算法算法取得了良好的性能。