基于社团多特征融合嵌入表示的时序链路预测方法

doi:10.11959/j.issn.2096-109x.2023013

Abstract

Abstract:

Dynamic networks integrates time attributes on the basis of static networks, and it contains multiple connotations such as the complexity and dynamics of the network structure.It is a better thinking object for studying complex network link prediction problems in the real world.Its high application value has attracted much attention in recent years.However, most of the research objects of traditional methods are still limited to static networks, and there are problems such as insufficient utilization of network time-domain evolution information and high time complexity.Combining sociological theory, a novel temporal link prediction method was proposed based on community multi-feature fusion embedding representation.The core idea of this method was to analyze the dynamic evolution characteristics of the network, learn the embedded representation vector of nodes within the community, and effectively fuse multiple features to measure the generation probability of the connection between nodes.The network was divided into several subgraphs by using community detection with collective influence weights and the Similarity index was proposed based on the collective influence.Then, the biased random walk and the Skip-gram were used to get the embedded vectors for every node and the Similarity index was proposed based on the random walk within the community.Integrating the collective influence, multiple central features of the community, and the representation vector learned within the community, the Similarity index was proposed based on the multi-features fusion.Compared with classical temporal link prediction methods, including moving average methods, embedded representation methods, and graph neural network methods, experimental results on six real data sets show that the proposed methods based on the random walk within the community and the multi-features fusion both achieve better prediction performance under the evaluation criteria of AUC.

Key words: temporal link prediction, community feature, influence, multi-feature, random walk, embedded representation

CLC Number:

TP393

Yuhang ZHU, Lixin JI, Yingle LI, Haitao LI, Shuxin LIU. Temporal link prediction method based on community multi-features fusion and embedded representation[J]. Chinese Journal of Network and Information Security, 2023, 9(1): 67-82.

Figures/Tables 12

References 44

[1]	吕琳媛, 任晓龙, 周涛 . 网络链路预测:概念与前沿[J]. 中国计算机学会通讯, 2016,012(4): 12-19.
	LYU L Y , REN X L , ZHOU T . Network link prediction:concepts and frontiers[J]. Communications of China Computer Society, 2016,12(4): 12-19.
[2]	WANG M , QIU L , WANG X . A survey on knowledge graph embeddings for link prediction[J]. Symmetry, 2021,13(3): 485.
[3]	WU X , WU J , LI Y ,et al. Link prediction of time-evolving network based on node ranking[J]. Knowledge-Based Systems, 2020,195:105740.
[4]	DIVAKARAN A , MOHAN A . Temporal link prediction:A survey[J]. New Generation Computing, 2019,38(3): 1-46.
[5]	BARABáSI A L , ALBERT R . Emergence of scaling in random networks[J]. Science, 1999,286(5439): 509-512.
[6]	MARTINEZ V , BERZAL F , CUBERO J C . A survey of link prediction in complex networks[J]. ACM Computing Surveys, 2017,49(4): 69.1-69.33.
[7]	LORRAIN F , WHITE H C . Structural equivalence of individuals in social networks[J]. Social Networks, 1977,1(1): 67-98.
[8]	ZHOU T , L Lü , ZHANG Y C . Predicting missing links via local information[J]. European Physical Journal B, 2009,71(4): 623-630.
[9]	Lü L Y , JIN C H , ZHOU T . Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, 2009,80(4): 046122.
[10]	KATZ L . A new status index derived from sociometric analysis[J]. Psychometrika, 1953,18(1): 39-43.
[11]	ZHAO H , DU L , BUNTINE W . Leveraging node attributes for incomplete relational data[C]// International Conference on Machine Learning. Sydney,Australia, 2017: 4072-4081.
[12]	刘树新, 李星, 陈鸿昶 ,等. 基于资源传输匹配度的复杂网络链路预测方法[J]. 通信学报, 2020,041(006): 70-79.
	LIU S X , LI X , CHEN H C ,et al. Link prediction method based on matching degree of resource transmission for complex network[J]. Journal on Communications, 2020,41(6): 70-79.
[13]	JAVARI A , QIU H , BARZEGARAN E , JALILI ,et al. Statistical link label modeling for sign prediction:Smoothing sparsityby joining local and global information[C]. Proceedings of the 2017 IEEE International Conference on Data Mining (ICDM),Orleans,LA,USA, 2017: 1039-1044.
[14]	PAN L , ZHOU T , Lü L ,et al. Predicting missing links and identifying spurious links via likelihood analysis[J]. Scientific Reports, 2016,6(1): 1-10.
[15]	LI T , WANG B , JIANG Y ,et al. Restricted Boltzmann machine-based approaches for link prediction in dynamic networks[J]. IEEE Access, 2018,6: 29940-29951.
[16]	CHEN J , XU X , WU Y ,et al. GC-LSTM:graph convolution embedded LSTM for dynamic link prediction[J]. Applied Intelligence. 2021,52: 1-16.
[17]	DAUD N N , AB HAMID S H , SAADOON M ,et al. Applications of link prediction in social networks:A review[J]. Journal of Network and Computer Applications, 2020,166:102716.
[18]	WANG P , XU B W , WU Y R ,et al. Link prediction in social networks:The state-of-the-art[J]. Science China Information Sciences, 2015,58(1): 1-38.
[19]	刘书新, 刘群, 杜凡 . 基于模体演化与社区一致性的时序链路预测方法[J]. 计算机应用研究, 2019,36(12): 3674-3678,3684.
	LIU S X , LIU Q , DU F . Time series link prediction method based on motif evolution and community consistency[J]. Application Research of Computers, 2019,36(12): 3674-3678,3684.
[20]	JORGE , VALVERDE-REBAZA , ALNEU ,et al. Exploiting behaviors of communities of twitter users for link prediction[J]. Social Network Analysis ＆ Mining, 2013,3(4): 1063-1074.
[21]	LIU H , HU Z , HADDADI H ,et al. Hidden link prediction based on node centrality and weak ties[J]. EPL (Europhysics Letters), 2013,101:18004.
[22]	IBRAHIM N M A , CHEN L . Link prediction in dynamic social networks by integrating different types of information[J]. Applied Intelligence, 2015,42(4): 738-750.
[23]	VALVERDE-REBAZA J C , Lopes A . Link prediction in complex networks based on cluster information[C]// Advances in Artificial Intelligence-SBIA 2012,Berlin:Springer-Verlag, 2012: 92-101.
[24]	WANG J , MA Y , LIU M ,et al. A vertex similarity index using community information to improve link prediction accuracy[J]. 2017 IEEE International Conference on Systems,Man,and Cybernetics (SMC), 2017: 158-163.
[25]	焦杨 . 复杂网络社区检测、链路预测及应用[D]. 西安:西安电子科技大学, 2018.
	JIAO Y . Community detection,link prediction and applications in complex networks[D]. Xi'an:Xidian University, 2018.
[26]	GüNE? ? , GüNDüZ-??üDüCü ? , ?ATALTEPE Z . Link prediction using time series of neighborhood-based node similarity scores[J]. Data Mining ＆ Knowledge Discovery, 2016,30(1): 147-180.
[27]	OZCAN A , OGUDUCU S G . Supervised temporal link prediction using time series of similarity measures[C]// International Conference on Ubiquitous ＆ Future Networks,Milan,Italy. 2017: 519-521.
[28]	LIU SHUXIN , LIU QUN , Du fan . Time series link prediction method based on motif evolution and community consistency[J]. Computer application research, 2019,36(12): 3674-3678.
[29]	HU W , TONG S , MENGERSEN K ,et al. Weather variability and the incidence of cryptosporidiosis:comparison of time series poisson regression and SARIMA models[J]. Annals of Epidemiology, 2007,17(9): 679-688.
[30]	SKARDING J , GABRYS B , MUSIAL K . Foundations and modeling of dynamic networks using dynamic graph neural networks:A survey[J]. IEEE Access, 2021,9: 79143-79168.
[31]	YANG Y , LICHTENWALTER R N , CHAWLA N V.(2014) . Evaluating link prediction methods[J]. Knowledge and Information Systems, 45(3), 751-782.
[32]	MORONE F , MAKSE H A . Influence maximization in complex networks through optimal percolation[J]. Nature, 2015,524(7563): 65-68.
[33]	BLONDEL V D , GUILLAUME J L , LAMBIOTTE R ,et al. Fast unfolding of communities in large networks[J]. Journal Statistical Mechanics:Theory and Experiment, 2008,10:1008.
[34]	GOLDBERG Y , LEVY O . Word2vec explained:deriving Mikolov et al.'s negative-sampling word-embedding method[J]. arXiv, 2014,arxiv:1402.3722.
[35]	GROVER A , LESKOVEC J . Node2vec:Scalable feature learning for networks[C]. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Francisco,CA,USA,13-17 August 2016: 855-864.
[36]	SELVARAJAH K , RAGUNATHAN K , KOBTI Z ,et al. Dynamic network link prediction by learning effective subgraphs using CNN-LSTM[C]. Proceedings of the 2020 International Joint Conference on Neural Networks (IJCNN),Glasgow,UK,IEEE:Glasgow,UK, 2020: 1-8.
[37]	LESKOVEC J , KLEINBERG J , FALOUTSOS C . Graph evolution:densification and shrinking diameters[J]. ACM transactions on Knowledge Discovery from Data (TKDD), 2007,1(1).
[38]	LESKOVEC J , LANG K J , DASGUPTA A ,et al. Community structure in large networks:natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009,6(1): 29-123.
[39]	KUNEGIS J , . Konect:The koblenz network collection[C]. Proceedings of the 22nd International Conference on World Wide Web. Rio de Janeiro,Brazil, 2013: 1343-1350.
[40]	PANZARASA P , OPSAHL T , CARLEY K M . Patterns and dynamics of users’ behavior and interaction:network analysis of an online community[J]. Journal of the American Society for Information Science and Technology, 2009,60(5): 911-932.
[41]	LESKOVEC J , KREVL A . SNAP Datasets:Stanford large network dataset collection[EB]. 2014.
[42]	TANG J , QU M , WANG M ,et al. Line:large-scale information network embedding[C]// Proceedings of the 24th International Conference on World Wide Web. Florence,Italy, 2015: 1067-1077.
[43]	SANKAR A , WU Y , GOU L ,et al. Dysat:Deep neural representation learning on dynamic graphs via self-attention networks[C]. Proceedings of the 13th International Conference on Web Search and Data Mining. Houston,TX,USA, 2020: 519-527.
[44]	PAREJA A , DOMENICONI G , Chen J ,et al. Evolvegcn:evolving graph convolutional networks for dynamic graphs[C]// Proceedings of the AAAI Conference on Artificial Intelligence.New York. NY,USA, 2020,34(4): 5363-5370.

Metrics

Recommended 0

No Suggested Reading articles found!

基本特征参数	E-mail	Enron	DNC	MAN	UCI	LEM
节点数	1 005	87 273	2 029	167	1 899	485
连边数	332 334	1 048 576	39 264	82 927	59 835	196 364
起始日期	2003-10	2001-1-1	2016-4-23	2010-01	2004-4-15	1979-04
结束日期	2005-5	2002-3-31	2016-5-25	2010-10	2004-10-26	2004-06
总时长	526天	454天	33天	268 天	195天	303 月
时序周期	周	周	天	周	周	半年
快照图数	76	66	33	39	28	51

方法	Email	Enron	DNC	MAN	UCI	LEM
Last	0.753 5	0.605 6	0.701 1	0.841 5	0.515 2	0.902 1
Average	0.879 3	0.728 2	0.815 6	0.896 4	0.572 4	0.952 0
Reduce	0.895 4	0.773 2	0.825 2	0.902 5	0.615 7	0.953 0
node2vec	0.838 4	0.887 7	0.842 0	0.602 8	0.522 7	0.744 4
LINE	0.825 3	0.878 4	0.862 4	0.606 8	0.650 7	0.771 3
DySAT	0.860 3	0.788 5	0.837 6	0.902 0	0.718 7	0.835 2
EvolveGCN	0.750 3	0.634 7	0.878 9	0.801 6	0.681 0	0.896 9
S_ci	0.852 4	0.693 8	0.780 9	0.906 1	0.604 0	0.842 9
S_com	0.950 6	0.899 3	0.911 7	0.901 9	0.846 8	0.951 4
S_mff	0.951 8	0.907 7	0.912 0	0.909 2	0.847 1	0.956 3

Temporal link prediction method based on community multi-features fusion and embedded representation

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 44

Related Articles 2

Metrics

Recommended 0

[1]	Yuan LI, Yunpeng WANG, Tao LI, Baoqiang MA. Webshell malicious traffic detection method based on multi-feature fusion [J]. Chinese Journal of Network and Information Security, 2021, 7(6): 143-154.
[2]	Xiao YANG,Xiuzhen CHEN,Jin MA,Haozhe LIANG,Shenghong LI. User interests-based microblog tracing algorithm [J]. Chinese Journal of Network and Information Security, 2020, 6(6): 164-173.