高壮良，吕雁飞，张鸿



基于Graphlab的网络图关键节点发现算法研究

高壮良1，吕雁飞2，张鸿2

（1. 北京航空航天大学计算机学院，北京 100191；2. 国家计算机网络应急技术处理协调中心，北京 100029）

针对桥接中心度的计算特点设计了一种分布式的网络图关键节点发现算法（DABC），并基于Graphlab进行了实现。算法具有良好的扩展性，由于能够利用集群的内存资源，算法能处理的图规模与集群的大小成正比，并且该算法利用并行处理大幅度提升了计算速度。实验表明，与传统的基于单机实现的关键节点发现算法相比，算法可以获得高达4倍的性能提升。

关键节点；桥接中心度；分布式算法；Graphlab

1 引言

网络图中的关键节点在图的组织和信息传播中起着枢纽作用，对图中关键节点进行标识和发现是图中的一个重要研究方向，有着丰富的应用场景和重要的应用价值。例如，社交网络成员中的关键节点通常具有更大的影响力或者更强的信息传播能力，找到社交网络中的关键节点可以分析甚至影响社交网络中的消息传播。在计算机网络拓扑中对关键节点进行保护可以提升整个网络的顽健性，反之对关键节点进行攻击会起到事半功倍的效果。此外，在反恐斗争中，关键节点研究也对重要恐怖分子的发现等[1]有着辅助作用。

识别网络图中关键节点的一类重要方法是计算图中节点的中心度，包括距离中心度、谱中心度和桥接中心度等。其中，桥接中心度是研究关键节点中常用的一种中心度度量，它可以用来衡量节点在网络图连通和信息传播中的重要程度。……