基于Graphlab的网络图关键节点发现算法研究
关键节点发现是图分析中的一类重要问题,具有较强的理论价值与现实意义.桥接中心度是衡量网络图中节点重要性的一个常用指标.随着图规模的不断扩大,原有的基于单机实现的桥接中心度关键节点发现算法已很难满足需求.单机的内存大小限制了能够计算的图规模,而且单机的处理能力也影响了算法的计算速度.本文针对桥接中心度的计算特点设计了一种分布式的网络图关键节点发现算法(DABC),并基于Graphlab进行了实现.算法具有良好的扩展性,由于能够利用集群的内存资源,算法能处理的图规模与集群的大小成正比.并且算法利用并行处理大幅度提升了计算速度.实验表明,与传统的基于单机实现的关键节点发现算法相比,算法可以获得高达4倍的性能提升.
网络图 关键节点发现 桥接中心度 分布式算法 Graphlab框架
高壮良 吕雁飞 张鸿
北京航空航天大学 北京 100191 国家计算机网络应急技术处理协调中心 北京 100029
国内会议
武汉
中文
189-196
2015-05-26（万方平台首次上网日期，不代表论文的发表时间）