复杂网络中局部搜索策略的研究

作     者：晏仲琦 

作者单位：湖北大学 

学位级别：硕士

导师姓名：罗益辉

授予年度：2012年

学科分类：07[理学] 081203[工学-计算机应用技术] 08[工学] 070104[理学-应用数学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：复杂网络 聚类系数 无标度网络 小世界网络 局部搜索策略 

摘      要：在过去的十年里,复杂网络的研究已经成为众多研究领域中的重要课题之一,复杂网络的搜索策略的研究对实际生活具有重要的意义。复杂网络中的搜索策略是利用节点所了解的网络信息找到从源节点到目的节点的较短路径。在复杂网络中有两种不同的搜索策略,即全局搜索策略和局部搜索策略。全局搜索策略,在搜索的过程中需要知道网络的全局信息,才能找到目的节点；局部搜索策略则利用网络的局部信息搜索目的节点。由于在许多实际网络中,单个节点是无法知道整个网络的全局信息,因此,局部搜索策略的研究一直是复杂网络搜索策略研究的重点之一。 本文研究了基本的复杂网络拓扑特征、拓扑模型和搜索策略,比较、分析和评价了已有的复杂网络搜索策略。在此基础上,根据网络的拓扑结构特征,提出了两种局部搜索策略。具体的研究内容和成果如下： 1.在深入研究复杂网络聚类系数和小世界网络的拓扑结构的关系的基础上,我们修改了聚类系数的定义,利用聚类系数这一刻画复杂网络结构特性的量,设计出最小聚类系数搜索策略,即当前节点选择聚类系数最小的邻居节点传递信息。然后,比较了最小聚类系数搜索策略、最大度搜索策略和随机搜索策略。通过实验,我们发现最小聚类系数搜索策略在小世界网络上的搜索性能是最好的。 2.针对大多数实际的网络都含有度量空间,建立了一个可调参数的无标度空间网络模型。在此基础上,根据无标度空间网络的结构特性,结合度和度量距离这两个影响搜索性能的量,设计出最大度最小距离搜索策略。随后,比较最大度最小聚类系数搜索策略和几种其他的搜索策略。经过试验,发现最大度最小距离搜索策略更适用于无标度空间网络。