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

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

Abstract

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.

Key words: complex network, link prediction, combination method, theoretical limit

CLC Number:

TP393

Yiteng WU,Hongtao YU,Ruiyang HUANG,Huawei LI. Theoretical limit of link prediction using a combination method[J]. Journal on Communications, 2020, 41(6): 34-50.

Figures/Tables 6

References 44

[1]	SEIFE C . What are the limits of conventional computing[J]. Science, 2005,309(5731):96.
[2]	SHANNON C E . A mathematical theory of communication[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2001,5(1): 3-55.
[3]	DONOHO D L , STARK P B . Uncertainty principles and signal recovery[J]. SIAM Journal on Applied Mathematics, 1989,49(3): 906-931.
[4]	LANDAUER R . Irreversibility and heat generation in the computing process[J]. IBM Journal of Research and Development, 1961,5(3): 183-191.
[5]	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.
[6]	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.
[7]	ALON U . Network motifs:theory and experimental approaches[J]. Nature Reviews Genetics, 2007,8(6): 450-461.
[8]	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.
[9]	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.
[10]	FRAN?OIS L , WHITE H C . Structural equivalence of individuals in social networks[J]. Social Networks, 1977,1(1): 67-98.
[11]	BARABASI A L , ALBERT R . Emergence of scaling in random networks[J]. Science, 1999,286(5439): 509-512.
[12]	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.
[13]	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.
[14]	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.
[15]	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.
[16]	刘树新, 季新生, 刘彩霞 ,等. 局部拓扑信息耦合促进网络演化[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.
[17]	KUMAR A , SINGH S S , SINGH K ,et al. Level-2 node clustering coefficient-based link prediction[J]. Applied Intelligence, 2019(1): 1-18.
[18]	BISWAS A , BISWAS B . Community-based link prediction[J]. Multimedia Tools and Applications, 2017,76(18): 18619-18639.
[19]	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.
[20]	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.
[21]	韦布, 科普西 . 统计模式识别:第三版[M]. 王萍,译.北京: 电子工业出版社, 2015.
	WEBB A R , COPSEY K D . Statistical pattern recognition[M]. 3rd ed.WANG P,transl. Beijing: Publishing House of Electronics IndustryPress, 2015.
[22]	HOLLAND P W , LASKEY K B , LEINHARDT S . Stochastic blockmodels:first steps[J]. Social Networks, 1983,5(2): 109-137.
[23]	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.
[24]	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.
[25]	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.
[26]	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.
[27]	刘冶, 朱蔚恒, 潘炎 ,等. 基于低秩和稀疏矩阵分解的多源融合链接预测算法[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.
[28]	吴祖峰, 梁棋, 刘峤 ,等. 基于 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.
[29]	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.
[30]	SARUKKAI R R . Link prediction and path analysis using Markov chains[J]. Computer Networks, 2000,33(1): 377-386.
[31]	詹姆斯 . 统计学习导论[M]. 王星,译.北京: 机械工业出版社, 2015.
	JAMES G . An introduction to statistical learning[M]. WANG X,transl. Beijing: China Machine PressPress, 2015.
[32]	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.
[33]	ZHOU J , CUI G , ZHANG Z ,et al. Graph neural networks:a review of methods and applications[J]. arXiv Preprint,arXiv:1812.08434, 2018
[34]	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.
[35]	LIAO L , HE X , ZHANG H ,et al. Attributed social network embedding[J]. IEEE Transactions on Knowledge ＆ Data Engineering, 2018,30: 2257-2270.
[36]	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.
[37]	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.
[38]	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.
[39]	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.
[40]	FAWCETT T . An introduction to ROC analysis[J]. Pattern Recognition Letters, 2006,27(8): 861-874.
[41]	LYU L , ZHOU T . Link prediction in complex networks:a survey[J]. Physica A:Statistical Mechanics and Its Applications, 2011,390(6): 1150-1170.
[42]	豪格, 克莱格 . 数理统计导论[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.
[43]	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.
[44]	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.

Metrics

Recommended 0

No Suggested Reading articles found!

参数	f :Θ=Θ _1f		f :Θ=Θ _{2 f}
	g:Θ=Θ_1g		g:Θ=Θ_2g
	AUC	Precision	AUC	Precision
维度1	0.554	0.047	0.569	0.114
维度2	0.566	0.015	0.660	0.140
维度3	0.547	0.014	0.604	0.081
维度4	0.585	0.027	0.622	0.038
绝对得分的求和规则	0.501	0.002	0.500	0.008
求和规则1	0.612	0.047	0.767	0.185
求和规则2	0.612	0.044	0.766	0.169
绝对得分的乘积规则	0.479	0.002	0.499	0.005
乘积规则	0.610	0.036	0.763	0.132
朴素贝叶斯	0.610	0.038	0.765	0.153
逻辑回归	0.668	0.020	0.676	0.051
理论极限	0.738	0.120	0.792	0.241
单调减函数变换	0.262	—	0.208	—
单调增函数变换	0.738	0.120	0.792	0.241

参数	f :Θ=Θ _1f g:Θ=Θ_1g		f :Θ=Θ _{2 f} g:Θ=Θ_2g		f :Θ=Θ _{3 f} g:Θ=Θ_3g
参数	AUC	Precision	AUC	Precision	AUC	Precision
维度1	0.769	0	0.575	0	0.813	0.033
维度2	0.779	0.025	0.813	0.175	0.744	0.021
维度3	0.709	0	0.671	0.042	0.909	0.048
维度4	0.923	0.103	0.744	0.072	0.803	0.112
绝对得分的求和规则	0.529	0	0.503	0	0.514	0.001
求和规则1	0.834	0.035	0.687	0.117	0.790	0.058
求和规则2	0.831	0	0.688	0.104	0.798	0.106
绝对得分的乘积规则	0.531	0	0.508	0	0.576	0.002
乘积规则	0.836	0	0.710	0.068	0.837	0.134
朴素贝叶斯	0.838	0.017	0.710	0.108	0.830	0.100
逻辑回归	0.983	0.039	0.925	0.082	0.860	0.030
理论极限	0.999	0.482	0.991	0.461	0.972	0.185
单调减函数变换	0.001	—	0.009	—	0.028	—
单调增函数变换	0.999	0.482	0.991	0.461	0.972	0.185

Theoretical limit of link prediction using a combination method

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 44

Related Articles 15

Metrics

Recommended 0

[1]	Yanfei SUN, Jiazheng YIN, Jin QI, Xiaoxuan HU, Mengting CHEN, Zhenjiang DONG. Topology control based on dynamic graph embedding in Internet of vehicles [J]. Journal on Communications, 2022, 43(6): 133-142.
[2]	Rong QIAN, Jianting XU, Kejun ZHANG, Hongyu DONG, Fangyuan XING. Research on HMM based link prediction method in heterogeneous network [J]. Journal on Communications, 2022, 43(5): 214-225.
[3]	Qiuyang GU, Bao WU, Renyong CHI. Link prediction method based on the similarity of high path [J]. Journal on Communications, 2021, 42(7): 61-69.
[4]	Jian SHU, Qining WANG, Linlan LIU. UAV ad hoc network link prediction based on deep graph embedding [J]. Journal on Communications, 2021, 42(7): 137-149.
[5]	Qiuyang GU, Bao WU, Zhaoyang SUN, Renyong CHI. Key node identification algorithm for complex network based on improved grey wolf optimization [J]. Journal on Communications, 2021, 42(6): 72-83.
[6]	Tao HAN, Wei HE, Jun DAI, Yong ZUO, Yang YANG, Xiaohu GE. Connectivity analysis of IoV based on scale-free network [J]. Journal on Communications, 2021, 42(4): 100-108.
[7]	Jinkang ZHU, Mingyang CHAI, Wuyang ZHOU. Three-three-three network architecture and learning optimization mechanism for B5G/6G [J]. Journal on Communications, 2021, 42(4): 62-75.
[8]	Xiaojuan ZHAO, Yan JIA, Aiping LI, Kai CHEN. Research on link prediction model based on hierarchical attention mechanism [J]. Journal on Communications, 2021, 42(3): 36-44.
[9]	Sheng ZHANG,Weikai DAI,Feng WU,Wenxiang LAN. Global efficiency estimation method of complex network based on fractal property [J]. Journal on Communications, 2020, 41(7): 204-212.
[10]	Shuxin LIU,Xing LI,Hongchang CHEN,Kai WANG. Link prediction method based on matching degree of resource transmission for complex network [J]. Journal on Communications, 2020, 41(6): 70-79.
[11]	Qiuyang GU, Chunhua JU, Gongxing WU. Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm [J]. Journal on Communications, 2020, 41(12): 21-35.
[12]	Yingzhuo XIANG,Zhengguo XU,Ling YOU. Instruction flow mining algorithm based on the temporal sequence of node communication actions [J]. Journal on Communications, 2019, 40(9): 51-60.
[13]	Fenghua LI,Tianzhu CHEN,Zhen WANG,Linjie ZHANG,Guozhen SHI,Yunchuan GUO. Cross-network access control mechanism for complex network environment [J]. Journal on Communications, 2018, 39(2): 1-10.
[14]	Kun DENG,Wen-ping LI,Fa-hong YU,Jian-pei ZHANG. Overlapping community detection in complex networks based on multi kernel label propagation [J]. Journal on Communications, 2017, 38(2): 53-66.
[15]	Jun LIU,Jian-zhong QIAO. Research on relevance between k-core and clustering coefficient in complex network [J]. Journal on Communications, 2015, 36(1): 224-229.