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

钱珺(1993-),男,江苏泰州人,硕士生,主要研究领域为社交网络,社区发现;郭高扬(1994-),男,博士生,主要研究领域为社交网络,深度学习;王朝坤(1976-),男,博士,副教授,博士生导师,CCF专业会员,主要研究领域为图和社交数据管理,音乐计算,大数据系统.

通讯作者:

王朝坤,E-mail:chaokun@tsinghua.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(61373023);工业和信息化部智能制造综合标准化与新模式应用项目


Community Based Node Betweenness Centrality Updating Algorithms in Dynamic Networks
Author:
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

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [31]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

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

    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.

    参考文献
    [1] Merrer EL, Tredan G. Centralities:Capturing the fuzzy notion of importance in social graphs. In:Proc. of the European Conf. on Computer Systems. 2009. 33-38.[doi:10.1145/1578002.1578008]
    [2] Bader DA, Kintali S, Madduri K, Mihail M. Approximating betweenness centrality. In:Proc. of the Workshop on Algorithms and Models for the Web Graph. 2007. 124-137.[doi:10.1007/978-3-540-77004-6_10]
    [3] Brandes U. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 2001,25(2):163-177.[doi:10.1080/0022250X.2001.9990249]
    [4] Sariyüce AE, Saule E, Kaya K, Çatalyürek ÜV. Shattering and compressing networks for centrality analysis. In:Proc. of the Computer Science. 2012..
    [5] Lee MJ, Lee J, Park JY, Choi RH, Chung CW. QUBE:A quick algorithm for updating betweenness centrality. In:Proc. of the Int'l Conf. on World Wide Web. ACM Press, 2012. 351-360.[doi:10.1145/2187836.2187884]
    [6] Lee MJ, Choi S, Chung CW. Efficient algorithms for updating betweenness centrality in fully dynamic graphs. In:Proc. of the Information Sciences. 2016. 278-296.[doi:10.1016/j.ins.2015.07.053]
    [7] Brandes U, Pich C. Centrality estimation in large networks. Int'l Journal of Bifurcation and Chaos, 2007,17(07):2303-2318.[doi:10.1142/S0218127407018403]
    [8] Geisberger R, Sanders P, Schultes D. Better approximation of betweenness centrality. In:Proc. of the Algorithm Engineering and Experimentation. 2008. 90-100.[doi:10.1137/1.9781611972887.9]
    [9] Girvan M, Newman ME. Community structure in social and biological networks. Proc. of the National Academy of Sciences of the United States of America, 2002,99(12):7821-7826.[doi:10.1073/pnas.122653799]
    [10] Huang FL, Zhang SC, Zhu XF. Discovering network community based on multi-objective optimization. Ruan Jian Xue Bao/Journal of Software, 2013,24(9):2062-2077(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4400.htm[doi:10.3724/SP.J.1001.2013.04400]
    [11] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks. Proc. of the National Academy of Sciences of the United States of America, 2004,101(9):2658.[doi:10.1073/pnas.0400054101]
    [12] Newman ME. Modularity and community structure in networks. Proc. of the National Academy of Sciences of the United States of America, 2006,103(23):8577-8382.[doi:10.1073/pnas.0601602103]
    [13] Newman ME. Fast algorithm for detecting community structure in networks. Physical Review E, 2004,69(6).[doi:10.1103/Phys RevE.69.066133]
    [14] Clauset A, Newman ME, Moore C. Finding community structure in very large networks. Physical Review E, 2004,70(6).[doi:10.1103/PhysRevE.70.066111]
    [15] Raghavan UN, Albert R, Kumara SR. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007,76(3).[doi:10.1103/PhysRevE.76.036106]
    [16] Leung IX, Hui P, Lio P, Crowcroft J. Towards real-time community detection in large networks. Physical Review E, 2009,79(6).[doi:10.1103/PhysRevE.79.066107]
    [17] Chen J, Saad Y. Dense subgraph extraction with application to community detection. IEEE Trans. on Knowledge and Data Engineering, 2012,24(7):1216-1230.[doi:10.1109/TKDE.2010.271]
    [18] Huang J, Sun H, Song Q, Deng H, Han J. Revealing density-based clustering structure from the core-connected tree of a network. IEEE Trans. on Knowledge and Data Engineering, 2013,25(8):1876-1889.[doi:10.1109/TKDE.2012.100]
    [19] Perozzi B, Alrfou R, Skiena S. DeepWalk:Online learning of social representations. In:Proc. of the Knowledge Discovery and Data Mining. 2014. 701-710.[doi:10.1145/2623330.2623732]
    [20] Shang JW, Wang CK, Xin X, Ying X. Community detection algorithm based on deep sparse autoencoder. Ruan Jian Xue Bao/Journal of Software, 2017,28(3):648-662(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5165.htm[doi:10. 13328/j.cnki.jos.005165]
    [21] Gong M, Li G, Wang Z, Ma L, Tian D. An efficient shortest path approach for social networks based on community structure. CAAI Trans. on Intelligence Technology, 2016,1(1):114-123.[doi:10.1016/j.trit.2016.03.011]
    [22] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. The MIT Press, 2001.
    [23] Erdős P, Rényi A. On random graphs I. Publicationes Mathematicae, 1959,6:290-297.
    [24] Watts DJ, Strogatz SH. Collective dynamics of ‘small-world’ networks. Nature, 1998,393(6684):440-442.[doi:10.1038/30918]
    [25] Barabasi A, Albert R. Emergence of scaling in random networks. Science, 1999,286(5439):509-512.[doi:10.1126/science.286. 5439.509]
    [26] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E, 2008, 78(4).[doi:10.1103/PhysRevE.78.046110]
    [27] SNAP datasets. http://snap.stanford.edu/data
    [28] Newman ME, Girvan M. Finding and evaluating community structure in networks. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004,69(2):26-113.[doi:10.1103/PhysRevE.78.046110]
    附中文参考文献:
    [10] 黄发良,张师超,朱晓峰.基于多目标优化的网络社区发现方法.软件学报,2013,24(9):2062-2077. http://www.jos.org.cn/1000-9825/4400.htm[doi:10.3724/SP.J.1001.2013.04400]
    [20] 尚敬文,王朝坤,辛欣,应翔.基于深度稀疏自动编码器的社区发现算法.软件学报,2017,28(3):648-662. http://www.jos.org.cn/1000-9825/5165.htm[doi:10.13328/j.cnki.jos.005165]
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:5071
  • 下载次数: 7836
  • HTML阅读次数: 3772
  • 引用次数: 0
历史
  • 收稿日期:2017-08-07
  • 最后修改日期:2017-09-05
  • 在线发布日期: 2017-12-05
文章二维码
您是第19727649位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号