面向应急管理的大图重要节点中介度高效近似计算方法  

Efficient node betweenness approximation computation method for large graph in emergency management

作　　者：邓小龙[1] 李欲晓[2] 

机构地区：[1]北京邮电大学可信分布式计算与服务教育部重点实验室,北京100876 [2]北京邮电大学国际学院,北京100876

出　　处：《系统工程理论与实践》2015年第10期2531-2543,共13页Systems Engineering-Theory & Practice

基　　金：十二五国家科技支撑计划国家文化科技创新工程2013年备选项目(2013BAH43F01);国家重点基础研究发展计划973项目(2013CB329600);国家自然科学基金(91224008)

摘　　要：社交网络中的重要节点对于信息的传播效率有着至关重要的作用,也是近年来的研究热点问题.同时,随着新媒体时代手机、微博、微信等新兴媒介日益变快的信息传播速度,政府部门和企业已经逐渐认识到通过识别社交网络中的重要节点对于管理和控制社交网络中的信息传播,在面向应急的非常规突发事件数据获取与分析中,有着举足轻重的作用.新媒体时代也扩展了人们社会活动的信息容量与交换速度,以MapReduce为代表的分布式计算系统在应急管理的大规模社交网络数据分析中也变得越来越普遍.为了便于应急管理中的信息传播控制,针对应急管理中大规模社交网络图上重要节点识别的关键问题,本文提出了一种新颖的基于轴节点选择策略的大图重要节点中介度近似计算方法和原型系统,并通过模拟数据和真实数据(包含一个连续六个月的真实社交网络数据集)进行了验证.实验结果表明,该方法能非常有效地找出社交网络上的重要节点,对于应急管理中的信息传播控制有着重要的作用.Important node is vital for information spreading efficiency in social network, which has always been the hottest research field in recent years. At the same time, with the increased information spreading speed in our daily life such as cellphone, MicroBlog, WeChat and so on, the staffs of government and enterprise have found that it is necessary and important to manage and control the information spreading in social network of people by recognizing important node in data analysis of emergency accidents man- agement. Meanwhile, with the rapid increase of information in society activities recently, the distributed information system engineering such as MapReduce-based computation system has become more and more popular in large-scale social network data analysis in emergency case management. In this article, a novel effective and efficient node betweenness approximation pivot selection method for large-scale graph was proposed on MapReduce-based system for social network analysis （SNA）. Furthermore, it has been proved useful in four discrete network datasets and one continuous network dataset （six month call graph） in important node discovery for large graph from real telecom data in China to help deal with information spreading control in emergency case management with more efficiently.

关 键 词：应急管理 重要节点识别 MAPREDUCE 中介度 轴节点选择策略 近似计算 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]