在复杂网络中,社团结构普遍存在,且随着时间的变化网络中的社团也在不断变化。为了追踪到社团的变化并把相邻时刻的社团关联起来形成关联群,在阐述相关定义的基础上,提出了利用综合加权的演化相似度来衡量相邻时刻的社团相似度,又提出了一种利用“多部图”提取演化路径,生成演化序列的方法。最后在某银行业务数据上进行实验,实验结果表明该算法比利用单一指标追踪到社团的准确率更高。
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.
[1]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.
[10] Aggarwal C, Subbian K. Evolutionary network analysis:a survey[J]. Acm Computing Surveys, 2014, 47(1):136.
[11] 伊鹏, 周桥, 门浩崧. 基于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.
[19] 吴春林. 采用专家打分法对债权价值进行分析的探讨[J]. 中国资产评估, 2007(11):1820.
Wu Chunlin. Analysis of creditor′s rights value by expert scoring method[J].Financial Assets Apprasisal, 2007(11):1820.
