基于社区改变量估计的非均匀时间片划分方法

doi:10.11772/j.issn.1001-9081.2022111736

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (11): 3457-3463.DOI: 10.11772/j.issn.1001-9081.2022111736

• 数据科学与技术 • 上一篇

基于社区改变量估计的非均匀时间片划分方法

罗香玉¹(), 闫克¹, 卢琰¹, 王甜¹, 辛刚²

^1.西安科技大学计算机科学与技术学院，西安 710054
^2.中国航空工业集团公司西安航空计算技术研究所，西安 710119

收稿日期:2022-11-22 修回日期:2023-02-27 接受日期:2023-03-08 发布日期:2023-03-20 出版日期:2023-11-10
通讯作者: 罗香玉
作者简介:罗香玉（1984—），女，河北邢台人，副教授，博士，CCF会员，主要研究方向：图计算、复杂网络 luoxiangyu@xust.edu.cn
闫克（1994—），男，河南南阳人，硕士研究生，主要研究方向：社区演化分析
卢琰（1998—），女，河南驻马店人，硕士研究生，主要研究方向：社区演化分析、传播动力学分析
王甜（1999—），女，陕西宝鸡人，硕士研究生，主要研究方向：社区演化分析、传播动力学分析
辛刚（1984—），男，陕西宝鸡人，高级工程师，硕士，主要研究方向：机器学习、大数据。
基金资助:
国家自然科学基金资助项目(12071367);陕西省基础研究计划面上项目(2022JM?317)

Nonuniform time slicing method based on prediction of community variance

Xiangyu LUO¹(), Ke YAN¹, Yan LU¹, Tian WANG¹, Gang XIN²

^1.College of Computer Science and Technology，Xi’an University of Science and Technology，Xi’an Shaanxi 710054，China
^2.AVIC Xi’an Aeronautics Computing Technique Research Institute，Xi’an Shaanxi 710119，China

Received:2022-11-22 Revised:2023-02-27 Accepted:2023-03-08 Online:2023-03-20 Published:2023-11-10
Contact: Xiangyu LUO
About author:LUO Xiangyu， born in 1984， Ph. D.， associate professor. Her research interests include graph computing， complex network.
YAN Ke， born in 1994， M. S. candidate. His research interests include community evolution analysis.
LU Yan， born in 1998， M. S. candidate. Her research interests include community evolution analysis， analysis of spreading dynamics.
WANG Tian， born in 1999， M. S. candidate. Her research interests include community evolution analysis， analysis of spreading dynamics.
XIN Gang， born in 1984， M. S.， senior engineer. His research interests include machine learning， big data.
Supported by:
National Natural Science Foundation of China(12071367);Program of Basic Natural Science of Shaanxi Province(2022JM-317)

摘要/Abstract

摘要：

动态网络时间片划分方法对社区演化分析结果的准确性具有重要影响，但社区随时间及网络拓扑改变呈现非线性的变化，现有均匀时间片划分以及基于网络拓扑改变量的非均匀时间片划分方法在捕捉社区演化事件方面均效果不佳。为此，提出一种基于社区改变量估计的非均匀时间片划分方法，其中社区改变量通过变化后网络期望达到的社区模块度与直接应用网络变化前的社区发现结果获得的社区模块度之差来定量描述。首先，基于时间序列分析建立社区模块度预测模型；其次，使用该模型预测变化后网络期望达到的社区模块度，并求得社区改变量的估计值；最后，当该估计值超过预先设置的阈值时即生成一个新的时间片。在两个真实网络数据集上的实验结果显示，相较于传统的均匀时间片划分方法和基于网络拓扑改变量的非均匀时间片划分方法，所提方法在动态网络数据集Arxiv HEP-PH上的识别社区消失事件方面分别提早1.10 d和1.30 d，识别社区形成事件方面分别提早8.34 d和3.34 d，识别出的社区缩小、扩大事件总数分别增加10个和1个；在Sx-MathOverflow数据集上的识别社区消失事件方面分别提早3.30 d和1.80 d，识别社区形成事件方面分别提早6.41 d和2.97 d，识别出的社区缩小、扩大事件总数分别增加15个和7个。

关键词: 动态网络, 时间片划分, 社区演化, 时间序列分析, 社区发现, 社区模块度

Abstract:

Time slicing methods in dynamic networks greatly influence the accuracy of community evolution analysis results. As communities vary nonlinearly with time and network topology， both the existing uniform time slicing method and network topology variance-based nonuniform time slicing method are unsatisfactory in capturing community evolution events. Therefore， a nonuniform time slicing method based on prediction of community variance was proposed， where the community variance is quantitatively described by the difference between the community modularity expected to be achieved by the updated network and the community modularity obtained by directly applying the community detection results of the network before changing. Firstly， the prediction model of community modularity was established on the basis of time series analysis. Secondly， with the established model， the expected community modularity of the updated network was predicted， and the prediction value of community variance was obtained. Finally， once the prediction value surpassed a previously set threshold， a new time slice was generated. Experimental results on two real network datasets show that compared with the traditional uniform time slicing method and the nonuniform time slicing method based on network topology variance， on the dynamic network dataset Arxiv HEP-PH， the proposed method identifies community disappearance events 1.10 days and 1.30 days earlier， respectively， and identifies the community forming events 8.34 days and 3.34 days earlier， respectively， and the total number of identified community shrinking and growing events increased by 10 and 1 respectively. On Sx?MathOverflow dataset， the proposed method identifies community disappearance events 3.30 days and 1.80 days earlier， and identifies the community forming events 6.41 days and 2.97 days earlier respectively， and the total number of identified community shrinking and growing events increased by 15 and 7， respectively.

Key words: dynamic network, time slicing, community evolution, time series analysis, community detection, community modularity

中图分类号:

TP391

罗香玉, 闫克, 卢琰, 王甜, 辛刚. 基于社区改变量估计的非均匀时间片划分方法[J]. 计算机应用, 2023, 43(11): 3457-3463.

Xiangyu LUO, Ke YAN, Yan LU, Tian WANG, Gang XIN. Nonuniform time slicing method based on prediction of community variance[J]. Journal of Computer Applications, 2023, 43(11): 3457-3463.

图/表 7

表 1 数据集描述

Tab. 1 Description of datasets

数据集	节点数	边数	时间跨度/d
Arxiv HEP-PH	34 546	42 578	3 689
Sx-MathOverflow	24 818	506 550	2 359

图 1 两个数据集上三种时间片划分方法划分的时间片的长度分布

Fig. 1 Length distribution of time slices sliced by three time slicing methods on two datasets

表 2 两个数据集上三种时间片划分方法的准确性对比

Tab. 2 Accuracy comparison of three time slicing methods on two datasets

方法	Arxiv HEP-PH						Sx-MathOverflow
方法	$T α$ /d	$Δ T α$ /d	$T β$ /d	$Δ T β$ /d	$N e$	$Δ N e$	$T α$ /d	$Δ T α$ /d	$T β$ /d	$Δ T β$ /d	$N e$	$Δ N e$
本文方法	292.9	—	22.33	—	83	—	189.4	—	19.74	—	124	—
均匀时间片划分方法	294.0	1.1	30.67	8.34	73	10	192.7	3.3	26.15	6.41	109	15
基于网络拓扑改变量的划分方法	294.2	1.3	25.67	3.34	82	1	191.2	1.8	22.71	2.97	117	7

表 2 两个数据集上三种时间片划分方法的准确性对比

Tab. 2 Accuracy comparison of three time slicing methods on two datasets

方法	Arxiv HEP-PH						Sx-MathOverflow
方法	$T α$ /d	$Δ T α$ /d	$T β$ /d	$Δ T β$ /d	$N e$	$Δ N e$	$T α$ /d	$Δ T α$ /d	$T β$ /d	$Δ T β$ /d	$N e$	$Δ N e$
本文方法	292.9	—	22.33	—	83	—	189.4	—	19.74	—	124	—
均匀时间片划分方法	294.0	1.1	30.67	8.34	73	10	192.7	3.3	26.15	6.41	109	15
基于网络拓扑改变量的划分方法	294.2	1.3	25.67	3.34	82	1	191.2	1.8	22.71	2.97	117	7

图 2 1995年4月30日网络快照上的一个社区

Fig. 2 A community in network snapshot on April 30， 1995

图 3 1995年6月1日网络快照上的一个社区

Fig. 3 A community in network snapshot on June 1， 1995

表3 社区发现算法对本文方法性能的影响

Tab. 3 Influence of community detection algorithm on performance of proposed method

社区发现算法	Arxiv HEP-PH				Sx-MathOverflow
社区发现算法	$T α$ /d	$T β$ /d	$N e$	$N s$	$T α$ /d	$T β$ /d	$N e$	$N s$
DynaMo	293.3	22.56	84	47	187.1	20.16	122	72
Louvain	292.9	22.33	83	47	187.4	19.74	124	72

表3 社区发现算法对本文方法性能的影响

Tab. 3 Influence of community detection algorithm on performance of proposed method

社区发现算法	Arxiv HEP-PH				Sx-MathOverflow
社区发现算法	$T α$ /d	$T β$ /d	$N e$	$N s$	$T α$ /d	$T β$ /d	$N e$	$N s$
DynaMo	293.3	22.56	84	47	187.1	20.16	122	72
Louvain	292.9	22.33	83	47	187.4	19.74	124	72

表4 阈值θ对本文方法性能的影响

Tab. 4 Influence of threshold θ on performance of proposed method

θ	Arxiv HEP-PH				Sx-MathOverflow
θ	$T α$ /d	$T β$ /d	$N e$	$N s$	$T α$ /d	$T β$ /d	$N e$	$N s$
0.005	289.2	8.26	272	167	182.3	9.73	314	218
0.010	290.3	10.33	189	93	183.5	14.85	227	165
0.015	291.4	14.28	137	76	186.7	17.31	159	108
0.020	292.9	22.33	83	47	187.4	19.74	124	72
0.025	295.3	31.72	67	39	191.7	27.39	83	46
0.030	298.6	34.65	53	33	193.2	32.61	67	28

表4 阈值θ对本文方法性能的影响

Tab. 4 Influence of threshold θ on performance of proposed method

θ	Arxiv HEP-PH				Sx-MathOverflow
θ	$T α$ /d	$T β$ /d	$N e$	$N s$	$T α$ /d	$T β$ /d	$N e$	$N s$
0.005	289.2	8.26	272	167	182.3	9.73	314	218
0.010	290.3	10.33	189	93	183.5	14.85	227	165
0.015	291.4	14.28	137	76	186.7	17.31	159	108
0.020	292.9	22.33	83	47	187.4	19.74	124	72
0.025	295.3	31.72	67	39	191.7	27.39	83	46
0.030	298.6	34.65	53	33	193.2	32.61	67	28

参考文献 35

1	YAN J， LIU G. Two-stage anomaly detection algorithm via dynamic community evolution in temporal graph［J］. Applied Intelligence， 2022， 52（11）： 12222-12240. 10.1007/s10489-021-03109-4
2	JIA X， LI X， DU N， et al. Tracking community consistency in dynamic networks： an influence-based approach［J］. IEEE Transactions on Knowledge and Data Engineering， 2019， 33（2）： 782-795.
3	PENG H， LI J， SONG Y， et al. Streaming social event detection and evolution discovery in heterogeneous information networks［J］. ACM Transactions on Knowledge Discovery from Data， 2021， 15（5）： No.89. 10.1145/3447585
4	HU Y， YANG B， LV C. A local dynamic method for tracking communities and their evolution in dynamic networks［J］. Knowledge-Based Systems， 2016， 110： 176-190. 10.1016/j.knosys.2016.07.027
5	SUN P G， QUAN Y N， MIAO Q G， et al. Identifying influential genes in protein-protein interaction networks［J］. Information Sciences， 2018， 454/455： 229-241. 10.1016/j.ins.2018.04.078
6	FREILICH R， ARHAR T， ABRAMS J L， et al. Protein-protein interactions in the molecular chaperone network［J］. Accounts of Chemical Research， 2018， 51（4）： 940-949. 10.1021/acs.accounts.8b00036
7	LUO Y， MA J. The influence of positive news on rumor spreading in social networks with scale-free characteristics［J］. International Journal of Modern Physics C， 2018， 29（9）： No.1850078. 10.1142/S012918311850078X
8	JIA J， WU W. A rumor transmission model with incubation in social networks［J］. Physica A： Statistical Mechanics and its Applications， 2018， 491： 453-462. 10.1016/j.physa.2017.09.063
9	陈小强，周丽华，程超，等. 动态网络中稳定社区发现［J］. 小型微型计算机系统， 2015， 36（9）： 1977-1981. 10.3969/j.issn.1000-1220.2015.09.012
	CHEN X Q， ZHOU L H， CHENG C， et al. Detecting stable communities in dynamic networks［J］. Journal of Chinese Computer Systems， 2015， 36（9）： 1977-1981. 10.3969/j.issn.1000-1220.2015.09.012
10	DAKICHE N， TAYEBA F B S， SLIMANI Y， et al. Tracking community evolution in social networks： a survey［J］. Information Processing and Management， 2019， 56（3）： 1084-1102. 10.1016/j.ipm.2018.03.005
11	TAJEUNA E G， BOUGUESSA M， WANG S. Modeling and predicting community structure changes in time-evolving social networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 31（6）： 1166-1180. 10.1109/tkde.2018.2851586
12	SAGANOWSKI S， BRÓDKA P， KAZIENKO P. Influence of the dynamic social network timeframe type and size on the group evolution discovery［C］// Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway： IEEE， 2012： 679-683. 10.1109/asonam.2012.113
13	KADKHODA MOHAMMADMOSAFERI K， NADERI H. Evolution of communities in dynamic social networks： an efficient map-based approach［J］. Expert Systems with Applications， 2020， 147： No.113221. 10.1016/j.eswa.2020.113221
14	PAN Y， ZHANG L. Modeling and analyzing dynamic social networks for behavioral pattern discovery in collaborative design［J］. Advanced Engineering Informatics， 2022， 54： No.101758. 10.1016/j.aei.2022.101758
15	GUO C， WANG J， ZHANG Z. Evolutionary community structure discovery in dynamic weighted networks［J］. Physica A： Statistical Mechanics and its Applications， 2014， 413： 565-576. 10.1016/j.physa.2014.07.004
16	LI W， ZHU H， LI S， et al. Evolutionary community discovery in dynamic social networks via resistance distance［J］. Expert Systems with Applications， 2021， 171： No.114536. 10.1016/j.eswa.2020.114536
17	ORMAN G K， ÇOLAK S. Similarity based compression ratio for dynamic network modelling［C］// Proceedings of the IEEE 19th International Conference on Smart Technologies. Piscataway： IEEE， 2021： 227-232. 10.1109/eurocon52738.2021.9535635
18	SULO R， BERGER-WOLF T， GROSSMAN R. Meaningful selection of temporal resolution for dynamic networks［C］// Proceedings of the 8th Workshop on Mining and Learning with Graphs. New York： ACM， 2010： 127-136. 10.1145/1830252.1830269
19	ROSSETTI G， CAZABET R. Community discovery in dynamic networks： a survey［J］. ACM Computing Surveys， 2018， 51（2）： No.35. 10.1145/3172867
20	WANG Y， ARCHAMBAULT D， HALEEM H， et al. Nonuniform timeslicing of dynamic graphs based on visual complexity［C］// Proceedings of the 2019 IEEE Visualization Conference. Piscataway： IEEE， 2019： 1-5. 10.1109/visual.2019.8933748
21	BHAT S Y， ABULAISH M. HOCTracker： tracking the evolution of hierarchical and overlapping communities in dynamic social networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2015， 27（4）： 1019-1031. 10.1109/tkde.2014.2349918
22	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. 10.1016/j.knosys.2018.05.026
23	QIAO S， HAN N， GAO Y， et al. Dynamic community evolution analysis framework for large-scale complex networks based on strong and weak events［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2021， 51（10）： 6229-6243. 10.1109/tsmc.2019.2960085
24	XU Z， RUI X， HE J， et al. Superspreaders and superblockers based community evolution tracking in dynamic social networks［J］. Knowledge-Based Systems， 2020， 192： No.105377. 10.1016/j.knosys.2019.105377
25	ÇOLAK S， ORMAN G K. Aggregating time windows for dynamic network extraction［C］// Proceedings of the 2021 International Conference on Innovations in Intelligent Systems and Applications. Piscataway： IEEE， 2021： 1-6. 10.1109/inista52262.2021.9548480
26	ORMAN G K， TÜRE N， BALCISOY S， et al. Finding proper time intervals for dynamic network extraction［J］. Journal of Statistical Mechanics： Theory and Experiment， 2021， 2021（3）： No.033414. 10.1088/1742-5468/abed45
27	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. 10.1073/pnas.122653799
28	BLONDEL V D， GUILLAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks［J］. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008（10）： No.P10008. 10.1088/1742-5468/2008/10/p10008
29	RAGHAVAN U N， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in large-scale networks［J］. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2007， 76（3）： No.036106. 10.1103/physreve.76.036106
30	BRÓDKA P， SAGANOWSKI S， KAZIENKO P. Tracking group evolution in social networks［C］// Proceedings of the 2011 International Conference on Social Informatics， LNCS 6984. Berlin： Springer， 2011： 316-319.
31	WHEELWRIGHT S， MAKRIDAKIS S， HYNDMAN R J， Forecasting ： Methods and Applications［M］. Hoboken， NJ： John Wiley & Sons， 2008： 335-346.
32	NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks［J］. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（2）： No.026113. 10.1103/physreve.69.026113
33	LESKOVEC J， KREVL A. High-energy physics citation network［DS/OL］. ［2021-12-15］..
34	LESKOVEC J， KREVL A. Math overflow temporal network［DS/OL］. ［2021-12-15］..
35	ZHUANG D， CHANG J M， LI M. DynaMo： dynamic community detection by incrementally maximizing modularity［J］. IEEE Transactions on Knowledge and Data Engineering， 2021， 33（5）： 1934-1945.

[1]	刘震宇, 王朝坤, 郭高扬. 面向动态网络的介数中心度并行算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 1987-1993.
[2]	杨煜, 段威威. 基于谱聚类的社交网络动态社区发现算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3129-3135.
[3]	李占利, 李颖, 罗香玉, 罗颖骁. 基于Monte-Carlo迭代求解策略的局部社区发现算法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 104-110.
[4]	胡军, 许正康, 刘立, 钟福金. 融合多粒度社区信息的网络嵌入方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 663-670.
[5]	郭媛, 王学文, 王充, 姜津霖. 基于动态网络的非线性置乱扩散同步图像加密[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 162-170.
[6]	张元钧, 张曦煌. 基于图卷积与长短期记忆网络的动态网络表示学习模型[J]. 计算机应用, 2021, 41(7): 1857-1864.
[7]	秦丽, 郝志刚, 李国亮. 国家食品安全标准图谱的构建及关联性分析[J]. 计算机应用, 2021, 41(4): 1005-1011.
[8]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[9]	李慧博, 赵云霄, 白亮. 基于深度神经网络和门控循环单元的动态图表示学习方法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3432-3437.
[10]	罗香玉, 李嘉楠, 罗晓霞, 王佳. 改进的动态图社区演化关系分析方法[J]. 计算机应用, 2020, 40(8): 2313-2318.
[11]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.
[12]	成其伟, 陈启买, 贺超波, 刘海. 基于改进对称二值非负矩阵分解的重叠社区发现方法[J]. 计算机应用, 2020, 40(11): 3203-3210.
[13]	李莎莎, 梁冬阳, 余杰, 纪斌, 马俊, 谭郁松, 吴庆波. 基于师门关系的研究团队挖掘算法[J]. 计算机应用, 2020, 40(11): 3198-3202.
[14]	邵豪, 王伦文, 邓健. 基于H运算的动态网络重要节点识别方法[J]. 计算机应用, 2019, 39(9): 2669-2674.
[15]	张琪, 纪淑娟, 傅强, 张纯金. 基于带权评论图的水军群组检测及特征分析[J]. 计算机应用, 2019, 39(6): 1595-1600.

基于社区改变量估计的非均匀时间片划分方法

Nonuniform time slicing method based on prediction of community variance

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 35

相关文章 15

编辑推荐

Metrics