通信学报 ›› 2020, Vol. 41 ›› Issue (6): 34-50.doi: 10.11959/j.issn.1000-436x.2020125
吴翼腾1,于洪涛1,黄瑞阳1,李华巍2
修回日期:
2020-03-06
出版日期:
2020-06-25
发布日期:
2020-07-04
作者简介:
吴翼腾(1992- ),男,山东乐陵人,信息工程大学博士生,主要研究方向为信息内容安全、对抗机器学习|于洪涛(1970- ),男,辽宁丹东人,博士,信息工程大学研究员、博士生导师,主要研究方向为大数据与人工智能|黄瑞阳(1986- ),男,福建漳州人,博士,信息工程大学副研究员,主要研究方向为知识图谱与文本挖掘|李华巍(1983- ),男,吉林省吉林市人,92538 部队工程师,主要研究方向为大数据
基金资助:
Yiteng WU1,Hongtao YU1,Ruiyang HUANG1,Huawei LI2
Revised:
2020-03-06
Online:
2020-06-25
Published:
2020-07-04
Supported by:
摘要:
对链路预测组合方法是否存在理论极限以及如何抵近极限开展研究。从是否使用多维度信息或是否直接定义多维度信息之间关系的角度,将链路预测方法分为单机制方法和组合方法。采用简单函数列逼近可测函数的方法,得出链路预测组合方法的理论极限定理;提出使组合方法准确性达到理论上限的组合规则,并给出所提组合规则的几何解释和针对极限定理的仿真示例说明。极限定理揭示了组合方法的本质和组合方法相比单机制方法具有更高准确性及稳健性的原因。
中图分类号:
吴翼腾,于洪涛,黄瑞阳,李华巍. 采用组合方法进行链路预测的理论极限研究[J]. 通信学报, 2020, 41(6): 34-50.
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.
表1
多元正态分布的仿真结果"
参数 | 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 |
表2
构建分布的仿真结果"
参数 | 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 |
[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. |
[1] | 孙雁飞, 尹嘉峥, 亓晋, 胡筱旋, 陈梦婷, 董振江. 基于动态图嵌入的车联网拓扑控制[J]. 通信学报, 2022, 43(6): 133-142. |
[2] | 顾秋阳, 吴宝, 池仁勇. 基于高阶路径相似度的复杂网络链路预测方法[J]. 通信学报, 2021, 42(7): 61-69. |
[3] | 舒坚, 王启宁, 刘琳岚. 基于深度图嵌入的无人机自组网链路预测[J]. 通信学报, 2021, 42(7): 137-149. |
[4] | 顾秋阳, 吴宝, 孙兆洋, 池仁勇. 基于改进灰狼优化的复杂网络重要节点识别算法[J]. 通信学报, 2021, 42(6): 72-83. |
[5] | 朱近康, 柴名扬, 周武旸. 面向B5G/6G的三三三网络体系架构和优化学习机制[J]. 通信学报, 2021, 42(4): 62-75. |
[6] | 韩涛, 贺威, 代俊, 左勇, 杨旸, 葛晓虎. 基于无标度网络的车联网连通性研究[J]. 通信学报, 2021, 42(4): 100-108. |
[7] | 张胜,戴维凯,吴锋,蓝文祥. 基于分形特性的复杂网络全局效率估计方法[J]. 通信学报, 2020, 41(7): 204-212. |
[8] | 刘树新,李星,陈鸿昶,王凯. 基于资源传输匹配度的复杂网络链路预测方法[J]. 通信学报, 2020, 41(6): 70-79. |
[9] | 顾秋阳, 琚春华, 吴功兴. 基于子图演化与改进蚁群优化算法的社交网络链路预测方法[J]. 通信学报, 2020, 41(12): 21-35. |
[10] | 项英倬,徐正国,游凌. 基于节点通信行为时序的指控信息流挖掘算法[J]. 通信学报, 2019, 40(9): 51-60. |
[11] | 李凤华,陈天柱,王震,张林杰,史国振,郭云川. 复杂网络环境下跨网访问控制机制[J]. 通信学报, 2018, 39(2): 1-10. |
[12] | 邓琨,李文平,余法红,张健沛. 基于多核心标签传播的复杂网络重叠社区识别方法[J]. 通信学报, 2017, 38(2): 53-66. |
[13] | 张洛什,王大伟,薛一波. 基于流感知的复杂网络应用识别模型[J]. 通信学报, 2015, 36(3): 161-169. |
[14] | 刘君,乔建志. 复杂网络中k-核与网络聚集系数的关联性研究[J]. 通信学报, 2015, 36(1): 224-229. |
[15] | 牛建伟,戴彬,童超,霍冠英,彭井. 基于Laplace矩阵Jordan型的复杂网络聚类算法[J]. 通信学报, 2014, 35(3): 11-21. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||
|