基于结构稳定性校准的在线式社区识别

杨海陆; 张健沛; 杨静

doi:10.3724/SP.J.1004.2014.02151

基于结构稳定性校准的在线式社区识别

doi: 10.3724/SP.J.1004.2014.02151

1.
哈尔滨工程大学计算机科学与技术学院哈尔滨 150001

基金项目:

国家自然科学基金(61073041, 61073043, 61202274, 61370083, 61402126), 高等学校博士学科点专项科研基金(20112304110011, 20122304110012) 资助

详细信息

作者简介:
杨海陆哈尔滨工程大学计算机科学与技术学院博士研究生. 主要研究方向为数据挖掘, 社会计算和社会网络安全.E-mail: yanghailu@hrbeu.edu.cn

计量
- 文章访问数: 1210
- HTML全文浏览量: 64
- PDF下载量: 1129
- 被引次数: 0
出版历程
- 收稿日期: 2013-11-18
- 修回日期: 2014-02-20
- 刊出日期: 2014-10-20

Identifying Online Communities by Calibrating Structure Stability

1.
College of Computer Science and Technology, Harbin Engineering University, Harbin 150001

Funds:

Supported by National Natural Science Foundation of China (61073041, 61073043, 61202274, 61370083, 61402126), Specialized Research Fund for the Doctoral Program of Higher Education (20112304110011, 20122304110012)

摘要

摘要: 本文探讨在线社会网络的社区识别问题, 重点研究网络演变特性对社区结构产生的影响. 首先基于节点的邻域倾向性提出社区稳定性的概念并给出稳定社区的快速识别算法, 然后设计了一种基于事件的社区稳定性校准算法以此识别新网络的社区结构. 由于算法的局部搜索策略, 该方法无需在新时间片段重复执行, 并且可以在无参数条件下识别加权网络中具有任意形状的社区结构. 在人工合成网络和真实网络上的实验结果验证了算法的可行性和有效性.
- 在线社会网络 /
- 重叠社区识别 /
- 社区稳定性 /
- 校准策略
Abstract: This paper investigates into the problem of identifying communities in online social networks. It focuses on the effect of evolution behavior of network on the community structure. In the work, the notion of community stability and a high-speed algorithm for mining stable community are first proposed according to the tendency between nodes and its neighborhood. Then a community stability calibrating method is designed, which takes advantage of the evolution event of network to recognize the new snapshot communities. Thanks to the local search strategy of the algorithm, the new method does not require to execute repeatedly in new snapshot and is able to recognize community structures with arbitrary shapes under the condition of no input parameters. Finally, competitive experiments on both synthesized and real-world social networks demonstrate the effectiveness and efficiency of the proposed algorithm.
- Online social networks /
- overlapping community detection /
- community stability /
- calibrating strategy

HTML全文

参考文献(23)

[1]	Hopcroft J, Khan O, Kulis B, Selman B. Tracking evolving communities in large linked networks. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(1): 5249-5253
[2]	[2] Asur S, Parthasarathy S, Ucar D. An event-based framework for characterizing the evolutionary behavior of interaction graphs. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2007. 913-921
[3]	[3] Sun J, Faloutsos C, Papadimitriou S, Yu P S. Graphscope: parameter-free mining of large time-evolving graphs. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2007. 687-696
[4]	[4] Palla G, Barabsi A L, Vicsek T. Quantifying social group evolution. Nature, 2007, 446(7136): 664-667
[5]	Wu Bin, Wang Bai, Yang Sheng-Qi. Framework for tracking the event-based evolution in social networks. Journal of Software, 2011, 22(7): 1488-1502(吴斌, 王柏, 杨胜琦. 基于事件的社会网络演化分析框架. 软件学报, 2011, 22(7): 1488-1502)
[6]	[6] Lin Y R, Chi Y, Zhu S H, Sundaram H, Tseng B L. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. In: Proceedings of the 17th International Conference on World Wide Web. Beijing, China: ACM, 2008. 685-694
[7]	[7] Tang L, Liu H, Zhang J P. Identifying evolving groups in dynamic multimode networks. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(1): 72-85
[8]	[8] Gauvin L, Panisson A, Cattuto C. Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach. Plos One, 2014, 9(1): e86028
[9]	[9] Cazabet R, Amblard F, Hanachi C. Detection of overlapping communities in dynamical social networks. In: Proceedings of the 2010 IEEE Second International Conference on Social Computing. Minneapolis, Minnesota, USA: IEEE, 2010. 309-314
[10]	Prez-Surez A, Martnez-Trinidad J F, Carrasco-Ochoa J A, Medina-Pagola J E. An algorithm based on density and compactness for dynamic overlapping clustering. Pattern Recognition, 2013, 46(11): 3040-3055
[11]	Lancichinetti A, Radicchi F, Ramasco J J, Fortunato S. Finding statistically significant communities in networks. Plos One, 2011, 6(4): e18961
[12]	Lin Wang-Qun, Deng Lei, Ding Zhao-Yun, Wu Quan-Yuan, Jia Yan, Zhou Bin. Hierarchical dynamic community detection by parallel computing. Chinese Journal of Computers, 2012, 35(8): 1712-1725(林旺群, 邓镭, 丁兆云, 吴泉源, 贾焰, 周斌. 一种新型的层次化动态社区并行计算方法. 计算机学报, 2012, 35(8): 1712-1725)
[13]	Dinh T N, Nguyen N P, Thai M T. An adaptive approximation algorithm for community detection in dynamic scale-free networks. In: Proceedings of the 32nd IEEE International Conference on Computer Communications. Piscataway, NJ, USA: IEEE, 2013. 55-59
[14]	Fortunato S. Community detection in graphs. Physics Reports, 2010, 486(3): 75-174
[15]	Wang G, Zhao Y, Shi X, Yu P S. Magnet community identification on social networks. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2012. 588-596
[16]	Newman M E J. Analysis of weighted networks. Physical Review E, 2004, 70(5): 056131
[17]	Liu Xu, Yi Dong-Yun. Complex network community detection by local similarity. Acta Automatica Sinica, 2011, 37(12): 1520-1529(刘旭, 易东云. 基于局部相似性的复杂网络社区发现方法. 自动化学报, 2011, 37(12): 1520-1529)
[18]	Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814-818
[19]	Yang Bo, Liu Jie, Liu Da-You. A random network ensemble model based generalized network community mining algorithm. Acta Automatica Sinica, 2012, 38(5): 812-822(杨博, 刘杰, 刘大有. 基于随机网络集成模型的广义网络社区挖掘算法. 自动化学报, 2012, 38(5): 812-822)
[20]	Zhang Xin-Meng, Jiang Sheng-Yi. Complex network community detection based on core graph incremental clustering. Acta Automatica Sinica, 2013, 39(7): 1117-1125(张新猛, 蒋盛益. 基于核心图增量聚类的复杂网络划分算法. 自动化学报, 2013, 39(7): 1117-1125)
[21]	Lee C, Reid F, McDaid A, Hurley N. Seeding for pervasively overlapping communities. Physical Review E, 2011, 86(3): 066107
[22]	Gregory S. Finding overlapping communities in networks by label propagation. New Journal of Physics, 2010, 12(10): 103018
[23]	Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 2009, 80(1): 016118