基于三元组结构的有向网链路预测方法

常圣; 马宏; 刘树新

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

您当前的位置：

首页 >

文章列表页 >

基于三元组结构的有向网链路预测方法

专栏：复杂网络环境下的路由技术 | 更新时间：2024-06-03

- 基于三元组结构的有向网链路预测方法
- New method for link prediction in directed networks based on triad patterns
- 网络与信息安全学报 2019年5卷第5期页码：39-47
- 作者机构：
- 作者简介：
  
  [ "常圣（1988- ），男，河南郑州人，国家数字交换系统工程技术研究中心硕士生，主要研究方向为链路预测。" ]
  [ "马宏（1968- ），男，江苏东台人，国家数字交换系统工程技术研究中心研究员，主要研究方向为社会网络分析、电信网关防护。" ]
  [ "刘树新（1987- ），男，山东潍坊人，博士，国家数字交换系统工程技术研究中心助理研究员，主要研究方向为复杂网络、网络信息挖掘。" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61803384)
- DOI：10.11959/j.issn.2096-109x.2019049
  中图分类号： TP393
- 网络首发：2019-10，
  
  纸质出版：2019-10-15
- 稿件说明：
移动端阅览
常圣, 马宏, 刘树新. 基于三元组结构的有向网链路预测方法[J]. 网络与信息安全学报, 2019,5(5):39-47.

Sheng CHANG, Hong MA, Shuxin LIU. New method for link prediction in directed networks based on triad patterns[J]. Chinese Journal of Network and Information Security, 2019, 5(5): 39-47.
常圣, 马宏, 刘树新. 基于三元组结构的有向网链路预测方法[J]. 网络与信息安全学报, 2019,5(5):39-47. DOI： 10.11959/j.issn.2096-109x.2019049.

Sheng CHANG, Hong MA, Shuxin LIU. New method for link prediction in directed networks based on triad patterns[J]. Chinese Journal of Network and Information Security, 2019, 5(5): 39-47. DOI： 10.11959/j.issn.2096-109x.2019049.

摘要

当前链路预测的研究主要集中在无向网络，然而现实世界中存在大量的有向网络，忽略链路的方向会缺失一些重要信息甚至使预测失去意义，而直接将无向网络的预测方法应用于有向网络又存在预测精度降低的问题。为此，提出了一个基于三元组的有向网络链路预测算法，该算法针对有向网络和无向网络三元组结构的不同，应用势理论对三元组进行筛选，通过统计分析不同三元组闭合的可能性，以网络整体三元组闭合指数作为权重计算节点间的相似性。在9个真实数据集上的实验表明，所提方法比基准方法的预测精度提高了4.3%。

Abstract

Almost all current studies on link prediction problem focus on undirected networks.Unfortunately

many complex networks in the real world are directed.Ignoring the direction of a link will overlook some important information or even make the prediction meaningless.Directly applying the methods for undirected networks to directed networks will reduce the accuracy of prediction.A new method for link prediction in directed networks based on triad patterns was proposed.The proposed metric compare the difference of triad structures between undirected and directed networks and use potential theory to filter the triad patterns.By statistics of triad closeness in various networks

new method calculate the similarity between nodes using the triad closeness index of a network as the weight for different triad patterns.Experiments on nine real networks show that accuracy of proposed method is 4.3% better than benchmark methods.

关键词

Keywords

references

LYU L , ZHOU T . Link prediction in complex networks:a survey [J ] . Physica A:Statistical Mechanics And Its Applications , 2011 , 390 ( 6 ): 1150 - 1170 .

吕琳媛 , 周涛 . 链路预测 [M ] . 北京 : 教育出版社 , 2013 .

LYU L Y , ZHOU T . Link prediction [M ] . Beijing : Higher Education PressPress , 2013 .

CLAUSET A , MOORE C , NEWMAN M E J . Hierarchical structure and the prediction of missing links in networks [J ] . Nature , 2008 , 453 : 98 - 101 .

GUIMERA R , SALES-PARDO M . Missing and spurious interactions and the reconstruction of complex networks [J ] . Proc Natl Sci Acad USA , 2009 , 106 ( 52 ): 22073 - 22078 .

ADAMIC L A , ADAR E . Friends and neighbors on the Web [J ] . Social Networks , 2003 , 25 ( 3 ): 211 - 230 .

SALTON G , MCGILL M J . Introduction to modern information retrieval [M ] . Auckland : MuGraw-HillPress , 1983 .

JACCARD P . Etude comparative de la distribution floraledansune portion des Alpes et des Jura [J ] . Bulletin de la SociétéVaudoise des Science Naturelles , 1901 , 37 : 547 - 579 .

ZHOU T , LYU L , ZHANG Y C . Predicting missing links via local information [J ] . EurPhys J B , 2009 , 71 ( 4 ): 623 - 630 .

KATZ L . A new status index derived from sociometric analysis [J ] . Psychometrika , 1953 , 18 ( 1 ): 39 - 43 .

BRIN S , PAGE L . The anatomy of a large-scale hypertextual Web search engine [J ] . ComputNetw＆ ISDN Syst , 1998 , 30 ( 1-7 ): 107 - 117 .

NARAYANAN A , SHI E , RUBINSTEIN B I P . Link prediction by de-anonymization:how we won the kaggle social network challenge [C ] // The 2011 International Joint Conference on Neural Networks (IJCNN) . 2011 : 1825 - 1834 .

CORLETTE D , SHIPMAN F M . Link prediction applied to an open large-scale online social network [C ] // The 21st ACM Conference on Hypertext and Hypermedia . 2010 : 135 - 140 .

LICHTENWALTER R N , LUSSIER J T , CHAWLA N V . New perspectives and methods in link prediction [C ] // The 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . 2010 : 243 - 252 .

ZHANG Q M , LYU L , WANG W Q , et al . Potential theory for directed networks [J ] . PloS One , 2013 , 8 ( 2 ):e55437.

AGHABOZORGI F , KHAYYAMBASHI M R . A new similarity measure for link prediction based on local structures in social networks [J ] . Physica A:Statistical Mechanics and its Applications , 2018 , 501 : 12 - 23 .

BÜTÜN E , KAYA M , ALHAJJ R . Extension of neighbor-based link prediction methods for directed,weighted and temporal social networks [J ] . Information Sciences , 2018 .

YIN H , BENSON A R , LESKOVEC J , et al . Local higher-order graph clustering [C ] // The 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . 2017 : 555 - 564 .

YAO Y , ZHANG R , YANG F , et al . Link prediction in complex networks based on the interactions among paths [J ] . Physica A:Statistical Mechanics and its Applications , 2018 .

BAIRD D , LUCZKOVICH J , CHRISTIAN R R . Assessment of spatial and temporal variability in ecosystem attributes of the st marks national wildlife refuge,apalachee bay,florida [J ] . Estuarine,Coastal and Shelf Science , 1998 , 47 ( 3 ): 329 - 349 .

WATTS D J , STROGATZ S H . Collective dynamics of“small-world” networks [J ] . Nature , 1998 , 393 ( 6684 ):440.

ADAMIC L A , GLANCE N . The political blogosphere and the 2004 US election:divided they blog [C ] // The 3rd International Workshop on Link discovery . 2005 : 36 - 43 .

LESKOVEC J , HUTTENLOCHER D , KLEINBERG J . Predicting positive and negative links in online social networks [C ] // The 19th International Conference on World Wide Web . 2010 : 641 - 650 .

LESKOVEC J , KLEINBERG J , FALOUTSOS C . Graph evolution:densification and shrinking diameters [J ] . ACM Transactions on Knowledge Discovery from Data (TKDD) , 2007 , 1 ( 1 ):2.

HANELY J A , MCNEIL B J . The meaning and use of the area under a receiver operating characteristic (ROC) curve [J ] . Radiology , 1982 , 143 : 29 - 36 .

吴祖峰 , 梁棋 , 刘峤 , 等 . 基于 AdaBoost 的链路预测优化算法 [J ] . 通信学报 , 2014 , 35 ( 3 ): 116 - 123 .

WU Z F , LIANG Q , LIU Q , et al . Modified link prediction algrithm based on AdaBoost [J ] . Journal on Communications , 2014 , 35 ( 3 ): 116 - 123 .

SORENSEN T . A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons [J ] . BiolSkr , 1948 , 5 ( 4 ): 1 - 34 .

RAVASZ E , SOMERA A L , MONGRU D A , et al . Hierarchical organization of modularity in metabolic networks [J ] . Science , 2002 , 297 ( 5586 ): 1553 - 1555 .

LEICHT E A , HOLME P , NEWMAN M E J . Vertex similarity in networks [J ] . Phys Rev E , 2006 , 73 :026120.

DEVI S J , SINGH B . Analysis of link prediction in directed and weighted social network structure [C ] // The International Symposium on Intelligent Systems Technologies and Applications . 2017 : 1 - 13 .

浏览量

778

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于SCL-CMM模型的超网络链路预测方法

面向强稀疏性移动社交网络的链路预测深度学习方法

基于节点匹配度的动态网络链路预测方法

基于广义共同邻居的有向网络链路预测方法

基于复杂网络动力学模型的链路预测方法