曾 成

(贵州省网络信息安全技术维护管理中心,贵州 贵阳 550001)

0 引言

在很长一段时间里, 搜索问题是复杂网络中比较热门的一个研究课题,大部分学者将主要研究放在了无权网络上,也就是将现实中的网络抽象化,接着再将其弱化为布尔网络来研究[1-4]。 大量实验结果证明了网络节点之间连接关系的紧密程度是不一样的,并不全都是布尔关系,人们把这类网络称为加权网络[5]。由此可知,研究加权网络中高效的搜索方法已变得很有意义,能将复杂网络的搜索问题具体地描述成信息之间的传递过程。 常用的局部搜索策略有:随机游走(Rand Walk,RW)策略和最大度搜索(High Degree Seeking,DS)策略[6]。 2005 年,Thadakamalla 等[7]提出一种适用于加权网络的搜索算法,他们在具有幂律分布的加权网络中使用一种利用局部介数(Local Betweenness Centrality,LBC)的分步式算法,并得到了很好的效果。 Yan 等[8]提出的利用加权网络搜索算法。 在具有幂律分布的网络中,最大局部介数搜索策略在搜索时间和搜索代价这一系列参数上要明显优于RW 策略和DS 策略。 以上的搜索算法虽然效率很高,但忽视了边权值[9]大小对节点搜索信息量的影响,所以在同时考虑边权值和节点聚类系数及复杂网络聚类与局部搜索[10]的基础上,结合了BBV 网络[11]的特性,本文提出一种结合节点聚类系数和边权值大小的搜索算法,即最小聚类系数最小距离(Minimum Clustering Coefficient and Distance,MCD)搜索算法。

1 理论分析

BBV 网络与其他网络存在较大差异性,当路线选择不理想时,会增添很多不必要的损耗。 与此同时,在BBV 网络中存在一种hub 的节点,这种hub 节点有着密集的节点结构。……