Community Based Node Betweenness Centrality Updating Algorithms in Dynamic Networks
Author:
Affiliation:

Clc Number:

TP311

Fund Project:

National Natural Science Foundation of China (61373023);Intelligent Manufacturing Comprehensive Standardization and New Pattern Application Project of Ministry of Industry and Information Technology

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    With the rapid development of Internet technology, social networks show a trend of explosive growth. As the traditional analysis on static networks becomes more and more difficult to achieve satisfactory results, dynamic network analysis has turned into a research hotspot in the field of social network data management. Node betweenness centrality measures the ability of a node to control the shortest paths between other nodes in the graph, which is useful for mining important nodes in social networks. However, the efficiency will be low if the betweenness centrality of all nodes needs to be calculated each time while the graph structure changes frequently. To address the difficult problem of computing node 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, the node pairs which are not affected during the dynamically updating process can be quickly filtered out, thus greatly improving the updating efficiency of node betweenness centrality. Experimental results conducted on real-world datasets and synthetic datasets show the effectiveness of the proposed algorithms.

    Reference
    Related
    Cited by
Get Citation

钱珺,王朝坤,郭高扬.基于社区的动态网络节点介数中心度更新算法.软件学报,2018,29(3):853-868

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:August 07,2017
  • Revised:September 05,2017
  • Adopted:
  • Online: December 05,2017
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063