Community Tracking Algorithm Based on Similarity of Association Group Evolution
XU Bing1,2, ZHAO Yawei1, XU Yang, yuanxiang1,2
1.Big Data Analysis Technology Laboratory, University of Chinese Academy of Sciences, Beijing 100049, China; 2.AI Lab Beijing Knowlegene Data Technology Company Limited, Beijing 100027, China
Abstract：In large-scale complex networks, community structure is ubiquitous, and with the change of time, the community in the network is also changing. In order to track the changes of the community and associate the adjacent time groups to form the related groups, this paper proposes a comprehensive weighted evolutionary similarity to measure the similarity of the neighboring time groups. A method of extracting evolutionary path and generating evolutionary sequence by using "multi-part graph" is also proposed. Finally, the experimental results on a bank business data show that the algorithm is more accurate than using a single index similarity judgment.
徐兵, 赵亚伟, 徐杨远翔. 基于关联群演化相似度的社团追踪算法[J]. 复杂系统与复杂性科学, 2019, 16(1): 14-25.
XU Bing, ZHAO Yawei, XU Yangyuanxiang. Community Tracking Algorithm Based on Similarity of Association Group Evolution. Complex Systems and Complexity Science, 2019, 16(1): 14-25.
Gregory S. Ordered community structure in networks[J]. Physica A Statistical Mechanics & Its Applications, 2012, 391(8):27522763.
[2]
Xu K S, Hero A O. Dynamic stochastic blockmodels for time-tvolving social networks[J]. IEEE Journal of Selected Topics in Signal Processing, 2014, 8(4):552562.
[3]
Leventhal G E, Hill A L, Nowak M A, et al. Evolution and emergence of infectious diseases in theoretical and real-world networks[J]. Nature Communications, 2015, 6:6101.
[4]
王莉, 程学旗. 在线社会网络的动态社区发现及演化[J]. 计算机学报, 2015, 38(2):219237.Wang Li, Cheng Xueqi. Dynamic community in online social networks[J]. Chinese Journal of Computers, 2015, 38:219237.
[5]
王莉, 程苏琦, 沈华伟,等. 在线社会网络共演化的结构推断与预测[J]. 计算机研究与发展, 2013, 50(12):24922503.Wang Li,Cheng Suqi,Shen Huawei, et al. Structure inference and prediction in the co-evolution of social networks[J]. Journal of Computer Research & Development, 2013, 50(12):24922503.
[6]
Ranshous S, Shen S, Koutra D, et al. Anomaly detection in dynamic networks: a survey[J]. Wiley Interdisciplinary Reviews Computational Statistics, 2015, 7(3):223247.
[7]
Harenberg S, Bello G, Gjeltema L, et al. Community detection in large-scale networks: a survey and empirical evaluation[J]. Wiley Interdisciplinary Reviews Computational Statistics, 2015, 6(6):426439.
[8]
徐兵,郭渊博,叶子维,等.基于图分析和支持向量机的企业网异常用户检测[J]. 计算机应用, 2018, 38(2):357362.Xu Bing,Guo Yuanbo,Ye Ziwei,et al. Abnormal user detection in enterprise network based on graph analysis and support vector machine[J]. Journal of Computer Applications, 2018, 38(2):357362.
[9]
Shao J, Han Z, Yang Q, et al. Community detection based on distance dynamics[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2015:10751084.
伊鹏, 周桥, 门浩崧. 基于HMM的动态社会网络社团发现算法[J]. 计算机研究与发展, 2017, 54(11):26112619.Yin Peng,Zhou Qiao,Men Haosong. Dynamic social network community detection algorithm based on hidden markov model[J]. Journal of Computer Research and Development, 2017.
[12]
Tantipathananandh C, Berger-Wolf T, Kempe D. A framework for community identification in dynamic social networks[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, DBLP, 2007:717726.
[13]
Greene D, Doyle D, Cunningham P. Tracking the evolution of communities in dynamic social networks[C]∥International Conference on Advances in Social Networks Analysis and Mining. IEEE, 2010:176183.
[14]
Takaffoli M, Sangi F, Fagnan J, et al. Community evolution mining in dynamic social networks[J]. Procedia-Social and Behavioral Sciences, 2011, 22(22):4958.
[15]
Bhat S Y, Abulaish M. HOC tracker: tracking the evolution of hierarchical and overlapping communities in dynamic social networks[J]. Knowledge & Data Engineering IEEE Transactions on, 2015, 27(4):10191013.
[16]
薛春晓. 基于核心成员的关联群追踪技术研究[D]. 北京:中国科学院大学, 2013.Xue Chunxiao. The researchof associated group tracking technolog based on the core of the individuals [D]. Beijing: University of Chinese Academy of Sciences, 2013.
[17]
Hennig C, Hausdorf B. Design of dissimilarity measures: a new dissimilarity between species distribution areas[J]. Data Science & Classification, 2006:2937.
[18]
Xia P, Zhang L, Li F. Learning similarity with cosine similarity ensemble[J]. Information Sciences, 2015, 307:3952.
