- 1 -
结合最大度与最小聚类系数的复杂网络搜
索策略研究
冯立雪，于双元*
（北京交通大学计算机与信息技术学院，北京 100044） 5
摘要：实际的复杂网络中同时存在多种拓扑特征的现象非常普遍，本文就从兼顾无标度和小
世界特性的角度出发，对局部搜索策略进行了深入的分析、研究和改进。通过分析最大度搜
索策略在幂律指数大于 的无标度网络中搜索效果不佳的原因，借助最大一最小度搜索策
略的思想，提出和设计了结合最大度与最小聚类系数的复杂网络搜索策略。该策略实现了由
最大度搜索策略向最小聚类系数搜索策略的过渡，不仅在无标度网络中效果良好，而且在高10
聚类系数的复杂网络中也有着明显的优势。本文使用具有不同复杂网络拓扑特征的数据集验
证了该策略的正确性和有效性。
关键词：复杂网络；最大度；最小聚类系数；搜索策略
中图分类号：TP393
15
Complex network search strategy combined with Max
degree and Min clustering coefficient
FENG Lixue, YU SHuangyuan
(Beijing Jiaotong University, Beijing 100044)
Abstract: Real complex network generally has a variety of topological characteristics. This paper 20
takes into account the scale-free and small world properties, conducted in-depth analysis, research
and improvement of the local search strategies. By means of the defect causes of high degree
seeking and the max-min degree search strategy, designed the complex network search strategy
combined with Max degree and Min clustering coefficient in this paper. The search strategy
achieved the maximum degree search strategy to the minimum clustering coefficient search 25
strategy, would apply to scale-free network and the complex network with high clustering
coefficient. Used certain data sets with the various complex network topological characteristics,
verify the correctness and validity of the complex network search strategy.
Keywords: complex network; maximum degree; minimum clustering coefficient; search strategy
30
0 引言
复杂网络中的搜索问题涉及网络中指定文件或数据的寻找及网络节点间最短路径的确
定，具有重要的现实意义和较高的研究价值。复杂网络搜索策略通常可用一个消息传递的过
程来描述，多采用局部搜索方式，其性能将直接影响到能否快速有效地搜索到所需要的目标，
以及找到目标所花费的代价能否被接受。当前的基本复杂网络搜索策略有如下三种：广度优35
先搜索策略(BFS)，随机游走搜索策略(RW)和最大度搜索策略(DS) [1、2、3]。BFS 策略实现起
来最为简单，可迅速发现目标，但是这样的处理方式会在网络中产生大量的查询消息流量，
很容易造成网络流量的急剧增加，从而导致网络拥塞。同 BFS 策略相比，RW 策略的搜索
步数要大得多，但由于 RW 策略中每一步只向前传递一个查询消息，因此大大减少了网络
中的查询消息流量。DS策略则可在这二者之间取得折中，即拥有相对小的搜索步数，达到40
迅速发现目标节点的目的，同时也在一定程度上减少了搜索过程中的查询消息流量，起到了
抑制网络拥塞的作用。但研究发现，最大度搜索策略只适用于非均匀网络，而不适用于均匀
- 2 -
网络。文献[4]详细分析了最大度搜索策略这一缺陷的主要成因，并在此基础上对该策略进行
了改进和扩展，但该分析过程仅考虑了实际复杂网络的无标度特性，而忽略了小世界特性，
也没有引入其他刻画网络特征的参数，例如聚类系数。 45
本文主要从实际复杂网络的无标度和小世界特性出发，对最大度搜索策略进行了分析与
改进，同时参考了最大度搜索策略在均匀网络中搜索效果不佳的成因，适当地加入了聚类系
数这一复杂网络基本参数，提出了结合最大度与最小聚类系数的复杂网络搜索策略。该策略
可不受网络度分布的限制，同时兼顾实际网络的聚类情况，进而能够在无标度和小世界网络
中都取得良好的搜索效果。 50
1 最大度搜索策略缺陷的成因
最大度搜索策略具有很强的局部搜索优势，但不适用于均匀网络的缺陷一直阻碍着其搜
索效果的提高。文献[4、5]中指出，最大度搜索策略在幂律指数 >γ 的无标度网络中的搜
索效果不够理想，若要最大度搜索策略达到理想的搜索效果，整个搜索过程就须要符合“按
度序列搜索”的设想。按度序列搜索是指：复杂网络搜索过程的每一步中，当前节点都选择55
自己的度最大的邻居节点将查询传递过去，迭代执行后可迅速到达整个复杂网络中度最大的
节点，而一旦访问过该网络中度最大的节点之后，相关路径就将被程序限制，当前节点将选
择自己的度次大的邻居节点将查询传递过去，以此类推。文献[4、5]认为在幂律指数γ不同的
无标度网络中，计算节点的度与其最大度邻居节点的度之间的比值大于 1时，均可形成度序
列。 60
图 1 无标度网络中最大度邻居节点度与节点度的比值曲线图[4、5]
The expected degree of the richest neighbor of a node in power-law networks
如图 1所示，最大度邻居节点度与节点度的比值曲线和 1=y 的交点，就是幂律指数γ65
不同的无标度网络在整个搜索过程中能够形成有效的度序列的临界值。但对于幂律指数
>γ 的无标度网络而言，大部分节点的度都不符合该临界值，此时采用最大度搜索策略
也就达不到理想的搜索效果，而这也就是最大度搜索策略缺陷的成因之一。
2 结合最大度与最小聚类系数的复杂网络搜索策略设计
策略描述 70
由最大度搜索策略的缺陷成因的分析过程可知，存在一分界值 k0，可使得 k0范围内的
- 3 -
节点的搜索过程符合“按度序列搜索”的设想，保证最大度搜索策略的高效。基于分界值
k0，本文设计提出了一种结合最大度与最小聚类系数的复杂网络搜索策略，描述如下：
（1）初始时选取源节点 s与目标节点 t。
（2）从源节点 s 出发，判断自己的邻居节点中有无目标节点。若有，则中止搜索；若75
无，则转向步骤（3）。
（3）记 ks为源节点 s的度，ccs为源节点 s的聚类系数， ( )sN 为源节点 s的邻居节点集。
若 0kks < ，则选择节点 i作为搜索的下一跳节点，其中 ( )sNi∈ 且满足 ( )( )sNji kk ∈= max ，
该过程等同于最大度搜索策略；若 0kks ≥ ，则选择节点 i 作为搜索的下一跳节点，其中
( )sNi∈ 且满足 ( )( )sNji cccc ∈= min ，该过程等同于最小聚类系数搜索策略。在确定好下一80
跳节点 i之后，转向步骤（2）。
（4）相关规定：可以多次访问同一个节点，但是同一条边只可被访问一次。如果与当
前节点相连的所有的边都已经被访问过，则返回到上一个节点继续搜索。
（5）重复步骤（2）和步骤（3），直到当前节点为目标节点 t 的任一个邻居节点，目
标节点 t即被找到，搜索完成。 85
该策略将复杂网络中的节点根据度的大小分成了两部分，并对这两部分节点分别采用各
自适合的策略进行搜索。当节点 s 的度 0kks < 时，符合按度序列搜索的前提条件，采用最
大度搜索策略效果显著，因此在搜索过程中对于这一部分节点沿用最大度搜索策略；当节点
s 的度 0kks ≥ 时，不符合按度序列搜索的前提条件，采用最大度搜索策略效果不佳，因此
在搜索过程中对于这一部分节点实行最小聚类系数搜索策略。 90
策略分析
本文之所以在节点 s 的度 0kks ≥ 时采用最小聚类系数搜索策略，是兼顾复杂网络的小
世界特性的表现。单一节点的聚类系数可表征该节点邻居之间连接的紧密程度。聚类系数越
小，说明当前节点的各个邻居节点之间连接的边数越少，这在一定程度上使得搜索策略在本
地的搜索时间相对变短，整个搜索过程将很快地转移到另外的节点聚集区域。而聚类系数越95
大，说明当前节点的各个邻居节点之间连接的边数越多，这在一定程度上增大了无记忆搜索
策略在本地进行重复搜索的可能，造成搜索效率的降低。研究表明，大部分搜索的源节点 s
和目标节点 t都处于不同的节点聚集区域，因此，能够实现快速转移搜索区域的复杂网络搜
索策略将在一定程度上增加找到目标节点 t的概率，有效提高搜索效率。
实际复杂网络大多兼而具有无标度和小世界特性，但研究人员出于单一分析准确性的考100
虑而分别提出了无标度网络模型和小世界网络模型，进而迫使各种复杂网络搜索策略依据不
同的复杂网络拓扑模型进行改进和效果分析。本文提出的结合最大度与最小聚类系数的复杂
网络搜索策略主要兼顾了实际复杂网络的无标度特征和聚类情况，既利用了最大度搜索策略
在一定幂律指数条件下的无标度网络中效果明显的优势，又预见了最大度搜索策略效果不佳
的位置，并及时将搜索策略的侧重点调整为复杂网络的小世界特性，结合了最小聚类系数搜105
索策略在小世界网络中效果明显的优势，实现了由最大度搜索策略向最小聚类系数搜索策略
的过渡，进而在无标度和小世界网络中取得良好的搜索效果。
- 4 -
中国科技论文在线
3 仿真结果
数据集
本文在仿真测试时使用了四个经研究人员调查得到的实际复杂网络数据集 karate、110
dolphins、football和 power [6]，可作为不同类型的复杂网络的代表，而通过分析和处理数据
集这一过程得到表 1。如表 1所示，为这四种实际复杂网络数据集的各项基本参数。
表 1 四种实际复杂网络数据集
Four kinds of real complex network data sets 115
分界值 k0的选取对搜索效果的影响
分界值 k0 作为该策略中判断节点是否符合按度序列搜索的前提条件的主要依据，辅助
程序实现了由最大度搜索策略向最小聚类系数搜索策略的过渡，在很大程度上影响着该策略120
在实际复杂网络中的搜索效果和表现。因此，本文在数据集 karate、dolphins、football和 power
上，使用分界值 k0 可调节的结合最大度与最小聚类系数的复杂网络搜索策略进行搜索，即
令 20151311109750 、、、、、、、=k ，对于各个固定的分界值 k0，程序将记录相应搜索策略的平均
搜索步数和平均搜索时间，并以此为指标进行搜索效果的分析与评价，从而得到分界值 k0
的选取与该策略搜索效果之间的影响。 125
如图 2 所示，为在不同数据集上，具有不同分界值 k0的结合最大度与最小聚类系数的
复杂网络搜索策略的搜索效果。其中，分界值 k0 与平均搜索步数的关系由点线图表示，使
用 x轴和右侧 y轴；分界值 k0与平均搜索时间的关系由柱状图表示，使用 x轴和左侧 y轴，
单位 ms，即 106ns。
130
(A)采用数据集 karate
(B)采用数据集 dolphins
- 5 -
中国科技论文在线
(C)采用数据集 football 135
(D)采用数据集 power
图 2 分界值 k0对搜索策略的影响
The dividing value's influence on the search strategy
140
如图 2(A)所示可知，结合最大度与最小聚类系数的复杂网络搜索策略在分界值
1090 、=k 处有最小的平均搜索步数，在 100 =k 处有最短的平均搜索时间。根据该策略的
基本设计思想可知，分界值 k0 越小，实际复杂网络中就有越多的节点会在当前搜索过程中
选择聚类系数最小的邻居节点将查询传递过去，此时的结合最大度与最小聚类系数的复杂网
络搜索策略更接近于最小聚类系数搜索策略；相反，分界值 k0 越大，就有越多的节点会选145
择度最大的邻居节点，此时的结合最大度与最小聚类系数的复杂网络搜索策略更接近于最大
度搜索策略。图 2(A)前半部分的平均搜索时间的柱状图在整体上要低于后半部分，而 karate
数据集又具有较高的平均聚类系数，因而也侧面验证了最小聚类系数搜索策略更适用于高平
均聚类系数的复杂网络这个结论[7]。
如图 2(B)所示可知，结合最大度与最小聚类系数的复杂网络搜索策略在分界值 100 =k150
处有最小的平均搜索步数和最短的平均搜索时间。图 2(B)前半部分的平均搜索时间的柱状
图在整体上要高于后半部分，而平均搜索步数的点线图的前半部分也明显高于后半部分，这
主要是因为 dolphins数据集的平均聚类系数不高，最小聚类系数搜索策略的表现不佳。
如图 2(C)和图 2(C)所示可知，结合最大度与最小聚类系数的复杂网络搜索策略在分界
值 100 =k 处均有最小的平均搜索步数和最短的平均搜索时间。 155
实际复杂网络中的搜索效果
由 节可知，在本文使用的这些实际复杂网络数据集上，分界值 100 =k 的结合最大
度与最小聚类系数的复杂网络搜索策略可得到最优的搜索效果，因此，将分界值 k0 设置为
10。另外，本节还分别实现了最大度搜索策略、最小聚类系数搜索策略、最大—最小度搜索
策略[4]，通过对相同的数据集使用不同的复杂网络搜索策略，可更为准确和全面地分析与评160
价各种搜索策略的优劣。如图 3和图 4所示，为在不同数据集上，不同搜索策略的平均搜索
步数和平均搜索时间。
- 6 -
中国科技论文在线
图 3 平均搜索步数的比较
Comparison of average search steps 165
如图 3所示可知，于 karate、dolphins、football和 power这四个实际复杂网络数据集而
言，本文提出的搜索策略均比最大—最小度搜索策略[4]有着更小的平均搜索步数，说明该策
略通过更少的中间节点就可查找到目的节点，相应的查询消息流量也更少。由数据集 karate
到数据集 power，测试用实际复杂网络的规模逐渐增大，各个搜索策略的平均搜索步数也相170
应增大，而根据图 3中表示平均搜索步数增长趋势的直线和虚线可知，本文提出的搜索策略
比最大—最小度搜索策略增长缓慢，说明该策略确实在平均搜索步数方面优于最大—最小度
搜索策略，并且优势还随着网络规模的增大而越加明显。
另外，karate 和 football 是两个高平均聚类系数的数据集，最小聚类系数搜索策略在其
上的平均搜索步数是四个搜索策略中最小的，本文提出的搜索策略的平均搜索步数与最小聚175
类系数搜索策略更为接近；而数据集 dolphins和 power的平均聚类系数并不高，此时最大度
搜索策略的平均搜索步数基本上是最小的，本文提出的搜索策略的平均搜索步数又与最大度
搜索策略更为接近。这说明结合最大度与最小聚类系数的复杂网络搜索策略兼顾了复杂网络
的无标度和小世界特性，在高平均聚类系数的复杂网络中能够表现出最小聚类系数搜索策略
的优势，而在低平均聚类系数的复杂网络中又能够表现出最大度搜索策略的优势，实现了最180
小聚类系数搜索策略与最大度搜索策略之间的过渡。
图 4 平均搜索时间的比较
Comparison of average search time
- 7 -
中国科技论文在线
如图 4所示可知，在平均搜索时间方面也可得到类似图 3的结果。 185
4 结论与进一步研究工作
最大度搜索策略在幂律指数 >γ 的无标度网络中的搜索效果不够理想，因此，基于
分界值 k0，本文提出了结合最大度与最小聚类系数的复杂网络搜索策略。该策略主要兼顾了
实际复杂网络的无标度特征和聚类情况，实现了由最大度搜索策略向最小聚类系数搜索策略
的过渡，在无标度和小世界网络中都可取得良好的搜索效果。仿真得出，分界值 k0 的选取190
与其在实际复杂网络中的搜索效果有一定程度的影响，分界值 k0 越小，该策略就越接近于
最小聚类系数搜索策略，分界值 k0 越大，该策略就越接近于最大度搜索策略。当且仅当分
界值 100 =k 时，本文提出的搜索策略可得到最优的搜索效果，优于最大—最小度搜索策略
[4]，且该优势还随着网络规模的增大而越加明显。不过，本文在理论分析工作方面还有待进
一步的完善，分界值 k0 的确定仍需要考证，数据集的使用也有着一定的局限性，因而，设195
计出在多种类型的实际复杂网络中都更为行之有效的局部搜索策略是本文进一步的研究工
作。
[参考文献] (References)
[1] Jon Kleinberg. Complex Networks and Decentralized Search Algorithms. 200
[2] Adamic L A., Lukose R M., Puniyani A R, etc.. Search in power-law networks. Phys. Rev. E, 64: 046135. 2001.
[3] 汪小帆，李翔，陈关荣. 复杂网络理论及其应用. 清华大学出版社. 2006
[4] 王天骄，汪小帆. 无标度和加权网络的搜索问题研究. 2007
[5] Ozgur Simsek, David Jensen. Decentralized search in networks using homophily and degree disparity. 205
Nineteenth International Joint Conference on Artificial Intelligence. 2005
[6] 数据集取自
[7] 吴艾，刘心松，皮建勇，刘克剑. 聚集度相关的网络节点搜索算法.
210
