Theoretical limit of link prediction using a combination method

Yiteng WU; Hongtao YU; Ruiyang HUANG; Huawei LI

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

您当前的位置：

首页 >

文章列表页 >

Theoretical limit of link prediction using a combination method

Papers | 更新时间：2024-06-05

- Theoretical limit of link prediction using a combination method
- Journal on Communications Vol. 41, Issue 6, Pages: 34-50(2020)
- 作者机构：
  
  1. 信息工程大学，河南郑州 450002
  2. 92538部队，辽宁旅顺 116041
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61601513);Major Collaborative Innovation Projects of Zhengzhou(162/32410218)
- DOI：10.11959/j.issn.1000-436x.2020125
  CLC： TP393
- Online First：2020-06，
  
  Published：25 June 2020
- 稿件说明：
移动端阅览
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：

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 .

Views

1380

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Link prediction method based on the similarity of high path

Link prediction method based on matching degree of resource transmission for complex network

Topology control based on dynamic graph embedding in Internet of vehicles

UAV ad hoc network link prediction based on deep graph embedding

Key node identification algorithm for complex network based on improved grey wolf optimization

Related Author

Renyong CHI

Bao WU

Qiuyang GU

Kai WANG

Hongchang CHEN

Xing LI

Shuxin LIU

Zhenjiang DONG

Related Institution

China Institute for Small and Medium Enterprises, Zhejiang University of Technology

School of Management, Zhejiang University of Technology

National Digital Switching System ＆Engineering Technology Research Center

Information Technology Institute,Information Engineering University

College of Computer, Nanjing University of Posts and Telecommunications

AI问答

⁰