信息熵改进主成分分析模型的链路预测算法

doi:10.11772/j.issn.1001-9081.2021071326

摘要/Abstract

摘要：

针对传统的链路预测在不同结构特征的网络中的计算结果不稳定的问题，提出了基于信息熵改进主成分分析（PCA）模型的链路预测算法。首先，用随机森林（RF）确定7个相似性指标作为最佳特征集合；然后，将七个相似性指标组合在一起提出基于信息熵改进PCA的特征信息融合模型，在对特征信息赋予权重后，把该模型与单机制算法结合后在6个真实数据集上验证其正确性以及校验效果；最后，通过与混合链路预测算法比较曲线下面积（AUC）值来验证基于所提模型的链路预测算法的可行性和有效性。实验结果表明，所提出的链路预测算法比有序加权平均算法（OWA）和集成模型链路预测算法（EMLP）在预测精度AUC值上分别提升了2.5~12.46个百分点和0.47~9.01个百分点，具有较好的稳定性和准确性。可见，将所提算法应用到不同结构特征的网络中能得到更稳定、更准确的链路预测结果。

关键词: 复杂网络, 混合链路预测, 信息熵, 主成分分析, 特征融合

Abstract:

Aiming at the problem that traditional link prediction has computational results not stable in networks with different structures， a link prediction algorithm based on information entropy improved Principal Component Analysis （PCA） model was proposed. Firstly， seven similarity indexes were determined by Random Forest （RF） as the optimal feature set. Then， seven similarity indexes were combined to propose a feature information fusion model based on information entropy improved PCA. After weighting the feature information， the model was combined with the single mechanism algorithms to verify the correctness and verification effect of the model on six real-world datasets. Finally， the feasibility and effectiveness of the link prediction algorithm based on the proposed model were verified by comparing Area Under the Curve （AUC） values with the hybrid link prediction algorithms. Experimental results show that the proposed link prediction algorithms improve the AUC value by 2.5 to 12.46 percentage points and 0.47 to 9.01 percentage points， respectively， compared with Ordered Weighted Averaging aggregation operator （OWA） and Ensemble-Model-based Link Prediction algorithm （EMLP）. It can be seen that applying the proposed algorithm to networks with different structural features can obtain more stable and accurate link prediction results.

Key words: complex network, hybrid link prediction, information entropy, Principal Component Analysis (PCA), feature fusion

中图分类号:

TP301.6

孟昱煜, 郭静. 信息熵改进主成分分析模型的链路预测算法[J]. 计算机应用, 2022, 42(9): 2823-2829.

Yuyu MENG, Jing GUO. Link prediction algorithm based on information entropy improved PCA model[J]. Journal of Computer Applications, 2022, 42(9): 2823-2829.

图/表 7

表1 数据集拓扑特征参数

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

图1 特征指标的重要性指数

Fig. 1 Importance indexes of feature indicators

表2 不同数据集中各个主成分的贡献率

Tab. 2 Contribution rates of principal components in different datasets

数据集	主相似性特征
数据集	$λ 1$	$λ 2$	$λ 3$
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

表2 不同数据集中各个主成分的贡献率

Tab. 2 Contribution rates of principal components in different datasets

数据集	主相似性特征
数据集	$λ 1$	$λ 2$	$λ 3$
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

表3 不同数据集中各个主成分的累计贡献率

Tab. 3 Cumulative contribution rate of each principal component in different datasets

数据集	主相似性特征
数据集	$λ 1$	$λ 1 + λ 2$	$λ 1 + λ 2 + λ 3$
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

表3 不同数据集中各个主成分的累计贡献率

Tab. 3 Cumulative contribution rate of each principal component in different datasets

数据集	主相似性特征
数据集	$λ 1$	$λ 1 + λ 2$	$λ 1 + λ 2 + λ 3$
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

表4 单机制算法校验中各个算法的AUC值

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

图2 单机制算法校验中所提算法相较对比算法的AUC提升幅度

Fig. 2 AUC improvement rate of the proposed algorithm compared with comparison algorithm in single mechanism algorithm verification

表5 基于PEW模型的混合链路测算法以及OWA和EMLP算法在6个网络上的AUC值

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

参考文献 19

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]	潘烨新, 杨哲. 基于多级特征双向融合的小目标检测优化模型[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2871-2877.
[2]	葛焌迟, 赵为华. 矩阵数据基于鲁棒主成分分析的距离加权判别分析[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2073-2079.
[3]	刘瑞华, 郝子赫, 邹洋杨. 基于多层级精细特征融合的步态识别算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2250-2257.
[4]	刘越, 刘芳, 武奥运, 柴秋月, 王天笑. 基于自注意力机制与图卷积的3D目标检测网络[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1972-1977.
[5]	杨冬菊, 胡成富. 基于改进TextRank的科技文本关键词抽取方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1720-1726.
[6]	黄梦源, 常侃, 凌铭阳, 韦新杰, 覃团发. 基于层间引导的低光照图像渐进增强算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1911-1919.
[7]	韩贵金, 张馨渊, 张文涛, 黄娅. 基于多特征融合的自监督图像配准算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1597-1604.
[8]	李鑫, 孟乔, 皇甫俊逸, 孟令辰. 基于分离式标签协同学习的YOLOv5多属性分类[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1619-1628.
[9]	李鸿天, 史鑫昊, 潘卫国, 徐成, 徐冰心, 袁家政. 融合多尺度和注意力机制的小样本目标检测[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1437-1444.
[10]	吴宁, 罗杨洋, 许华杰. 基于多尺度特征融合的遥感图像语义分割方法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 737-744.
[11]	郑宇亮, 陈云华, 白伟杰, 陈平华. 融合事件数据和图像帧的车辆目标检测[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 931-937.
[12]	李新叶, 侯晔凝, 孔英会, 燕志旗. 结合特征融合与增强注意力的少样本目标检测[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 745-751.
[13]	蒋占军, 吴佰靖, 马龙, 廉敬. 多尺度特征和极化自注意力的Faster-RCNN水漂垃圾识别[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 938-944.
[14]	贾宗泽, 高鹏飞, 马应龙, 刘晓峰, 夏海鑫. 基于注意力机制的多特征融合对话行为层次化分类方法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 715-721.
[15]	黄巧玲, 郑伯川, 丁梓成, 吴泽东. 融合监督注意力模块和跨阶段特征融合的图像修复改进网络[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 572-579.