Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (9): 2823-2829.DOI: 10.11772/j.issn.1001-9081.2021071326
• Network and communications • Previous Articles Next Articles
Received:
2021-07-23
Revised:
2021-10-22
Accepted:
2021-10-25
Online:
2021-11-01
Published:
2022-09-10
Contact:
Yuyu MENG
About author:
GUO Jing, born in 1997, M. S. candidate. Her research interests include complex network, link prediction.
通讯作者:
孟昱煜
作者简介:
郭静(1997—),女,甘肃白银人,硕士研究生,主要研究方向:复杂网络、链路预测。
CLC Number:
Yuyu MENG, Jing GUO. Link prediction algorithm based on information entropy improved PCA model[J]. Journal of Computer Applications, 2022, 42(9): 2823-2829.
孟昱煜, 郭静. 信息熵改进主成分分析模型的链路预测算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2823-2829.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2021071326
数据集 | |V| | |E| | 〈k〉 | C | D |
---|---|---|---|---|---|
USAir | 332 | 2 126 | 12.810 | 0.749 | 6.00 |
Celegans | 297 | 2 148 | 14.460 | 0.308 | 5.00 |
Router | 5 022 | 6 258 | 2.490 | 0.033 | 15.00 |
Yeast | 2 375 | 11 693 | 9.200 | 0.388 | 15.00 |
PB | 1 222 | 19 021 | 27.360 | 0.360 | 8.00 |
wiki-vote | 7 066 | 103 663 | 14.573 | 0.142 | 4.77 |
Tab. 1 Topological feature parameters of datasets
数据集 | |V| | |E| | 〈k〉 | C | D |
---|---|---|---|---|---|
USAir | 332 | 2 126 | 12.810 | 0.749 | 6.00 |
Celegans | 297 | 2 148 | 14.460 | 0.308 | 5.00 |
Router | 5 022 | 6 258 | 2.490 | 0.033 | 15.00 |
Yeast | 2 375 | 11 693 | 9.200 | 0.388 | 15.00 |
PB | 1 222 | 19 021 | 27.360 | 0.360 | 8.00 |
wiki-vote | 7 066 | 103 663 | 14.573 | 0.142 | 4.77 |
数据集 | 主相似性特征 | ||
---|---|---|---|
USAir | 0.834 9 | 0.114 1 | 0.051 0 |
Celegans | 0.852 1 | 0.090 2 | 0.057 7 |
Router | 0.786 7 | 0.199 3 | 0.014 0 |
Yeast | 0.777 8 | 0.149 6 | 0.072 6 |
PB | 0.893 4 | 0.060 8 | 0.045 8 |
wiki-vote | 0.842 3 | 0.142 9 | 0.014 8 |
Tab. 2 Contribution rates of principal components in different datasets
数据集 | 主相似性特征 | ||
---|---|---|---|
USAir | 0.834 9 | 0.114 1 | 0.051 0 |
Celegans | 0.852 1 | 0.090 2 | 0.057 7 |
Router | 0.786 7 | 0.199 3 | 0.014 0 |
Yeast | 0.777 8 | 0.149 6 | 0.072 6 |
PB | 0.893 4 | 0.060 8 | 0.045 8 |
wiki-vote | 0.842 3 | 0.142 9 | 0.014 8 |
数据集 | 主相似性特征 | ||
---|---|---|---|
USAir | 0.834 9 | 0.949 0 | 1.000 0 |
Celegans | 0.852 1 | 0.9423 | 1.000 0 |
Router | 0.786 7 | 0.986 0 | 1.000 0 |
Yeast | 0.777 8 | 0.927 4 | 1.000 0 |
PB | 0.893 4 | 0.954 2 | 1.000 0 |
wiki-vote | 0.842 3 | 0.985 2 | 1.000 0 |
Tab. 3 Cumulative contribution rate of each principal component in different datasets
数据集 | 主相似性特征 | ||
---|---|---|---|
USAir | 0.834 9 | 0.949 0 | 1.000 0 |
Celegans | 0.852 1 | 0.9423 | 1.000 0 |
Router | 0.786 7 | 0.986 0 | 1.000 0 |
Yeast | 0.777 8 | 0.927 4 | 1.000 0 |
PB | 0.893 4 | 0.954 2 | 1.000 0 |
wiki-vote | 0.842 3 | 0.985 2 | 1.000 0 |
算法 | 数据集 | |||||
---|---|---|---|---|---|---|
USAir | Celegans | Router | Yeast | PB | wiki-vote | |
CN | 0.954 2 | 0.846 6 | 0.652 2 | 0.915 1 | 0.923 4 | 0.937 1 |
Katz | 0.950 2 | 0.862 0 | 0.976 7 | 0.972 1 | 0.932 9 | 0.391 2 |
LHNII | 0.610 4 | 0.594 5 | 0.929 2 | 0.967 0 | 0.638 0 | 0.383 1 |
ACT | 0.901 2 | 0.742 5 | 0.964 4 | 0.899 7 | 0.892 5 | 0.950 3 |
LP | 0.952 2 | 0.864 6 | 0.943 8 | 0.970 4 | 0.936 2 | 0.970 7 |
MFI | 0.941 2 | 0.871 6 | 0.976 7 | 0.972 3 | 0.906 0 | 0.955 9 |
SRW | 0.974 2 | 0.903 4 | 0.960 4 | 0.975 8 | 0.938 4 | 0.963 6 |
PEW-CN | 0.971 5 | 0.870 8 | 0.661 9 | 0.886 6 | 0.927 4 | 0.944 1 |
PEW-Katz | 0.996 5 | 0.992 1 | 0.995 9 | 0.995 5 | 0.988 3 | 0.479 5 |
PEW-LHNII | 0.747 9 | 0.843 9 | 0.976 7 | 0.992 9 | 0.824 8 | 0.871 0 |
PEW-ACT | 0.932 9 | 0.802 6 | 0.993 6 | 0.932 1 | 0.903 8 | 0.953 9 |
PEW-LP | 0.958 4 | 0.879 0 | 0.950 0 | 0.972 3 | 0.937 7 | 0.972 0 |
PEW-MFI | 0.980 7 | 0.975 3 | 0.993 6 | 0.993 0 | 0.977 0 | 0.971 0 |
PEW-SRW | 0.996 1 | 0.992 5 | 0.967 3 | 0.980 9 | 0.991 7 | 0.993 2 |
Tab. 4 AUC values of each algorithm in single mechanism algorithm verification
算法 | 数据集 | |||||
---|---|---|---|---|---|---|
USAir | Celegans | Router | Yeast | PB | wiki-vote | |
CN | 0.954 2 | 0.846 6 | 0.652 2 | 0.915 1 | 0.923 4 | 0.937 1 |
Katz | 0.950 2 | 0.862 0 | 0.976 7 | 0.972 1 | 0.932 9 | 0.391 2 |
LHNII | 0.610 4 | 0.594 5 | 0.929 2 | 0.967 0 | 0.638 0 | 0.383 1 |
ACT | 0.901 2 | 0.742 5 | 0.964 4 | 0.899 7 | 0.892 5 | 0.950 3 |
LP | 0.952 2 | 0.864 6 | 0.943 8 | 0.970 4 | 0.936 2 | 0.970 7 |
MFI | 0.941 2 | 0.871 6 | 0.976 7 | 0.972 3 | 0.906 0 | 0.955 9 |
SRW | 0.974 2 | 0.903 4 | 0.960 4 | 0.975 8 | 0.938 4 | 0.963 6 |
PEW-CN | 0.971 5 | 0.870 8 | 0.661 9 | 0.886 6 | 0.927 4 | 0.944 1 |
PEW-Katz | 0.996 5 | 0.992 1 | 0.995 9 | 0.995 5 | 0.988 3 | 0.479 5 |
PEW-LHNII | 0.747 9 | 0.843 9 | 0.976 7 | 0.992 9 | 0.824 8 | 0.871 0 |
PEW-ACT | 0.932 9 | 0.802 6 | 0.993 6 | 0.932 1 | 0.903 8 | 0.953 9 |
PEW-LP | 0.958 4 | 0.879 0 | 0.950 0 | 0.972 3 | 0.937 7 | 0.972 0 |
PEW-MFI | 0.980 7 | 0.975 3 | 0.993 6 | 0.993 0 | 0.977 0 | 0.971 0 |
PEW-SRW | 0.996 1 | 0.992 5 | 0.967 3 | 0.980 9 | 0.991 7 | 0.993 2 |
算法 | 数据集 | |||||
---|---|---|---|---|---|---|
USAir | Celegans | Router | Yeast | PB | wiki-vote | |
PEW-CN | 0.971 5 | 0.870 8 | 0.661 9 | 0.886 6 | 0.927 4 | 0.944 1 |
PEW-Katz | 0.996 5 | 0.992 1 | 0.995 9 | 0.995 5 | 0.988 3 | 0.479 5 |
PEW-LHNII | 0.747 9 | 0.843 9 | 0.976 7 | 0.992 9 | 0.824 8 | 0.871 0 |
PEW-ACT | 0.932 9 | 0.802 6 | 0.993 6 | 0.932 1 | 0.903 8 | 0.953 9 |
PEW-LP | 0.958 4 | 0.879 0 | 0.950 0 | 0.972 3 | 0.937 7 | 0.972 0 |
PEW-MFI | 0.980 7 | 0.975 3 | 0.993 6 | 0.993 0 | 0.977 0 | 0.971 0 |
PEW-SRW | 0.996 1 | 0.992 5 | 0.967 3 | 0.980 9 | 0.991 7 | 0.993 2 |
OWA | 0.966 7 | 0.867 9 | 0.926 3 | 0.977 4 | 0.884 9 | 0.968 2 |
EMLP | 0.999 6 | 0.902 4 | 0.989 9 | 0.991 2 | 0.973 2 | 0.988 5 |
Tab. 5 AUC values of hybrid link prediction algorithms based on PEW model, OWA and EMLP algorithms on six networks
算法 | 数据集 | |||||
---|---|---|---|---|---|---|
USAir | Celegans | Router | Yeast | PB | wiki-vote | |
PEW-CN | 0.971 5 | 0.870 8 | 0.661 9 | 0.886 6 | 0.927 4 | 0.944 1 |
PEW-Katz | 0.996 5 | 0.992 1 | 0.995 9 | 0.995 5 | 0.988 3 | 0.479 5 |
PEW-LHNII | 0.747 9 | 0.843 9 | 0.976 7 | 0.992 9 | 0.824 8 | 0.871 0 |
PEW-ACT | 0.932 9 | 0.802 6 | 0.993 6 | 0.932 1 | 0.903 8 | 0.953 9 |
PEW-LP | 0.958 4 | 0.879 0 | 0.950 0 | 0.972 3 | 0.937 7 | 0.972 0 |
PEW-MFI | 0.980 7 | 0.975 3 | 0.993 6 | 0.993 0 | 0.977 0 | 0.971 0 |
PEW-SRW | 0.996 1 | 0.992 5 | 0.967 3 | 0.980 9 | 0.991 7 | 0.993 2 |
OWA | 0.966 7 | 0.867 9 | 0.926 3 | 0.977 4 | 0.884 9 | 0.968 2 |
EMLP | 0.999 6 | 0.902 4 | 0.989 9 | 0.991 2 | 0.973 2 | 0.988 5 |
1 | 汪小帆. 数据科学与社会网络:大数据,小世界[J]. 科学与社会, 2014, 4(1):27-35. 10.3969/j.issn.2095-1949.2014.01.003 |
WANG X F. Data science and social network: big data, small world[J]. Science and Society, 2014, 4(1): 27-35. 10.3969/j.issn.2095-1949.2014.01.003 | |
2 | WANG Z B, LIAO J L, CAO Q, et al. Friendbook: a semantic-based friend recommendation system for social networks[J]. IEEE Transactions on Mobile Computing, 2015, 14(3): 538-551. 10.1109/tmc.2014.2322373 |
3 | KOVÁCS I A, LUCK K, SPIROHN K, et al. Network-based prediction of protein interactions[J]. Nature Communications, 2019, 10: No.1240. 10.1038/s41467-019-09177-y |
4 | 刘宏鲲,吕琳媛,周涛. 利用链路预测推断网络演化机制[J]. 中国科学: 物理学 力学 天文学, 2011, 41(7): 816-823. 10.1360/132010-922 |
LIU H K, LYU L Y, ZHOU T. Uncovering the network evolution mechanism by link prediction[J]. SCIENTIA SINICA: Physica, Mechanica and Astronomica, 2011, 41(7): 816-823. 10.1360/132010-922 | |
5 | LORRAIN F, WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematical Sociology, 1971, 1(1): 49-80. 10.1080/0022250x.1971.9989788 |
6 | MARTÍNEZ V, BERZAL F, CUBERO J C. A survey of link prediction in complex networks[J]. ACM Computing Surveys, 2017, 49(4): No.69. 10.1145/3012704 |
7 | LÜ L Y, ZHOU T. Link prediction in complex networks: a survey[J]. Physic A: Statistical Mechanics and its Applications, 2011, 390(6):1150-1170. 10.1016/j.physa.2010.11.027 |
8 | WEBB A R, COPSEY K D. 统计模式识别[M]. 3版. 王萍,译. 北京:电子工业出版社, 2015: 63-91. |
WEBB A R, COPSEY K D. Statistical Pattern Recognition[M]. 3rd ed. WANG P, translated. Beijing: Publishing House of Electronics Industry, 2015: 63-91. | |
9 | 吴翼腾,于洪涛,黄瑞阳,等. 采用组合方法进行链路预测的理论极限研究[J]. 通信学报, 2020, 41(6):34-50. 10.11959/j.issn.1000-436x.2020125 |
WU Y T, YU H T, HUANG R Y, et al. Theoretical limit of link prediction using a combination method[J]. Journal on Communications, 2020, 41(6): 34-50. 10.11959/j.issn.1000-436x.2020125 | |
10 | HE Y L, LIU J N K, HU Y X, et al. OWA operator based link prediction ensemble for social network[J]. Expert Systems with Applications, 2015, 42(1): 21-50. 10.1016/j.eswa.2014.07.018 |
11 | 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. 10.1016/j.physleta.2017.08.047 |
12 | 吴祖峰,梁棋,刘峤,等. 基于AdaBoost的链路预测优化算法[J]. 通信学报, 2014, 35(3):116-123. 10.3969/j.issn.1000-436x.2014.03.013 |
WU Z F, LIANG Q, LIU Q, et al. Modified link prediction algorithm based on AdaBoost[J]. Journal on Communications, 2014, 35(3): 116-123. 10.3969/j.issn.1000-436x.2014.03.013 | |
13 | LI K Y, TU L L, CHAI L. Ensemble-model-based link prediction of complex networks[J]. Computer Networks, 2020, 166: No.106978. 10.1016/j.comnet.2019.106978 |
14 | WANG Y J, YAO Y, TONG H H, et al. A brief review of network embedding[J]. Big Data Mining and Analytics, 2019, 2(1): 35-47. 10.26599/bdma.2018.9020029 |
15 | 姚登举,杨静,詹晓娟. 基于随机森林的特征选择算法[J]. 吉林大学学报(工学版), 2014, 44(1):137-141. 10.1504/ijdmb.2015.070852 |
YAO D J, YANG J, ZHAN X J. Feature selection algorithm based on random forest[J]. Journal of Jilin University (Engineering and Technology Edition), 2014, 44(1): 137-141. 10.1504/ijdmb.2015.070852 | |
16 | VON MERING C, KRAUSE R, SNEL B, et al. Comparative assessment of large-scale data sets of protein-protein interactions[J]. Nature, 2002, 417(6887):399-403. 10.1038/nature750 |
17 | 李渊,乔兵,陆宇平. 基于聚类方法的圆拟合算法[J]. 计算机应用, 2013, 33(S2): 206-208. |
LI Y, QIAO B, LU Y P. Circle fitting algorithm based on clustering[J]. Journal of Computer Applications, 2013, 33(S2): 206-208. | |
18 | 刘冶,朱蔚恒,潘炎,等. 基于低秩和稀疏矩阵分解的多源融合链接预测算法[J]. 计算机研究与发展, 2015, 52(2):423-436. 10.7544/issn1000-1239.2015.20140221 |
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. 10.7544/issn1000-1239.2015.20140221 | |
19 | 杨伟,陈家新,李济顺. 基于投影的二阶段空间圆线拟合算法[J]. 工程设计学报, 2009, 16(2): 117-121. |
YANG W, CHEN J X, LI J S. Two-step spatial circle fitting method based on projection[J]. Chinese Journal of Engineering Design, 2009, 16(2): 117-121. |
[1] | Yexin PAN, Zhe YANG. Optimization model for small object detection based on multi-level feature bidirectional fusion [J]. Journal of Computer Applications, 2024, 44(9): 2871-2877. |
[2] | Junchi GE, Weihua ZHAO. Distance weighted discriminant analysis based on robust principal component analysis for matrix data [J]. Journal of Computer Applications, 2024, 44(7): 2073-2079. |
[3] | Ruihua LIU, Zihe HAO, Yangyang ZOU. Gait recognition algorithm based on multi-layer refined feature fusion [J]. Journal of Computer Applications, 2024, 44(7): 2250-2257. |
[4] | Yue LIU, Fang LIU, Aoyun WU, Qiuyue CHAI, Tianxiao WANG. 3D object detection network based on self-attention mechanism and graph convolution [J]. Journal of Computer Applications, 2024, 44(6): 1972-1977. |
[5] | Dongju YANG, Chengfu HU. Keyword extraction method for scientific text based on improved TextRank [J]. Journal of Computer Applications, 2024, 44(6): 1720-1726. |
[6] | Mengyuan HUANG, Kan CHANG, Mingyang LING, Xinjie WEI, Tuanfa QIN. Progressive enhancement algorithm for low-light images based on layer guidance [J]. Journal of Computer Applications, 2024, 44(6): 1911-1919. |
[7] | Guijin HAN, Xinyuan ZHANG, Wentao ZHANG, Ya HUANG. Self-supervised image registration algorithm based on multi-feature fusion [J]. Journal of Computer Applications, 2024, 44(5): 1597-1604. |
[8] | Hongtian LI, Xinhao SHI, Weiguo PAN, Cheng XU, Bingxin XU, Jiazheng YUAN. Few-shot object detection via fusing multi-scale and attention mechanism [J]. Journal of Computer Applications, 2024, 44(5): 1437-1444. |
[9] | Xin LI, Qiao MENG, Junyi HUANGFU, Lingchen MENG. YOLOv5 multi-attribute classification based on separable label collaborative learning [J]. Journal of Computer Applications, 2024, 44(5): 1619-1628. |
[10] | Zhanjun JIANG, Baijing WU, Long MA, Jing LIAN. Faster-RCNN water-floating garbage recognition based on multi-scale feature and polarized self-attention [J]. Journal of Computer Applications, 2024, 44(3): 938-944. |
[11] | Xinye LI, Yening HOU, Yinghui KONG, Zhiqi YAN. Few-shot object detection combining feature fusion and enhanced attention [J]. Journal of Computer Applications, 2024, 44(3): 745-751. |
[12] | Zongze JIA, Pengfei GAO, Yinglong MA, Xiaofeng LIU, Haixin XIA. Multi-feature fusion attention-based hierarchical classification method for dialogue act [J]. Journal of Computer Applications, 2024, 44(3): 715-721. |
[13] | Ning WU, Yangyang LUO, Huajie XU. Semantic segmentation method for remote sensing images based on multi-scale feature fusion [J]. Journal of Computer Applications, 2024, 44(3): 737-744. |
[14] | Yuliang ZHENG, Yunhua CHEN, Weijie BAI, Pinghua CHEN. Vehicle target detection by fusing event data and image frames [J]. Journal of Computer Applications, 2024, 44(3): 931-937. |
[15] | Qiaoling HUANG, Bochuan ZHENG, Zicheng DING, Zedong WU. Improved image inpainting network incorporating supervised attention module and cross-stage feature fusion [J]. Journal of Computer Applications, 2024, 44(2): 572-579. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||