一种基于BBV 网络的局部搜索策略

曾 成

(贵州省网络信息安全技术维护管理中心,贵州 贵阳 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 节点有着密集的节点结构。 它虽然不会产生数据包,但有着强大的数据包转发能力,能让数据包缩短找到目标节点的时间。 所以hub 节点附近的网络线路会比较复杂、搜索信息量大,则相对于其他网络更容易形成堵塞[12]。

和无权网络不同的是,加权网络在一定程度上可以表现出节点之间关联程度的不同。 在搜索进行时,这种关联程度的不同会直接影响到邻居节点的选择。用选择因子Cij来表示这种影响(其中Cij是节点i和j之间的边lij对应的): 下一个节点被选中的概率与Cij有关,Cij的值越大选中概率就越大。 然而,在加权网络中,权值的具体表示决定了Cij怎么计算。

最短路径在网络中是节点与节点联系最紧密的路径,且搜索代价也是最小的路径。 在加权网络里,在选择下一节点的时候,其选择概率与选择因子是成正比的。 这种情况下边lij(选择因子为Cij)下一步选择节点的概率定义为:

其中,N(i) 为节点i附近所有相邻节点的集合,p为上一步走过的节点,Csum(i) 是节点i对相邻各边计算选择因子Cij后进行的求和。 此时,节点i的搜索信息值则可以定义为:

BBV 网络模型中每个节点之间的流量是用权值来表示的,如果节点之间流量过大,那么搜索的难度也会随之增加,由于以上原因,选择因子与权值成反比,则由Cij=。 可以看出,如果加权网络中路径越短,那么流量就越小,道路就越畅通。

邻近节点之间的集团性质是由该节点的聚类系数体现出来的,如果各个节点联系越紧凑,那么该顶点的聚类系数就会越高。 加权网络集聚系数[13]是由Barrat和他的团队,根据无权网络集聚系数的基础上被定义的,加权网络集聚系数为:

由以上信息,并结合聚类系数与搜索信息,如果想要很快地找寻目标节点,只需要在搜索时把信息送达流量比较小、聚类系数比较小的邻居节点即可。

2 算法设计

根据影响搜索算法的权值、借点聚类系数和BBV网络的特点,提出了一种结合节点聚类系数与边权值的搜索算法。 为达到动态规划中的最优搜索路径算法的想法,只能在搜索过程中的每一步达到局部最优。在包含节点的聚类系数和其相连的边的权值情况下,假定网络中有且只有自己的邻居节点信息,MCD 搜索算法如下。

(1)初始阶段先任意选择一对源节点s和目标节点,且将源节点s赋上值给s0。

(2)节点s0在选择下一个相邻节点时确认是否有目标节点t;如果存在,则搜索结束;否则转第3 步。

(3)s0确认相邻节点中是否存在节点d1(d1∈M)。 如果有此节点,则把携带的信息传递给d1,然后把d1的值赋给节点s0;否则根据第2 种规则进行选择。

(4)重复2 和3 的步骤,直到找到目标节点t为止。 当∂处于在0 ≤∂≤1 时,节点的聚类系数和边权值都相对较小的点才是要找的节点。

3 仿真实验

图1 搜索代价与网络规模的关系

由上图可知,在BBV 网络中,LBC 搜索策略与DS搜索策略明显劣于MCD 搜索策略。 MCD 搜索算法有效地结合了LBC 搜索策略的优势,并融合了节点聚类系数及边权值对网络的影响,提高搜索效率。 在局部信息的搜索代价上,MCD 搜索算法也优于LBC 搜索策略。 可得出结论,在加权非均匀网络中,要利用边权值的搜索算法才能更高效地提高搜索效率。

仿真2,该实验对比3 种搜索策略的搜索时间(在不同网络规模中)。 在仿真中,搜索时间用搜索步数替换,假定每一步的耗时都相同(t),搜索时间T=step×t(步数用step 表示)。 BBV 模型利用r=2 来模拟网络,实验结果如图2 所示。

由图2 可以看出,网络中LBC 和 MCD 搜索时间明显要优于DS 所用时间。 MCD 搜索策略BBV 网络的特点,很大程度上运用了hub 节点的高链路负载的特点,由于BBV 网络服从幂率分布,各边的权值分布不均等,这样就高效率地避免了网络拥塞,减少了搜索时间和搜索步数。

图2 搜索时间与网络规模的关系

从图3 可以发现,∂值取极大和极小,对应的搜索时间都偏大。 因此,在MCD 搜索算法中,MCD 搜索策略的搜索时间随着∂值的增大或减小而逐渐增大,且在∂值取中间值的时候搜索时间最小。 因此,参数∂的选择相当关键,算法中聚类系数和边权值都会由于此参数的变化而变化。

图3 不同∂值时的搜索时间

4 结语

本文在BBV 网络性质的基础上提出了MCD 搜索算法,此算法综合了聚类系数和边权值这两个加权网络中重要的参数对搜索效率的影响,在搜索时间和搜索代价上都要强于DS 算法和LBC 算法,且MCD 算法在寻找下一节点时所需要的局部信息量也要小于LBC算法。 因此,在BBV 网络中,边权值的大小对于节点的搜索效率有着很大的影响,结合节点聚类系数和边权值的搜索策略的效率相对较高。 本文对于生成的BBV网络的边权没有采取任何限制,考虑到在现实的网络里,边权重不可能无休止地增加,所以将来会在考虑节点强度的基础上重点考虑网络中边权重的限制,使BBV 网络模型更加接近真实世界,符合真实网络的特点。