结合最大度与最小聚类系数的复杂网络搜索策略研究

摘要

复杂网络中的搜索问题涉及网络中指定文件或数据的寻找及网络节点间最短路径的确定,具有重要的现实意义和较高的研究价值。复杂网络搜索策略通常可用一个消息传递的过程来描述,多采用局部搜索方式,其性能将直接影响到能否快速有效地搜索到所需要的目标,以及找到目标所花费的代价能否被接受。实际的复杂网络中普遍同时存在多种拓扑特征,本文从兼顾无标度和小世界特性的角度出发,对局部搜索策略进行了深入的分析、研究和改进。
　　 本文研究了基本的复杂网络拓扑特征、拓扑模型和搜索策略,比较了各种复杂网络搜索策略的优劣,分析了最大度搜索策略的缺陷成因,指出存在一分界值,可使得对于该范围内的节点的搜索过程符合“按度序列搜索”的设想,保证最大度搜索策略的高效。基于分界值,本文提出了将复杂网络中的节点按其度的大小分为两部分的思想,对度小于分界值的那一部分节点采用最大度搜索策略,而对度不小于分界值的那一部分节点采用最小聚类系数搜索策略,并设计了结合最大度与最小聚类系数的复杂网络搜索策略。本文完成了对现有的实际复杂网络数据集的分析和处理工作,将包含着网络邻接矩阵的数据集转换成为了存储着网络全部节点的数组,并抽取和计算了节点的相关局部信息,之后实现了最大度搜索策略、最小聚类系数搜索策略、最大-最小度搜索策略及本文提出的结合最大度与最小聚类系数的复杂网络搜索策略的具体搜索过程。
　　 本文使用具有不同复杂网络拓扑特征的数据集,完成了相关的仿真测试工作,并依据平均搜索步数和平均搜索时间这两大有效性指标,比较、分析和评价了各个复杂网络搜索策略的搜索效果,验证了结合最大度与最小聚类系数的复杂网络搜索策略的正确性和有效性。