基于社区的动态网络节点介数中心度更新算法

随着互联网技术的迅猛发展，社会网络呈现出爆炸增长的趋势，传统的静态网络分析方法越来越难以达到令人满意的效果，于是对网络进行动态分析就成为社会网数据管理领域的一个研究热点。节点介数中心度衡量的是一个节点对图中其他点对最短路径的控制能力，有利于挖掘社会网络中的重要节点。在图结构频繁变化的场合，若每次变化后都重新计算整个图中所有节点的介数中心度，则效率将会很低。针对动态网络中节点介数中心度计算困难的问题，本文提出一种基于社区的节点介数中心度更新算法。通过维护社区与社区、社区与节点的最短距离集合，快速过滤掉那些在网络动态更新中不受影响的点对，从而大大提高节点介数中心度的更新效率。真实数据集和合成数据集上的实验结果表明了论文所提算法的有效性。

Community Based Node Betweenness Centrality Updating Algorithms in Dynamic Networks

With the rapid development of Internet technology, social networks show a trend of explosive growth. The traditional analysis on static networks is more and more difficult to achieve satisfactory results. Then dynamic network analysis has become a research hotspot in the field of social network data management. Node Betweenness Centrality measures the ability of a node to control the shortest pathsbetween other nodes in the graph, which is useful for mining important nodes in social networks. However, the efficiency will be low if we recalculate the betweenness centrality of all nodes each time, when the graph structure changes frequently. To addressthe difficult problem ofthe computation ofnode betweenness centrality in dynamic networks, a community based betweenness centrality updating algorithm is proposed in this paper. By maintaining the shortest distance sets between communities and communities, as well as between communities and nodes, we could quickly filter out the node pairs which are not affected during the dynamically updating process, and thus greatly improve the updating efficiency of node betweenness centrality. Experimental resultsconducted on real-world datasets and synthetic datasets show the effectiveness of the proposed algorithms.