Improved community evolution relationship analysis method for dynamic graphs

doi:10.11772/j.issn.1001-9081.2020010072

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (8): 2313-2318.DOI: 10.11772/j.issn.1001-9081.2020010072

• Advanced computing • Previous Articles Next Articles

Improved community evolution relationship analysis method for dynamic graphs

LUO Xiangyu^1,2, LI Jianan¹, LUO Xiaoxia¹, WANG Jia¹

1. College of Computer Science and Technology, Xi'an University of Science and Technology, Xi'an Shaanxi 710054, China;
2. School of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an Shaanxi 710049, China

Received:2020-02-04 Revised:2020-04-17 Online:2020-08-10 Published:2020-04-28
Supported by:
This work is partially supported by the Youth Program of National Natural Science Foundation of China (61702408), the Key Project of National Natural Science Foundation of China (51634007), the Scientific Research Program of Education Department of Shaanxi Province (18JK0507).

改进的动态图社区演化关系分析方法

罗香玉^1,2, 李嘉楠¹, 罗晓霞¹, 王佳¹

1. 西安科技大学计算机科学与技术学院, 西安 710054;
2. 西安交通大学电子与信息工程学部, 西安 710049

通讯作者: 罗香玉(1984-),女,河北宁晋人,讲师,博士,CCF会员,主要研究方向:分布式存储、大数据;luoxiangyu@xust.edu.cn
作者简介:李嘉楠(1992-),男,陕西西安人,硕士研究生,主要研究方向:分布式存储、动态图演化;罗晓霞(1964-),女,陕西扶风人,教授,主要研究方向:大数据、云计算、软件工程、分布式计算;王佳(1995-),女,陕西延安人,硕士研究生,主要研究方向:分布式存储、图的划分算法。
基金资助:
国家自然科学基金青年基金资助项目（61702408）；国家自然科学基金重点项目（51634007）；陕西省教育厅专项科研计划项目（18JK0507）。

Abstract

Abstract: The community evolution relationships extracted by the traditional adjacent time slice analysis cannot fully describe the entire community evolution process in dynamic graphs. Therefore, an improved community evolution relationship analysis method was proposed. First, the community events were defined, and the evolution states of the community were described according to the occurred community events. Then, the event matching was performed on two communities within different time slices to obtain community evolution relationships. Results of comparison with the traditional methods show that the total number of community events detected by the proposed method is more than twice that revealed by the traditional method, which proves that the proposed method can provide more useful information for describing the evolution process of communities in dynamic graphs.

Key words: dynamic graph, community structure, community event, community evolution relationship analysis, community detection

摘要： 传统基于相邻时间片分析所获得的社区演化关系无法完备地刻画动态图社区演化的整个过程。为此提出了一种改进的社区演化关系分析方法。首先，定义社区事件，并根据发生的社区事件来描述社区的演化状态；然后，对两个不相同时间片内的社区进行事件匹配，从而获得社区演化关系；最后，通过实验将所提方法与传统方法进行比较。实验结果表明，所提方法发现的社区事件总数是传统方法的2倍以上，可为动态图社区演化过程的描述提供更丰富的信息。

关键词: 动态图, 社区结构, 社区事件, 社区演化关系分析, 社区发现

CLC Number:

TP393.027

LUO Xiangyu, LI Jianan, LUO Xiaoxia, WANG Jia. Improved community evolution relationship analysis method for dynamic graphs[J]. Journal of Computer Applications, 2020, 40(8): 2313-2318.

罗香玉, 李嘉楠, 罗晓霞, 王佳. 改进的动态图社区演化关系分析方法[J]. 计算机应用, 2020, 40(8): 2313-2318.

References

[1] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.
[2] GUIMERA R, AMARAL L A N. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433(7028):895-900.
[3] LESKOVEC J, KLEINBERG J, FALOUTSOS C. Graphs over time:densification laws, shrinking diameters and possible explanation[C]//Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. New York:ACM, 2005:177-187.
[4] LESKOVEC J, LANG K J, DASGUPTA, et al. Statistical properties of community structure in large social and information networks[C]//Proceedings of the 17th International Conference on World Wide Web. New York:ACM, 2008:695-704.
[5] MISLOVE A, MARCON M, GUMMADI K P, et al. Measurement and analysis of online social networks[C]//Proceeding of the 7th ACM SIGCOMM Conference on Internet Measurement. New York:ACM, 2007:29-42.
[6] 窦炳琳,李澍淞,张世永. 基于结构的社会网络分析[J]. 计算机学报, 2012, 35(4):741-753. (DOU B L, LI S S, ZHANG S Y. Social network analysis based on structure[J]. Chinese Journal of Computers, 2012, 35(4):741-753.)
[7] 王莉,程学旗. 在线社会网络的动态社区发现及演化[J]. 计算机学报, 2015, 38(2):219-237. (WANG L, CHENG X Q. Dynamic community in online social networks[J]. Chinese Journal of Computers, 2015, 38(2):219-237.)
[8] BARABÃSI A L, BONABEAU E. Scale-free networks[J]. Scientific American, 2003, 288(5):60-69.
[9] FALKOWSKI T, BARTH A, SPILIOPOULOU M. Studying community dynamics with an incremental graph mining algorithm[C]//Proceedings of the 14th Americas Conference on Information Systems. Atlanta:Association for Information Systems, 2008:No.29.
[10] HOPCROFT J, KHAN O, KULIS B, et al. Tracking evolving communities in large linked networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(S1):5249-5253.
[11] CLAUSET A, NEWMAN M E C, MOORE C. Finding community structure in very large networks[J]. Physical Review E:Statistical, Nonlinear, and Soft Matter Physics, 2004, 70:No.066111.
[12] ASUR S, PARTHASARATHY S, UCAR D. An event-based framework for characterizing the evolutionary behavior of interaction graphs[J]. ACM Transactions on Knowledge Discovery from Data, 2009, 3(4):No.16.
[13] VAN DONGEN S. A cluster algorithm for graphs[J]. Report-Information Systems, 2000, 10:1-40.
[14] GREENE D, DOYAL D, CUNNINGHAM P. Tracking the evolution of communities in dynamic social networks[C]//Proceedings of the 2010 International Conference on Advances in Social Networks Analysis and Mining. Piscataway:IEEE, 2010:176-183.
[15] TAKAFFOLI M, SANGI F, FAGNAN J, et al. Community evolution mining in dynamic social networks[J]. Procedia-Social and Behavioral Sciences, 2011, 22:49-58.
[16] BRÓDKA P, SAGANOWSKI S, KAZIENKO P. GED:the method for group evolution discovery in social networks[J]. Social Network Analysis and Mining, 2013, 3(1):1-14.
[17] SUN Y, TANG J, PAN L, et al. Matrix based community evolution events detection in online social networks[C]//Proceedings of the 2015 IEEE International Conference on Smart City/Social Computing and Networking/Sustainable Computing and Communications. Piscataway:IEEE, 2015:465-470.
[18] ZHU J, LIU J, ZHANG X, et al. A reconstructed event-based framework for analyzing community evolution[C]//Proceedings of the 2016 IEEE International Conference on Big Data Analysis. Piscataway:IEEE, 2016:1-4.
[19] LIU J, DU Y, LI Q, et al. Social community evolution by combining gravitational relationship with community structure[J]. Intelligent Data Analysis, 2018, 22(5):1143-1161.
[20] WANG Z, LI Z, YUAN G, et al. Tracking the evolution of overlapping communities in dynamic social networks[J]. Knowledge-Based Systems, 2018, 157:81-97.
[21] 徐兵,赵亚伟,徐杨远翔. 基于关联群演化相似度的社团追踪算法[J].复杂系统与复杂性科学, 2019, 16(1):14-25. (XU B, ZHAO Y W, XU Y Y X. Community tracking algorithm based on similarity of association group evolution[J]. Complex Systems and Complexity Science, 2019, 16(1):14-25.)
[22] PALLA G, DERÉNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043):814-818.
[23] LIU X, MURATA T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J]. Physica A:Statistical Mechanics and Its Applications, 2010, 389(7):1493-1500.
[24] GÉNOIS M, VESTERGAARD C L, FOURNET J, et al. Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers[J]. Network Science, 2015, 3(3):326-347.
[25] GÉNOIS M, BARART A. Can co-location be used as a proxy for face-to-face contacts?[J]. EPJ Data Science, 2018, 7(1):No.11.

Improved community evolution relationship analysis method for dynamic graphs

改进的动态图社区演化关系分析方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LI Yafang, LIANG Ye, FENG Weiwei, ZU Baokai, KANG Yujian. Deep network embedding method based on community optimization [J]. Journal of Computer Applications, 2021, 41(7): 1956-1963.
[2]	LI Ping, WANG Fen, CHEN Qidong, SUN Jun. Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem [J]. Journal of Computer Applications, 2021, 41(3): 803-811.
[3]	LI Chunying, TANG Yong, XIAO Zhenghong, LI Tiansong. Influential scholar recommendation model in academic social network [J]. Journal of Computer Applications, 2020, 40(9): 2594-2599.
[4]	ZHENG Wenping, YUE Xiangdou, YANG Gui. Improved label propagation algorithm based on random walk [J]. Journal of Computer Applications, 2020, 40(12): 3423-3429.
[5]	CHENG Qiwei, CHEN Qimai, HE Chaobo, LIU Hai. Overlapping community detection method based on improved symmetric binary nonnegative matrix factorization [J]. Journal of Computer Applications, 2020, 40(11): 3203-3210.
[6]	LI Shasha, LIANG Dongyang, YU Jie, JI Bin, MA Jun, TAN Yusong, WU Qingbo. Research team mining algorithm based on teacher-student relationship [J]. Journal of Computer Applications, 2020, 40(11): 3198-3202.
[7]	CHEN Wanjie, SHENG Yiqiang. Non-unidimensional community detection algorithm based on network representation learning [J]. Journal of Computer Applications, 2019, 39(12): 3467-3475.
[8]	DU Hangyuan, PEI Xiya, WANG Wenjian. Overlapping community detection algorithm for attributed networks [J]. Journal of Computer Applications, 2019, 39(11): 3151-3157.
[9]	GU Junhua, HUO Shijie, WANG Shoubin, TIAN Zhe. Fast label propagation algorithm based on node centrality and community similarity [J]. Journal of Computer Applications, 2018, 38(5): 1320-1326.
[10]	LI Lei, YAN Guanghui, YANG Shaowen, ZHANG Haitao. Improved Louvain method with strategy of separating isolated nodes [J]. Journal of Computer Applications, 2017, 37(4): 970-974.
[11]	CHEN Yiying, CHAI Bianfang, LI Wenbin, HE Yichao, WU Congcong. Semi-supervised community detection algorithm using active link selection based on iterative framework [J]. Journal of Computer Applications, 2017, 37(11): 3085-3089.
[12]	CHAI Bianfang, WANG Jianling, XU Jiwei, LI Wenbin. Active semi-supervised community detection method based on link model [J]. Journal of Computer Applications, 2017, 37(11): 3090-3094.
[13]	YOU Xinxin, GE Meng. Community detection algorithm based on belief propagation in complex networks [J]. Journal of Computer Applications, 2017, 37(11): 3115-3118.
[14]	WANG Yan, HUANG Faliang, YUAN Chang'an. Semi-synchronous communities detection algorithm based on label influence [J]. Journal of Computer Applications, 2016, 36(6): 1573-1578.
[15]	WANG Tianhong, WU Xing, LAN Wangsen. Improved community detection algorithm based on local modularity [J]. Journal of Computer Applications, 2016, 36(5): 1296-1301.