采用组合方法进行链路预测的理论极限研究

吴翼腾; 于洪涛; 黄瑞阳; 李华巍

doi:10.11959/j.issn.1000-436x.2020125

您当前的位置：

首页 >

文章列表页 >

采用组合方法进行链路预测的理论极限研究

学术论文 | 更新时间：2024-06-05

- 采用组合方法进行链路预测的理论极限研究
- Theoretical limit of link prediction using a combination method
- 通信学报 2020年41卷第6期页码：34-50
- 作者机构：
  
  1. 信息工程大学，河南郑州 450002
  2. 92538部队，辽宁旅顺 116041
- 作者简介：
  
  [ "吴翼腾（1992- ），男，山东乐陵人，信息工程大学博士生，主要研究方向为信息内容安全、对抗机器学习" ]
  [ "于洪涛（1970- ），男，辽宁丹东人，博士，信息工程大学研究员、博士生导师，主要研究方向为大数据与人工智能" ]
  [ "黄瑞阳（1986- ），男，福建漳州人，博士，信息工程大学副研究员，主要研究方向为知识图谱与文本挖掘" ]
  [ "李华巍（1983- ），男，吉林省吉林市人，92538 部队工程师，主要研究方向为大数据" ]
- 基金信息：
  
  国家自然科学基金资助项目(61601513);郑州市协同创新重大专项基金资助项目(162/32410218)
- DOI：10.11959/j.issn.1000-436x.2020125
  中图分类号： TP393
- 网络出版日期：2020-06，
  
  纸质出版日期：2020-06-25
- 稿件说明：
移动端阅览
吴翼腾, 于洪涛, 黄瑞阳, 等. 采用组合方法进行链路预测的理论极限研究[J]. 通信学报, 2020,41(6):34-50.

Yiteng WU, Hongtao YU, Ruiyang HUANG, et al. Theoretical limit of link prediction using a combination method[J]. Journal on communications, 2020, 41(6): 34-50.
吴翼腾, 于洪涛, 黄瑞阳, 等. 采用组合方法进行链路预测的理论极限研究[J]. 通信学报, 2020,41(6):34-50. DOI： 10.11959/j.issn.1000-436x.2020125.

Yiteng WU, Hongtao YU, Ruiyang HUANG, et al. Theoretical limit of link prediction using a combination method[J]. Journal on communications, 2020, 41(6): 34-50. DOI： 10.11959/j.issn.1000-436x.2020125.

摘要

对链路预测组合方法是否存在理论极限以及如何抵近极限开展研究。从是否使用多维度信息或是否直接定义多维度信息之间关系的角度，将链路预测方法分为单机制方法和组合方法。采用简单函数列逼近可测函数的方法，得出链路预测组合方法的理论极限定理；提出使组合方法准确性达到理论上限的组合规则，并给出所提组合规则的几何解释和针对极限定理的仿真示例说明。极限定理揭示了组合方法的本质和组合方法相比单机制方法具有更高准确性及稳健性的原因。

Abstract

The problem that whether there a theoretical limit exists for link prediction combination methods and how to approximate was investigated.Link prediction methods were divided into single or combination methods

based on whether multidimension information was used

or whether the relation of multidimension information was defined directly.Limit theorems for link prediction by approximating a measurable function by a simple function sequence were provided.Combination rule and corresponding geometric interpretations and simulation examples for limit theorems were also provided.Limit theorems show why combination methods have higher accuracy and robustness than single methods.

关键词

Keywords

references

SEIFE C . What are the limits of conventional computing [J ] . Science , 2005 , 309 ( 5731 ):96.

SHANNON C E . A mathematical theory of communication [J ] . ACM SIGMOBILE Mobile Computing and Communications Review , 2001 , 5 ( 1 ): 3 - 55 .

DONOHO D L , STARK P B . Uncertainty principles and signal recovery [J ] . SIAM Journal on Applied Mathematics , 1989 , 49 ( 3 ): 906 - 931 .

LANDAUER R . Irreversibility and heat generation in the computing process [J ] . IBM Journal of Research and Development , 1961 , 5 ( 3 ): 183 - 191 .

BÉRUT A , ARAKELYAN A , PETROSYAN A , et al . Experimental verification of Landauer’s principle linking information and thermodynamics [J ] . Nature , 2012 , 483 ( 7388 ): 187 - 189 .

LIBEN-NOWELL D , KLEINBERG J . The link-prediction problem for social networks [J ] . Journal of the American Society for Information Science ＆ Technology , 2007 , 58 ( 7 ): 1019 - 1031 .

ALON U . Network motifs:theory and experimental approaches [J ] . Nature Reviews Genetics , 2007 , 8 ( 6 ): 450 - 461 .

LYU L , PAN L , ZHOU T , et al . Toward link predictability of complex networks [J ] . Proceedings of the National Academy of Sciences , 2015 , 112 ( 8 ): 2325 - 2330 .

WU Y T , YU H T , HUANG R Y , et al . A fusion link prediction method based on limit theorem [J ] . Applied Sciences , 2017 , 8 ( 1 ):32.

FRANÇOIS L , WHITE H C . Structural equivalence of individuals in social networks [J ] . Social Networks , 1977 , 1 ( 1 ): 67 - 98 .

BARABASI A L , ALBERT R . Emergence of scaling in random networks [J ] . Science , 1999 , 286 ( 5439 ): 509 - 512 .

ZHOU T , LYU L , ZHANG Y C . Predicting missing links via local information [J ] . The European Physical Journal B-Condensed Matter and Complex Systems , 2009 , 71 ( 4 ): 623 - 630 .

MA C , BAO Z K , ZHANG H F . Improving link prediction in complex networks by adaptively exploiting multiple structural features of networks [J ] . Physics Letters A , 2017 , 381 ( 39 ): 3369 - 3376 .

YAO Y , ZHANG R , YANG F , et al . Link prediction based on local weighted paths for complex networks [J ] . International Journal of Modern Physics C , 2017 , 28 ( 4 ): 1 - 23 .

LIU S X , JI X S , LIU C X , et al . Similarity indices based on link weight assignment for link prediction of unweighted complex networks [J ] . International Journal of Modern Physics B , 2016 :1650254.

刘树新 , 季新生 , 刘彩霞 , 等 . 局部拓扑信息耦合促进网络演化 [J ] . 电子与信息学报 , 2016 , 38 ( 9 ): 2180 - 2187 .

LIU S X , JI X S , LIU C X , et al . Information coupling of local topology promoting the network evolution [J ] . Journal of Electronics ＆ Information Technology , 2016 , 38 ( 9 ): 2180 - 2187 .

KUMAR A , SINGH S S , SINGH K , et al . Level-2 node clustering coefficient-based link prediction [J ] . Applied Intelligence , 2019 ( 1 ): 1 - 18 .

BISWAS A , BISWAS B . Community-based link prediction [J ] . Multimedia Tools and Applications , 2017 , 76 ( 18 ): 18619 - 18639 .

DE B C , POWER E A , LARREMORE D B , et al . Community detection,link prediction,and layer interdependence in multilayer networks [J ] . Physical Review E , 2017 , 95 ( 4-1 ):042317.

MAN G , LING C , BIN L , et al . A link prediction algorithm based on low-rank matrix completion [J ] . Applied Intelligence , 2018 , 48 : 4531 - 4550 .

韦布 , 科普西 . 统计模式识别:第三版 [M ] . 王萍,译.北京 : 电子工业出版社 , 2015 .

WEBB A R , COPSEY K D . Statistical pattern recognition [M ] . 3rd ed.WANG P,transl . Beijing : Publishing House of Electronics IndustryPress , 2015 .

HOLLAND P W , LASKEY K B , LEINHARDT S . Stochastic blockmodels:first steps [J ] . Social Networks , 1983 , 5 ( 2 ): 109 - 137 .

GUIMERÀ R , SALES-PARDO M . Missing and spurious interactions and the reconstruction of complex networks [J ] . Proceedings of the National Academy of Sciences , 2009 , 106 ( 52 ): 22073 - 22078 .

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

HE Y , LIU J N K , HU Y , et al . OWA operator based link prediction ensemble for social network [J ] . Expert Systems with Applications , 2015 , 42 ( 1 ): 21 - 50 .

YU H T , WANG S H , MA Q Q . Link prediction algorithm based on the Choquet fuzzy integral [J ] . Intelligent Data Analysis , 2016 , 20 ( 4 ): 809 - 824 .

刘冶 , 朱蔚恒 , 潘炎 , 等 . 基于低秩和稀疏矩阵分解的多源融合链接预测算法 [J ] . 计算机研究与发展 , 2015 , 52 ( 2 ): 423 - 436 .

LIU Y , ZHU W H , PAN Y , et al . Multiple sources fusion for link prediction via low-rank and sparse matrix decomposition [J ] . Journal of Computer Research and Development , 2015 , 52 ( 2 ): 423 - 436 .

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

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

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 .

SARUKKAI R R . Link prediction and path analysis using Markov chains [J ] . Computer Networks , 2000 , 33 ( 1 ): 377 - 386 .

詹姆斯 . 统计学习导论 [M ] . 王星,译.北京 : 机械工业出版社 , 2015 .

JAMES G . An introduction to statistical learning [M ] . WANG X,transl . Beijing : China Machine PressPress , 2015 .

WANG Y , YAO Y , TONG H , et al . A brief review of network embedding [J ] . Big Data Mining and Analytics , 2019 , 2 ( 1 ): 35 - 47 .

ZHOU J , CUI G , ZHANG Z , et al . Graph neural networks:a review of methods and applications [J ] . arXiv Preprint,arXiv:1812.08434 , 2018

WU Z , PAN S , CHEN F , et al . A comprehensive survey on graph neural networks [J ] . IEEE Transactions on Neural Networks and Learning Systems , 2020 : 1 - 21 .

LIAO L , HE X , ZHANG H , et al . Attributed social network embedding [J ] . IEEE Transactions on Knowledge ＆ Data Engineering , 2018 , 30 : 2257 - 2270 .

CHEN T , SUN Y . Task-guided and path-augmented heterogeneous network embedding for author identification [C ] // 10th ACM International Conference on Web Search and Data Mining . New York:ACM Press , 2017 : 295 - 304 .

WANG Z , CHEN C , LI W . Predictive network representation learning for link prediction [C ] // International ACM SIGIR Conference on Research and Development in Information Retrieval . New York:ACM Press , 2017 : 969 - 972 .

BRADLEY A P . The use of the area under the ROC curve in the evaluation of machine learning algorithms [J ] . Pattern Recognition , 1997 , 30 ( 7 ): 1145 - 1159 .

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

FAWCETT T . An introduction to ROC analysis [J ] . Pattern Recognition Letters , 2006 , 27 ( 8 ): 861 - 874 .

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 ] . 王忠玉,卜长江,译.北京 : 机械工业出版社 , 2015 .

HOGG R V , CRAIG A T . Introduction to mathematical statistics [M ] . WANG Z Y,BU C J,transl . Beijing : China Machine PressPress , 2015 .

NEYMAN J , PEARSON E S . The testing of statistical hypotheses in relation to probabilities a priori [C ] // Mathematical Proceedings of the Cambridge Philosophical Society . Cambridge:Cambridge University Press , 1933 .

MAYO D G , SPANOS A . Severe testing as a basic concept in a Neyman-Pearson philosophy of induction [J ] . The British Journal for the Philosophy of Science , 2006 , 57 ( 2 ): 323 - 357 .

浏览量

685

下载量

CSCD

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

提交

工具集

关联资源

基于高阶路径相似度的复杂网络链路预测方法

基于资源传输匹配度的复杂网络链路预测方法

基于动态图嵌入的车联网拓扑控制

基于深度图嵌入的无人机自组网链路预测

基于改进灰狼优化的复杂网络重要节点识别算法