基于自我中心网络结构特征和网络表示学习的链路预测算法

doi:10.11896/jsjkx.201200231

摘要/Abstract

摘要： 链路预测是网络分析与挖掘领域中备受关注的研究方向。链路预测算法所预测的网络中的缺失连接实际上是一种数据挖掘的过程,而推断的将来可能产生的连接则与网络的发展演化相关。因此,如何提高链路预测的精确度是一项有意义且具有挑战性的研究。基于自我中心网络分解和社区聚类的最新研究,提出一种基于自我中心网络结构特征和网络表示学习的链路预测算法(Ego-Embedding)。Ego-Embedding将原网络转换成角色图,再结合网络的微观结构信息和上下文信息重构嵌入过程,为每一个节点学习一个或多个向量表示,使向量表示更准确地描述网络节点信息,从而提高链路预测的精确度。在3个公开数据集(Facebook,PPI-Yeast和ca-HepTh)上进行实验仿真,并使用AUC作为评价指标,仿真结果表明,算法Ego-Embedding的表现均优于5个实验对比方法(CN,AA,Node2vec,M-NMF和Splitter),且最高将链路预测的错误率减少了约47%。

关键词: Ego-Embedding, 角色分解, 链路预测, 网络表示学习, 自我中心网络

Abstract: Link prediction is a research direction that has attracted much attention in the field of network analysis and mining.The link prediction algorithm predicts the missing connections in the network,which is actually a process of data mining,and the inferred possible future connections are related to the development and evolution of the network.Therefore,how to improve the accuracy of link prediction is a meaningful and challenging research.Based on the latest research on ego network decomposition and community clustering,a link prediction algorithm (Ego-Embedding) is proposed,which is based on ego network structure characteristics and network representation learning.Ego-Embedding converts the original network into a persona graph,and then reconstructs the embedding process by combining the microstructure information and context information of the network,learning one or more vector representations for each node,so that the vector representation can describe the node information more accurately,thereby improving the accuracy of link prediction.This paper conducts experimental simulations on three public data sets (Facebook,PPI-Yeast,ca-HepTh),and uses AUC as the evaluation index.The experimental results show that the performance of the algorithm Ego-Embedding is better than the five experimental comparison methods (CN,AA,node2vec,M-NMF,Splitter),and the best link prediction AUC reduces the error by up to 47%.

Key words: Ego network, Ego-Embedding, Link prediction, Network representation learning, Persona decomposition

中图分类号:

TP393

赵曼, 赵加坤, 刘金诺. 基于自我中心网络结构特征和网络表示学习的链路预测算法[J]. 计算机科学, 2021, 48(11A): 211-217. https://doi.org/10.11896/jsjkx.201200231

ZHAO Man, ZHAO Jia-kun, LIU Jin-nuo. Link Prediction Algorithm Based on Ego Networks Structure and Network Representation Learning[J]. Computer Science, 2021, 48(11A): 211-217. https://doi.org/10.11896/jsjkx.201200231

参考文献

[1]LI L,FANG S,BAI S,et al.Effective Link Prediction Based on Community Relationship Strength[J].IEEE Access,2019,7:43233-43248.
[2]LIAO H,MARIANI M S,MEDO M,et al.Ranking in evolving complex networks[J].Physics Reports,2017,689:1-54.
[3]PEROZZI B,SKIENA S .Exact Age Prediction in Social Networks[C]//the 24th International Conference.ACM,2015.
[4]SAID A,ABBASI R A,MAQBOOL O,et al.CC-GA:A Clustering Coefficient based Genetic Algorithm for Detecting Communities in Social Networks[J].Applied Soft Computing,2017,63:59-70.
[5]ABU-EL-HAIJA S,PEROZZI B,AL-RFOU R.Learning EdgeRepresentations via Low-Rank Asymmetric Projections[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management (CIKM'17).NewYork:ACM,2017:1787-1796.
[6]YUAN R,SONG Y R,MENG F R.A Link Prediction Method Based on Weighted Network Topology Weight[J].Computer Science,2020,47(5):273-278.
[7]YANG X H,YU J,ZHANG D.Link prediction algorithm based on local community and node correlation[J].Computer Science,2019,46(1):155-161.
[8]MA C,ZHOU T,ZHANG H F.Playing the role of weak clique property in link prediction:A friend recommendation model[J].Scientific Reports,2016.
[9]ZHANG Q M,XU X K,ZHU Y X,et al.Measuring multiple evolution mechanisms of complex networks[J].Scientific Reports,2015,5(1):10350.
[10]MARTÍNEZ V,BERZAL F,CUBERO J C .A Survey of Link Prediction in Complex Networks[C]//ACM Computing Surveys (CSUR).2016.
[11]CANNISTRACI C V,ALANIS-LOBATO G,RAVASI T .From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J].Scientific Reports,2013,3(1):1613.
[12]HANNEMAN R A,RIDDLE M.Introduction to social network methods.Riverside[D].CA:University of California,Riverside,2005.
[13]EPASTO A,LATTANZI S,MIRROKNI V,et al.Ego-net community mining applied to friend suggestion[J].VLDB,2015,9(4):324-335.
[14]EPASTO A,LATTANZI S,LEME R P .Ego-splitting Framework:from Non-Overlapping to Overlapping Clusters[C]//Acm Sigkdd International Conference on Knowledge Discovery & Data Mining.ACM,2017.
[15]EPASTO A,PEROZZI B .Is a Single Embedding Enough?Learning Node Representations that Capture Multiple Social Contexts[C]//WWW'19.2019:394-404.
[16]GONCALVES B,PERRA N,VESPIGNANI A,et al.Modeling Users' Activity on Twitter Networks:Validation of Dunbar's Number[J].Plos One,2011,6(8):e22656.
[17]FREEMAN L C .Centered graphs and the structure of ego networks[J].Mathematical Social Sciences,1982,3(3):291-304.
[18]MCAULEY J,LESKOVEC J.Learning to Discover Social Circles in Ego Networks[C]//NIPS.2012:539-547.
[19]ARNABOLDI V,CONTI M,PASSARELLA A,et al.Analysis ofEgo Network Structure in Online Social Networks[C]//Ase/ieee International Conference on Social Computing & Ase/ieee International Conference on Privacy.IEEE,2012.
[20]ZHANG Y X,FENG Y X.Overview of Link Prediction Methods and Development[J].Measurement & Control Technology,2019,324(2):12-16.
[21]MIKOLOV T,CHEN K,CORRADO G,et al.Efficient Estimation of Word Representations in Vector Space[C]//International Conference on Learning Representations.2013.
[22]DUNBAR R I M.The Social Brain Hypothesis[J].Evolutionary Anthropology Issues News & Reviews,1998,6(5):178-190.
[23]WANG Q,GAO J,ZHOU T,et al.Critical size of ego communication networks[J].Europhysics Letters,2016(114):58004.
[24]GROVER A,LESKOVEC J .node2vec:Scalable Feature Learning for Networks[C]//the 22nd ACM SIGKDD International Conference.ACM,2016.
[25]PEROZZI B,AL-RFOU R,SKIENA S.DeepWalk:Online Learn-ing of Social Representations[C]//Knowledge Discovery and Data Mining.2014.
[26]MIKOLOV T,SUTSKEVER I,CHEN K,et al.DistributedRepresentations of Words and Phrases and their Compositionali-ty[C]//Proceedings of NIPS.2013.
[27]GAO F,MUSIAL K,GABRYS B.A Community Bridge Boosting Social Network Link Prediction Model[C]//the 2017 IEEE/ACM International Conference.ACM,2017.
[28]NEWMAN M E J.Clustering and preferential attachment ingrowing networks[J].Phys Rev E Stat Nonlin Soft Matter Phys,2001,64(2):025102.
[29]ADAMIC L A,ADAR E.Friends and neighbors on the Web[J].Social Networks,2003,25(3):211-230.
[30]WANG X,CUI P,WANG J,et al.Community Preserving Network Embedding[C]//The 31st AAAI Conference on Artificial Intelligence.2017.
[31]HANELY J A,MCNEIL B J.The meaning and use of the areaunder a receiver operating characteristic(ROC) curve[J].Radiology,1982,143(1):29-36.

相关文章 15

[1]	李勇, 吴京鹏, 张钟颖, 张强. 融合快速注意力机制的节点无特征网络链路预测算法 Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism 计算机科学, 2022, 49(4): 43-48. https://doi.org/10.11896/jsjkx.210800276
[2]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[3]	蒋宗礼, 樊珂, 张津丽. 基于生成对抗网络和元路径的异质网络表示学习 Generative Adversarial Network and Meta-path Based Heterogeneous Network Representation Learning 计算机科学, 2022, 49(1): 133-139. https://doi.org/10.11896/jsjkx.201000179
[4]	龚追飞, 魏传佳. 基于改进AdaBoost算法的复杂网络链路预测 Link Prediction of Complex Network Based on Improved AdaBoost Algorithm 计算机科学, 2021, 48(3): 158-162. https://doi.org/10.11896/jsjkx.200600075
[5]	李鑫超, 李培峰, 朱巧明. 一种基于层级信息优化的有向网络表示学习方法 Directed Network Representation Method Based on Hierarchical Structure Information 计算机科学, 2021, 48(2): 100-104. https://doi.org/10.11896/jsjkx.191200033
[6]	富坤, 赵晓梦, 付紫桐, 高金辉, 马浩然. 基于不完全信息的深度网络表示学习方法 Deep Network Representation Learning Method on Incomplete Information Networks 计算机科学, 2021, 48(12): 212-218. https://doi.org/10.11896/jsjkx.201000015
[7]	龚追飞, 魏传佳. 基于拓扑相似和XGBoost的复杂网络链路预测方法 Complex Network Link Prediction Method Based on Topology Similarity and XGBoost 计算机科学, 2021, 48(12): 226-230. https://doi.org/10.11896/jsjkx.200800026
[8]	潘雨, 邹军华, 王帅辉, 胡谷雨, 潘志松. 基于网络表示学习的深度社团发现方法 Deep Community Detection Algorithm Based on Network Representation Learning 计算机科学, 2021, 48(11A): 198-203. https://doi.org/10.11896/jsjkx.210200113
[9]	黄寿孟. 一种基于监督学习的异构网链路预测模型 Heterogeneous Network Link Prediction Model Based on Supervised Learning 计算机科学, 2021, 48(11A): 111-116. https://doi.org/10.11896/jsjkx.210300030
[10]	丁钰, 魏浩, 潘志松, 刘鑫. 网络表示学习算法综述 Survey of Network Representation Learning 计算机科学, 2020, 47(9): 52-59. https://doi.org/10.11896/jsjkx.190300004
[11]	王慧, 乐孜纯, 龚轩, 武玉坤, 左浩. 基于特征分类的链路预测方法综述 Review of Link Prediction Methods Based on Feature Classification 计算机科学, 2020, 47(8): 302-312. https://doi.org/10.11896/jsjkx.190700136
[12]	黄易, 申国伟, 赵文波, 郭春. 一种基于漏洞威胁模式的网络表示学习算法 Network Representation Learning Algorithm Based on Vulnerability Threat Schema 计算机科学, 2020, 47(7): 292-298. https://doi.org/10.11896/jsjkx.190600156
[13]	蒋宗礼, 李苗苗, 张津丽. 基于融合元路径图卷积的异质网络表示学习 Graph Convolution of Fusion Meta-path Based Heterogeneous Network Representation Learning 计算机科学, 2020, 47(7): 231-235. https://doi.org/10.11896/jsjkx.190600085
[14]	富坤, 仇倩, 赵晓梦, 高金辉. 基于节点演化分阶段优化的事件检测方法 Event Detection Method Based on Node Evolution Staged Optimization 计算机科学, 2020, 47(5): 96-102. https://doi.org/10.11896/jsjkx.190400072
[15]	袁榕, 宋玉蓉, 孟繁荣. 一种基于加权网络拓扑权重的链路预测方法 Link Prediction Method Based on Weighted Network Topology Weight 计算机科学, 2020, 47(5): 265-270. https://doi.org/10.11896/jsjkx.190600031

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed