隐马尔可夫模型的异质网络链接预测方法研究

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

通信学报 ›› 2022, Vol. 43 ›› Issue (5): 214-225.doi: 10.11959/j.issn.1000-436x.2022095

• 学术通信 • 上一篇

隐马尔可夫模型的异质网络链接预测方法研究

钱榕¹^,², 许建婷², 张克君¹^,², 董宏宇¹, 邢方远¹

¹ 北京电子科技学院网络空间安全系，北京 100070
² 西安电子科技大学计算机科学与技术学院，陕西西安 710071

修回日期:2022-04-07 出版日期:2022-05-25 发布日期:2022-05-01
作者简介:钱榕（1970- ），男，福建福州人，博士，北京电子科技学院副教授、硕士生导师，主要研究方向为复杂网络、数据挖掘、云计算安全等
许建婷（1997- ），女，河北石家庄人，西安电子科技大学硕士生，主要研究方向为复杂网络、数据挖掘等
张克君（1972- ），男，山东临沂人，博士，北京电子科技学院教授、博士生导师，主要研究方向为智能计算、信息安全等
董宏宇（1994- ），女，内蒙古乌兰察布人，北京电子科技学院硕士生，主要研究方向为复杂网络、数据挖掘等
邢方远（1998- ），男，辽宁宽甸人，北京电子科技学院硕士生，主要研究方向为复杂网络、数据挖掘等
基金资助:
国家重点研发计划基金资助项目(2018YFB1004101)

Research on HMM based link prediction method in heterogeneous network

Rong QIAN¹^,², Jianting XU², Kejun ZHANG¹^,², Hongyu DONG¹, Fangyuan XING¹

¹ Department of Cyberspace Security, Beijing Electronic Science and Technology Institute, Beijing 100070, China
² College of Computer Science and Technology, Xidian University, Xi’an 710071, China

Revised:2022-04-07 Online:2022-05-25 Published:2022-05-01
Supported by:
The National Key Research and Development Program of China(2018YFB1004101)

摘要/Abstract

摘要：

为了解决异质网络的结构信息和语义信息挖掘不全面的问题，针对异质网络的链接预测，提出了将基于元路径的分析方式与隐马尔可夫模型相结合的链接预测方法。考虑到聚簇可以有效地捕获异质网络的结构信息，将k-means算法进行改进得到基于距离均方差最小的初始聚簇中心方法，并将其应用到隐马尔可夫模型（HMM）中，设计了基于聚簇的一阶隐马尔可夫模型（C-HMM⁽¹⁾）的链接预测方法，同时提出基于聚簇的二阶隐马尔可夫模型（C-HMM⁽²⁾）的异质网络的链接预测方法。进一步考虑数据的特征信息，提出了将最大熵模型和二阶隐马尔可夫模型相结合的链接预测方法ME-HMM。实验结果表明，ME-HMM比C-HMM方法的链接预测精确度更高，且ME-HMM因充分考虑到数据的特征信息比C-HMM的性能更加优异。

关键词: 异质网络, 链接预测, 隐马尔可夫模型, 聚簇, 最大熵

Abstract:

In order to solve the problem that incomplete mining of structural information and semantic information in heterogeneous networks, a link prediction method combining meta-path-based analysis and hidden Markov model was proposed for link prediction of heterogeneous network.Considering that clustering could effectively capture the structural information of heterogeneous network, the k-means algorithm was improved to obtain the initial clustering center method based on the minimum distance mean square error, and it was applied to the hidden Markov model, first-order cluster hidden markov model (C-HMM⁽¹⁾) link prediction method, and a link prediction method for heterogeneous network with second-order cluster hidden Markov model (C-HMM⁽²⁾) were designed.Further, considering the feature information of the data, a link prediction method called ME-HMM that combined the maximum entropy model and the second-order Markov model was proposed.The experimental results show that the ME-HMM has higher link prediction accuracy than the C-HMM, and the ME-HMM method has better performance than the C-HMM method because it fully considers the feature information of the data.

Key words: heterogeneous network, link prediction, hidden Markov model, clustering, maximum entropy

中图分类号:

TP181

钱榕, 许建婷, 张克君, 董宏宇, 邢方远. 隐马尔可夫模型的异质网络链接预测方法研究[J]. 通信学报, 2022, 43(5): 214-225.

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.

图/表 16

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

表1

图12

表2

图13

表3

参考文献 27

[1]	LEE J B , ADORNA H . Link prediction in a modified heterogeneous bibliographic network[C]// Proceedings of 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway:IEEE Press, 2012: 442-449.
[2]	蒋宗礼, 陈浩强, 张津丽 . 基于融合元路径权重的异质网络表征学习[J]. 计算机系统应用, 2019,28(12): 28-36.
	JIANG Z L , CHEN H Q , ZHANG J L . Heterogeneous network representation learning based on fusion meta-path weights[J]. Computer Systems ＆ Applications, 2019,28(12): 28-36.
[3]	MA Y , CHENG G Q , LIANG X X ,et al. Heterogeneous graph neural networks based on meta-path[C]// Proceeding of 2020 3rd International Conference on Algorithms,Computing and Artificial Intelligence.[S.l.:s.n.], 2020: 95-98.
[4]	朱恺 . 异构社交网络中基于元路径的链接预测研究[D]. 南京:南京大学, 2020.
	ZHU K . Research on meta path-based link prediction in heterogeneous social networks[D]. Nanjing:Nanjing University, 2020.
[5]	郑玉艳 . 异质信息网络的语义元路径分析方法研究[D]. 北京:北京邮电大学, 2019.
	ZHENG Y Y . Research on semantic meta path analysis method of heterogeneous information networks[D]. Beijing:Beijing University of Posts and Telecommunications, 2019.
[6]	孙艺洲, 韩家炜 . 异构信息网络挖掘:原理和方法[M]. 段磊,朱敏,唐常杰,等,译 . 北京: 机械工业出版社, 2017.
	SUN Y Z , HAN J W . Mining heterogeneous information networks:principles and methodologies[M]. Translated by DUAN L,ZHU M,TANG C J,et al. Beijing: China Machine Press, 2017.
[7]	SUN Y , HAN J , YAN X ,et al. PathSim:meta path based top-k similarity search in heterogeneous information networks[J]. Proceedings of the VLDB Endowment, 2011,4(11): 992-1003.
[8]	郭振宏, 李海峰 . 异质信息网络中演员合作关系的链路预测[J]. 计算机工程, 2017,43(1): 219-225.
	GUO Z H , LI H F . Link prediction of actor cooperation relationship in heterogeneous information network[J]. Computer Engineering, 2017,43(1): 219-225.
[9]	韩忠明, 李胜男, 郑晨烨 ,等. 基于动态网络表示的链接预测[J]. 物理学报, 2020,69(16): 332-345.
	HAN Z M , LI S N , ZHENG C Y ,et al. Link prediction model based on dynamic network representation[J]. Acta Physica Sinica, 2020,69(16): 332-345.
[10]	刘大伟, 吕元娜, 余智华 . 一种改进的复杂网络链路预测算法[J]. 小型微型计算机系统, 2016,37(5): 1071-1074.
	LIU D W , LV Y N , YU Z H . An improved link prediction algorithm for complex networks[J]. Journal of Chinese Computer Systems, 2016,37(5): 1071-1074.
[11]	董鑫 . 基于 Boosting 的异质信息网络链路预测方法研究[D]. 黑龙江:哈尔滨工程大学, 2017.
	DONG X . Research on boosting based method of link prediction in heterogeneous information network[D]. Heilongjiang:Harbin Engineering University, 2017.
[12]	赵妍, 赵书良, 马秋微 . 基于图核的异质信息网络链路预测方法[J]. 计算机应用研究, 2021,38(10): 3125-3130.
	ZHAO Y , ZHAO S L , MA Q W . Graph kernel based link prediction in heterogeneous information network[J]. Application Research of Computers, 2021,38(10): 3125-3130.
[13]	孙诚, 王志海 . 社会网络中基于神经网络的链路预测方法[J]. 数学建模及其应用, 2017,6(4): 10-17.
	SUN C , WANG Z H . The link prediction algorithms based on neural networks in social networks[J]. Mathematical Modeling and Its Applications, 2017,6(4): 10-17.
[14]	黄立威, 李德毅, 马于涛 ,等. 一种基于元路径的异质信息网络链路预测模型[J]. 计算机学报, 2014,37(4): 848-858.
	HUANG L W , LI D Y , MA Y T ,et al. A meta path-based link prediction model for heterogeneous information networks[J]. Chinese Journal of Computers, 2014,37(4): 848-858.
[15]	王凯, 刘树新, 丁洪涛 ,等. 基于共同邻居有效性的复杂网络链路预测算法[J]. 电子科技大学学报, 2019,48(3): 432-439.
	WANG K , LIU S X , YU H T ,et al. Predicting missing links of complex network via effective common neighbors[J]. Journal of University of Electronic Science and Technology of China, 2019,48(3): 432-439.
[16]	汤永新, 齐敬英 . 基于共同邻居的小度节点有利链路预测算法[J]. 现代电子技术, 2021,44(5): 37-40.
	TANG Y X , QI J Y . Algorithm of predicting missing links of small promoted index via common neighbors[J]. Modern Electronics Technique, 2021,44(5): 37-40.
[17]	JIN W , JUNG J , KANG U . Supervised and extended restart in random walks for ranking and link prediction in networks[J]. PLoS One, 2019,14(3): e0213857.
[18]	DONG S L , WU Z G , SHI P ,et al. Quantized control of Markov jump nonlinear systems based on fuzzy hidden Markov model[J]. IEEE Transactions on Cybernetics, 2019,49(7): 2420-2430.
[19]	杨妮亚 . 异质网络中基于元路径的链路预测方法的研究[D]. 长春:吉林大学, 2018.
	YANG N Y . Meta path-based link prediction research for heterogeneous information networks[D]. Changchun:Jilin University, 2018.
[20]	赵宇红, 吴昊 . 基于图表示深度学习的异质网络链路预测研究[J]. 小型微型计算机系统,(2021-12-13)[2022-01-10].
	ZHAO Y H , WU H . Link prediction in heterogeneous networks based on deep learning of graph representation[J]. 小型微型计算机系统,(2021-12-13)[2022-01-10].
[21]	彭高婧 . 基于PU学习的链接预测方法研究[D]. 南京:南京邮电大学, 2018.
	PENG G J . Research on link prediction method based on PU learning[D]. Nanjing:Nanjing University of Posts and Telecommunications, 2018.
[22]	崔仕颖 . 基于隐马尔可夫模型的食品安全风险评估方法研究及应用[D]. 北京:北京化工大学, 2020.
	CUI S Y . Research and application of food safety risk assessment algorithm based on hidden Markov model[D]. Beijing:Beijing University of Chemical Technology, 2020.
[23]	安晓宁, 王智文, 张灿龙 ,等. 基于隐马尔可夫模型的人脸特征标注和识别[J]. 广西科技大学学报, 2020,31(2): 118-125.
	AN X N , WANG Z W , ZHANG C L ,et al. Face feature labeling and recognition based on hidden Markov model[J]. Journal of Guangxi University of Science and Technology, 2020,31(2): 118-125.
[24]	MACQUEEN J , . Some methods for classification and analysis of multivariate observations[C]// Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. California:University of California Press, 1967: 281-297.
[25]	丛蓉, 王秀坤, 李进军 ,等. 基于层次和密度聚类分析的航迹关联算法[J]. 系统仿真学报, 2005,17(4): 841-843.
	CONG R , WANG X K , LI J J ,et al. Plot-track association algorithm based on hierarchical and density clustering analysis[J]. Acta Simulata Systematica Sinica, 2005,17(4): 841-843.
[26]	李永森, 杨善林, 马溪骏 ,等. 空间聚类算法中的 K 值优化问题研究[J]. 系统仿真学报, 2006,18(3): 573-576.
	LI Y S , YANG S L , MA X J ,et al. Optimization study on K value of spatial clustering[J]. Journal of System Simulation, 2006,18(3): 573-576.
[27]	KAUFMAN L , ROUSSEEUW P J . Finding groups in data:an introduction to cluster analysis[M]. Saarland: DBLP, 2009.

待预测节点	C-HMM⁽¹⁾	HMM
作者	0.836 246	0.823 226
标题	0.858 673	0.853 853
会议	0.887 625	0.835 826

待预测节点	C-HMM⁽¹⁾	C-HMM⁽²⁾
作者	0.823 226	0.836 246
标题	0.853 853	0.858 673
会议	0.835 826	0.887 625

链接预测方法	Precision	Recall	F-Measure
CN	0.827	0.836	0.843
RWR	0.853	0.862	0.876
HMM	0.829	—	—
BRLinks	—	—	0.873
MDGCN	0.830	—	—
PURP	—	—	0.805
C-HMM⁽¹⁾	0.853	0.883	0.903
C-HMM⁽²⁾	0.921	0.876	0.922
ME-HMM	0.943	0.923	0.957

隐马尔可夫模型的异质网络链接预测方法研究

Research on HMM based link prediction method in heterogeneous network

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 16

参考文献 27

相关文章 10

Metrics

推荐阅读 0

[1]	赵晓娟, 贾焰, 李爱平, 陈恺. 基于层级注意力机制的链接预测模型研究[J]. 通信学报, 2021, 42(3): 36-44.
[2]	龙华,杨明亮,邵玉斌. 基于特征流融合的带噪语音检测算法[J]. 通信学报, 2020, 41(4): 134-142.
[3]	乔亚琼, 罗向阳, 马江涛, 李晨亮, 张萌, 李瑞祥. 基于多种提及关系的社交媒体用户位置推断[J]. 通信学报, 2020, 41(12): 72-81.
[4]	郭渊博,刘春辉,孔菁,王一丰. 内部威胁检测中用户行为模式画像方法研究[J]. 通信学报, 2018, 39(12): 141-150.
[5]	罗建桢,余顺争,蔡君. 基于最大似然概率的协议关键词长度确定方法[J]. 通信学报, 2016, 37(6): 119-128.
[6]	王昌海,张建忠,徐敬东,许昱玮. 基于HMM的动作识别结果可信度计算方法[J]. 通信学报, 2016, 37(5): 143-151.
[7]	杨晓峰,孙明明,胡雪蕾,杨静宇. 基于改进隐马尔可夫模型的网络攻击检测方法[J]. 通信学报, 2010, 31(3): 95-101.
[8]	邬书跃,田新广. 基于隐马尔可夫模型的用户行为异常检测新方法[J]. 通信学报, 2007, 28(4): 38-43.
[9]	王春桃,倪江群,黄继武,张荣跃,罗锡璋. 基于内容自适应的优化DWT-HMM顽健图像水印算法[J]. 通信学报, 2007, 28(2): 80-87.
[10]	殷玮玮,吴乐南. 基于HMM的信源—信道迭代联合译码[J]. 通信学报, 2006, 27(7): 61-65.