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

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

摘要/Abstract

摘要：

时序动态网络在静态网络基础上综合了时间属性的概念，包含了网络结构的复杂性、动态性等内涵，是研究复杂网络链路预测问题的较优思维对象，因在现实世界中具有较高应用价值而备受关注。目前大部分传统方法研究对象仍局限于静态网络，存在对网络时域演化信息利用不充分、时间复杂度较高等问题。结合社会学理论，提出一种基于社团多特征融合嵌入表示的时序链路预测方法，该方法的核心思想是通过分析网络动态演化特性，在社团范围内学习节点的嵌入表示向量，融合多特征以衡量节点间连边的生成概率。利用网络集体影响力的方法对节点和连边的权值进行计算，基于集体影响的连边权值进行社团划分，将网络划分为若干个社团子图，得到基于集体影响的相似性指标。在社团范围内，利用有偏的随机游走，结合梯度优化的Skip-gram方法获取所有节点的嵌入表示向量，得到基于社团范围游走的相似性指标。融合节点的集体影响、社团范围节点的多个中心性特征和学习到的节点表示向量，得到多特征融合的相似性指标，3 种新指标都可以用于衡量节点之间形成连边的概率。对比基于移动平均、嵌入表示、图神经网络等经典时序链路预测方法，在 6 个真实数据集上的实验结果表明，所提基于社团多特征融合的方法在 AUC评价标准下取得更优的预测性能。

关键词: 时序链路预测, 社团特征, 影响力, 多特征, 随机游走, 嵌入表示

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

中图分类号:

TP393

朱宇航, 吉立新, 李英乐, 李海涛, 刘树新. 基于社团多特征融合嵌入表示的时序链路预测方法[J]. 网络与信息安全学报, 2023, 9(1): 67-82.

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.

图/表 12

图1

图2

图3

图4

图5

图6

表1

表2

图7

图8

图9

图10

参考文献 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.

基本特征参数	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