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

来源:用户上传      作者:曾成

　　摘要：基于BBV 网络，文章在对随机游走（Rand Walk，RW）策略、最大度搜索（High Degree Seeking，DS）和局部介数（Local Betweenness Centrality，LBC）等局部搜索策略进行对比研究的基础上，结合了搜索信息最小及局部中心 节点的思 想，提出一种结合节点聚类系数和边权值大小的搜索策略，即最小聚类系数最小距离（Minimum Clustering Coefficient and Distance，MCD）搜索策略。理论分析和仿真实验表明：在搜索代价、搜索时间及搜索覆盖率等方面，MCD 搜索策略都优于DS 策略和最大 LBC 搜索策略。
　　关键词：BBV 网络;最短路径;边权;搜索信息
　　0 引言
　　在很长一段时间里，搜索问题是复杂网络中比较 热门的一个研究课题，大部分学者将主要研究放在了无权网络上，也就是将现实中的网络抽象化，接着再将 其弱化为布尔网络来研究[1-4]。大量实验结果证明了网络节点之间连接关系的紧密程度是不一样的，并不 全都是布尔关系，人们把这类网络称为加权网络[5]。由此可知，研究加权网络中高效的搜索方法已变得很有意义，能将复杂网络的搜索问题具体地描述成信息之间的传递过程。常用的局部搜索策略有：随机游走（Rand Walk，RW）策 略和最 大 度 搜 索（HighDegree 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 ）下一步选择节点的概率定义为：
　　BBV 网络模型中每个节点之间的流量是用权值来表示的，如果节点之间流量过大，那么搜索的难度也会随之增加，由于以上原因，选择因子与权值成反比，则由Cij=w-ij 1。可以看出，如果加权网络中路径越短，那 么流量就越小，道路就越畅通。
　　邻近节点之间的集团性质是由该节点的聚类系数体现出来的，如果各个节点联系越紧凑，那么该顶点的聚类系数就会越高。加权网络集聚系数[13]是由Barrat和他的团队，根据无权网络集聚系数的基础上被定义的，加权网络集聚系数为：
　　由以上信息，并结合聚类系数与搜索信息，如果想要很快地找寻目标节点，只需要在搜索时把信息送达流量比较小、聚类系数比较小的邻居节点即可。
　　2算法设计
　　根据影响搜索算法的权值、借点聚类系数和BBV 网络的特点，提出了一种结合节点聚类系数与边权值的搜索算法。为达到动态规划中的最优搜索路径算法的想法，只能在搜索过程中的每一步达到局部最优。在包含节点的聚类系数和其相连的边的权值情况下，假定网络中有且只有自己的邻居节点信息，MCD 搜索算法如下。
　　（1）初始阶段先任意选择一对源节点s和目标节点，且将源节点s 赋上值给 s0。
　　（2）节点s0在选择下一个相邻节点时确认是否有目标节点t ;如果存在，则搜索结束;否则转第 3 步。
　　（3）s0确认相邻节点中是否存在节点d1（d1 ∈ M）。如果有此节点，则把携带的信息传递给 d1，然后 把 d1 的值赋给节点s0 ;否则根据第 2 种规则进行选择。
　　计算节点的概率公式
　　其中 ?为可调参数，且 0 ≤ ? ≤ 1，ci为节点的聚类系数，di为边权值，? 可以用来调节 ci和di在概率中的比重。在选择下一个节点d2时按依照此概率，并将信息传递 给此节点，进而将 d2 的值赋给节点s0。
　　（4）重复 2和3的步骤，直到找到目标节点t为止。当 ? 处于在0 ≤ ? ≤ 1 时，节点的聚类系数和边权 值都相对较小的点才是要找的节点。
　　3 仿真实验
　　由上图可知，在BBV 网络中，LBC 搜索策略与DS 搜索策略明显劣于MCD 搜索策略。MCD 搜索算法有效地结合了LBC 搜索策略的优势，并融合了节点聚类系数及边权值对网络的影响，提高搜索效率。在局部信息的搜索代价上，MCD 搜索算法也优于LBC 搜索策 略。可得出结论，在加权非均匀网络中，要利用边权值的搜索算法才能更高效地提高搜索效率。

nlc202208301125

转载注明来源:https://www.xzbu.com/8/view-15438751.htm