Nonuniform time slicing method based on prediction of community variance

doi:10.11772/j.issn.1001-9081.2022111736

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (11): 3457-3463.DOI: 10.11772/j.issn.1001-9081.2022111736

Special Issue: 数据科学与技术

• Data science and technology • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

动态网络时间片划分方法对社区演化分析结果的准确性具有重要影响，但社区随时间及网络拓扑改变呈现非线性的变化，现有均匀时间片划分以及基于网络拓扑改变量的非均匀时间片划分方法在捕捉社区演化事件方面均效果不佳。为此，提出一种基于社区改变量估计的非均匀时间片划分方法，其中社区改变量通过变化后网络期望达到的社区模块度与直接应用网络变化前的社区发现结果获得的社区模块度之差来定量描述。首先，基于时间序列分析建立社区模块度预测模型；其次，使用该模型预测变化后网络期望达到的社区模块度，并求得社区改变量的估计值；最后，当该估计值超过预先设置的阈值时即生成一个新的时间片。在两个真实网络数据集上的实验结果显示，相较于传统的均匀时间片划分方法和基于网络拓扑改变量的非均匀时间片划分方法，所提方法在动态网络数据集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个。

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

CLC Number:

TP391

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.

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

Figures/Tables 7

Tab. 1 Description of datasets

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

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

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

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

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

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

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

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

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

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

References 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]	Xinrui LIN, Xiaofei WANG, Yan ZHU. Academic anomaly citation group detection based on local extended community detection [J]. Journal of Computer Applications, 2024, 44(6): 1855-1861.
[2]	Shiliang LIU, Yi WANG, Yinglong MA. Non-overlapping community detection with imbalanced community sizes [J]. Journal of Computer Applications, 2024, 44(11): 3396-3402.
[3]	Zhenyu LIU, Chaokun WANG, Gaoyang GUO. Parallel algorithm of betweenness centrality for dynamic networks [J]. Journal of Computer Applications, 2023, 43(7): 1987-1993.
[4]	Lin ZHOU, Yuzhi XIAO, Peng LIU, Youpeng QIN. Community mining algorithm based on multi-relationship of nodes and its application [J]. Journal of Computer Applications, 2023, 43(5): 1489-1496.
[5]	LI Zhanli, LI Ying, LUO Xiangyu, LUO Yingxiao. Local community detection algorithm based on Monte-Carlo iterative solving strategy [J]. Journal of Computer Applications, 2023, 43(1): 104-110.
[6]	Jun HU, Zhengkang XU, Li LIU, Fujin ZHONG. Network embedding method based on multi-granularity community information [J]. Journal of Computer Applications, 2022, 42(3): 663-670.
[7]	Yuan GUO, Xuewen WANG, Chong WANG, Jinlin JIANG. Nonlinear scrambling diffusion synchronization image encryption based on dynamic network [J]. Journal of Computer Applications, 2022, 42(1): 162-170.
[8]	ZHANG Yuanjun, ZHANG Xihuang. Dynamic network representation learning model based on graph convolutional network and long short-term memory network [J]. Journal of Computer Applications, 2021, 41(7): 1857-1864.
[9]	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.
[10]	Huibo LI, Yunxiao ZHAO, Liang BAI. Dynamic graph representation learning method based on deep neural network and gated recurrent unit [J]. Journal of Computer Applications, 2021, 41(12): 3432-3437.
[11]	Jicheng CHEN, Hongchang CHEN. Community detection method based on tensor modeling and evolutionary K-means clustering [J]. Journal of Computer Applications, 2021, 41(11): 3120-3126.
[12]	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.
[13]	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.
[14]	ZHENG Wenping, YUE Xiangdou, YANG Gui. Improved label propagation algorithm based on random walk [J]. Journal of Computer Applications, 2020, 40(12): 3423-3429.
[15]	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.

Nonuniform time slicing method based on prediction of community variance

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 35

Related Articles 15

Recommended Articles

Metrics