基于子图演化与改进蚁群优化算法的社交网络链路预测方法

doi:10.11959/j.issn.1000-436X.2020223

通信学报 ›› 2020, Vol. 41 ›› Issue (12): 21-35.doi: 10.11959/j.issn.1000-436X.2020223

基于子图演化与改进蚁群优化算法的社交网络链路预测方法

顾秋阳¹^,²^,³, 琚春华⁴, 吴功兴⁴

¹ 浙江工业大学管理学院，浙江杭州 310023
² 浙江工业大学中国中小企业研究院，浙江杭州 310023
³ 宁波诺丁汉大学商学院，浙江宁波 315175
⁴ 浙江工商大学管理工程与电子商务学院，浙江杭州 310018

修回日期:2020-09-05 出版日期:2020-12-25 发布日期:2020-12-01
作者简介:顾秋阳（1995- ），男，浙江杭州人，浙江工业大学博士生，主要研究方向为智能信息处理、数据挖掘、中小企业高质量发展等。
琚春华（1962- ），男，博士，浙江衢州人，浙江工商大学教授、博士生导师，主要研究方向为智能信息处理、数据挖掘、电子商务与物流优化等。
吴功兴（1974- ），男，博士，浙江义乌人，浙江工商大学副教授，主要研究方向为智能信息处理、数据挖掘、电子商务与物流优化等。
基金资助:
国家自然科学基金资助项目(71571162);浙江省社科规划重点课题基金资助项目(20NDJC10Z);浙江省自然科学基金资助项目(LQ20G010002)

Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm

Qiuyang GU¹^,²^,³, Chunhua JU⁴, Gongxing WU⁴

¹ School of Management, Zhejiang University of Technology, Hangzhou 310023, China
² China Institute for Small and Medium Enterprises, Zhejiang University of Technology, Hangzhou 310023, China
³ Business School, University of Nottingham Ningbo, Ningbo 315175, China
⁴ School of Management Science ＆Engineering, Zhejiang Gongshang University, Hangzhou 310018, China

Revised:2020-09-05 Online:2020-12-25 Published:2020-12-01
Supported by:
The National Natural Science Foundation of China(71571162);Zhejiang Social Science Planning Key Projects Fundation(20NDJC10Z);The Natural Science Foundation of Zhejiang Province(LQ20G010002)

摘要/Abstract

摘要：

基于改进蚁群优化算法与子图演化，提出了一种新型非监督社交网络链路预测（SE-ACO）方法。该方法首先在社交网络图中确定特殊子图；然后研究子图演化以预测图中的新链接，并用蚁群优化算法定位特殊子图；最后针对所提方法使用不同网络拓扑环境与数据集进行检验。结果表明，与其他无监督社交网络预测算法相比，所提SE-ACO方法在多数数据集上的评估结果较好，且运行时间较短，这表明图形结构在链路预测算法中起重要作用。

关键词: 链路预测, 蚁群优化算法, 社交网络, 子图演化

Abstract:

Based on improved ant colony algorithm and subgraph evolution fusion, a new unsupervised social network link prediction method (SE-ACO) was proposed.First, the special subgraph was determined in the social network graph.Then the evolution of the subgraph was studied to predict the new links in the graph, and the special subgraph was located by the ant colony method.Finally, using different network topology environments and data sets to test the proposed method.Compared with other unsupervised social network prediction algorithms, the proposed SE-ACO method has the best evaluation results, shorter running time and the best effect on most data sets, which indicates that graph structure plays an important role in link prediction algorithm.

Key words: link prediction, ant colony optimization algorithm, social network, subgraph evolution

中图分类号:

TP391

顾秋阳, 琚春华, 吴功兴. 基于子图演化与改进蚁群优化算法的社交网络链路预测方法[J]. 通信学报, 2020, 41(12): 21-35.

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.

图/表 14

图1

图2

图3

图4

表1

表2

表3

表4

几种算法在数据集的精度对比"

算法	新浪微博	Twitter	Facebook	hep-ph	astro-ph	dblp-collab	dblp-cite	polblogs	patent-colla
随机预测器精度	57.84%	69.42%	56.92%	24.81%	49.02%	3.71%	5.89%	37.84%	7.38%
CN	46.73%	57.28%	43.81%	31.90%	48.91%	3.81%	3.94%	39.82%	4.83%
AA	54.28%	64.90%	48.94%	49.39%	39.30%	12.21%	6.44%	48.39%	12.93%
JC	59.39%	68.38%	59.10%	38.18%	42.89%	4.93%	4.92%	43.82%	4.83%
PA	48.30%	54.89%	52.78%	39.28%	42.19%	4.37%	5.84%	43.92%	3.20%
Katz	30.34%	43.99%	58.94%	21.03%	43.90%	5.49%	4.83%	22.07%	0.28%
Distance	56.59%	54.89%	64.90%	58.39%	46.37%	27.83%	4.83%	40.91%	3.35%
RP	68.59%	64.72%	69.28%	43.89%	54.19%	5.44%	5.91%	58.42%	0.43%
SR	55.84%	44.83%	58.49%	56.92%	34.90%	12.83%	6.45%	44.90%	20.34%
PF	34.23%	54.30%	53.91%	41.02%	23.81%	7.38%	5.48%	42.31%	11.23%
RA	53.25%	43.90%	57.84%	37.26%	17.83%	8.65%	9.43%	35.08%	3.34%
SE-ACO	$89 . 43 %$	$91 . 43 %$	$85 . 49 %$	$87 . 84 %$	$89 . 02 %$	$78 . 44 %$	$73 . 92 %$	$86 . 85 %$	$82 . 57 %$
注：加粗的数字表示针对某数据集精度最高的算法。

表4

表5

SE-ACO算法的Top-n与其他算法的精度比较情况"

算法	新浪微博	Twitter	Facebook	hep-ph	astro-ph	dblp-collab	dblp-cite	polblogs	patent-colla
CN	36.73	168.93	73.91	26.89	17.83	4 693	284.03	68.48	4737
AA	29.89	193.78	50.84	18.04	13.29	4 791	419.02	56.03	4290
JC	38.91	122.9	68.05	23.91	19.24	3 980	382.99	64.83	4379
PA	24.73	96.09	49.55	21.64	17.83	3 678	376.91	61.2	4728
Katz	19.04	152.66	56.04	27.9	26.04	4 017	392.04	65.09	4910
Distance	10.87	103.94	47.82	24.5	18.75	3 913	386.91	63.48	4289
RP	27.98	84.07	54.17	28.99	23.89	4 692	428.94	78.93	—
SR	24.01	79.3	48.91	25.63	17.32	—	217.03	47.16	—
PF	31.07	105.87	68.93	27.57	20.88	4 903	472.04	73.98	5382
RA	34.97	107.41	70.66	29.17	21.94	5 038	480.94	75.26	5490
SE-ACO	$42 . 68$	162.98	$84 . 37$	$34 . 81$	25.46	$5194$	$529 . 4$	72.63	$5629$
注：加粗的数字表示针对某数据集精度最高的算法。

表5

图5

表6

基于ROC曲线下面积的不同算法比较"

算法	新浪微博	Twitter	Facebook	hep-ph	astro-ph	dblp-collab	dblp-cite	polblogs	patent-colla
CN	57.83%	51.83%	58.37%	59.02%	52.91%	59.33%	63.89%	67.33%	58.31%
AA	57.31%	58.94%	52.09%	56.38%	58.44%	53.83%	62.91%	63.40%	68.37%
JC	59.75%	57.21%	52.98%	56.12%	52.89%	51.92%	69.23%	63.71%	58.19%
PA	58.38%	50.76%	50.38%	59.83%	64.92%	50.33%	58.92%	59.43%	58.93%
Katz	58.49%	52.93%	51.82%	62.98%	60.42%	61.24%	61.20%	70.26%	69.04%
Distance	50.00%	50.00%	50.00%	50.00%	50.00%	50.00%	50.00%	50.00%	50.00%
RP	62.83%	57.29%	39.40%	53.72%	58.93%	60.22%	64.95%	67.29%	—
SR	58.03%	61.89%	49.38%	60.41%	53.78%	—	68.94%	70.32%	—
PF	53.82%	60.44%	48.39%	53.24%	48.91%	52.31%	57.43%	67.93%	61.22%
RA	61.05%	48.92%	42.94%	54.10%	58.93%	61.84%	60.11%	59.35%	54.89%
SE-ACO	$68 . 43 %$	60.28%	$63 . 82 %$	$64 . 27 %$	60.32%	$63 . 91 %$	$72 . 81 %$	$87 . 83 %$	62.39%
注：加粗的数字表示针对某数据集精度最高的算法。

表6

表7

基于精确率-召回率曲线下面积的不同算法比较"

算法	新浪微博	Twitter	Facebook	hep-ph	astro-ph	dblp-collab	dblp-cite	polblogs	patent-colla
CN	3.28%	7.81%	3.66%	0.83%	2.89%	1.62%	5.74%	5.71%	1.74%
AA	4.49%	4.10%	4.07%	1.56%	1.63%	2.18%	4.23%	6.18%	2.38%
JC	2.71%	5.89%	2.90%	0.94%	1.78%	1.37%	3.84%	5.41%	2.91%
PA	1.93%	4.90%	6.85%	1.72%	4.83%	2.71%	4.12%	2.37%	3.72%
Katz	2.31%	3.72%	8.57%	2.17%	1.29%	1.63%	5.33%	3.92%	2.81%
Distance	1.52%	1.87%	4.95%	0.73%	0.74%	2.65%	4.81%	4.36%	0.84%
RP	3.93%	4.38%	7.83%	0.65%	1.58%	3.28%	4.73%	4.01%	—
SR	4.25%	3.99%	9.12%	1.22%	2.34%	—	4.10%	7.41%	—
PF	2.84%	5.84%	8.49%	0.93%	2.45%	2.81%	4.61%	5.26%	0.73%
RA	0.83%	3.42%	39.28%	0.34%	2.04%	4.09%	5.19%	4.31%	1.27%
SE-ACO	$6 . 74 %$	7.15%	$14 . 34 %$	$2 . 67 %$	4.49%	$4 . 22 %$	$6 . 22 %$	7.34%	$5 . 64 %$
注：加粗的数字表示针对某数据集精度最高的算法。

表7

图6

图7

参考文献 52

[28]	LI D , SHEN D R , KOU Y ,et al. Research on a link-prediction method based on a hierarchical hybrid-feature graph[J]. Science in Chi-na(Information Sciences), 2020,50(2): 221-238.
[29]	方哲, 游宏梁, 薛非 ,等. 专家知识协作加权超网络模型及其超链路预测研究[J]. 科研管理, 2017,38(S1): 259-266.
	FANG Z , YOU H L , XUE F ,et al. Research on expert knowledge collaboration weighted super network model and hyperlink predic-tion[J]. Science Research Management, 2017,38(S1): 259-266.
[30]	尚凤军, 龚文娟, 耿哲 . 基于链路预测和网络编码的MAC机制[J]. 通信学报, 2016,37(1): 17-27.
	SHANG F F , GONG W J , GENG Z . MAC mechanism based on link prediction and network coding[J]. Journal on Communications, 2016,37(1): 17-27.
[31]	HUANG Z . Link prediction based on graph topology:the predictive value of generalized clustering coefficient[J]. SSRN Electronic Journal, 2010: 1634014.
[32]	黄璐, 朱一鹤, 张嶷 . 基于加权网络链路预测的新兴技术主题识别研究[J]. 情报学报, 2019,38(4): 335-341.
	HUANG L , ZHU Y H , ZHANG Y . Research on identification of emerging topics based on link prediction with weighted networks[J]. Journal of the China Society for Scientific and Technical Information, 2019,38(4): 335-341.
[33]	LATAPY M . Main-memory triangle computations for very large (sparse (power-law)) graphs[J]. Theoretical Computer Science, 2008,407(1): 458-473.
[34]	TSOURAKAKIS C E , DRINEAS P , MICHELAKIS E ,et al. Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation[J]. Social Network Analysis and Mining, 2011,1(2): 75-81.
[35]	刘树新, 李星, 陈鸿昶 ,等. 基于资源传输匹配度的复杂网络链路预测方法[J]. 通信学报, 2020,41(6): 70-79.
	LIU S X , LI X , CHEN H C ,et al. Link prediction method based on matching degree of resource transmission for complex network[J]. Journal on Communications, 2020,41(6): 70-79.
[1]	李永立, 罗鹏, 张书瑞 . 基于决策分析的社交网络链路预测方法[J]. 管理科学学报, 2017,20(1): 64-74.
	LI Y L , LUO P , ZHANG S R . Link prediction in social networks based on decision analysis[J]. Journal of Management Sciences in China, 2017,20(1): 64-74.
[36]	NEWMAN M E J . Clustering and preferential attachment in growing networks[J]. Physical Review E:Statistical Nonlinear and Soft Matter Physics, 2001,64(2): 25102.
[37]	WU B , WU G , YANG M . A MapReduce based ant colony optimization approach to combinatorial optimization problems[C]// Proceedings of the 2012 8th International Conference on Natural Computation. Piscataway:IEEE Press, 2012: 728-732.
[2]	WANG Z , LIANG J , LI R . A fusion probability matrix factorization framework for link prediction[J]. Knowledge-Based Systems, 2018,159: 72-85.
[3]	LIBEN-NOWELL D , KLEINBERG J . The link-prediction problem for social networks[J]. Journal of the American Society for Information Science, 2007,58(7): 1019-1031.
[38]	DEAN J , GHEMAWAT S . MapReduce:simplified data processing on large clusters[J]. Communications of the ACM, 2008,51(1): 107-113.
[39]	NEWMAN M E J . Assortative mixing in networks[J]. Physical Review Letters, 2002,89(20): 208701.
[4]	王智强, 梁吉业, 李茹 . 基于信息融合的概率矩阵分解链路预测方法[J]. 计算机研究与发展, 2019,56(2): 306-318.
	WANG Z Q , LIANG J Y , LI R . Probability matrix factorization for link prediction based on information fusion[J]. Journal of Computer Research and Development, 2019,56(2): 306-318.
[40]	LICHTENWALTER R N , CHAWLA N V . Lpmade:link prediction made easy[J]. The Journal of Machine Learning Research, 2011,12: 2489-2492.
[41]	ADAMIC L A , GLANCE N . The political blogosphere and the 2004 U.S.election:divided they blog[C]// Proceedings of the 3rd International Workshop on Link Discovery. Chicago:Association for Computing Machinery, 2005: 36-43.
[5]	HUANG Z , LIN D K J . The time-series link prediction problem with applications in communication surveillance[J]. Informs Journal on Computing, 2008,21(2): 286-303.
[6]	YIN D , HONG L , DAVISON B D . Structural link analysis and prediction in microblogs[C]// Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York:ACM Press, 2011: 1163-1168.
[42]	LESKOVEC J , KLEINBERG J , FALOUTSOS C . Graphs over time:densification laws,shrinking diameters and possible explanations[C]// Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. New York:ACM Press, 2005: 177-187.
[43]	KATZ L . A new status index derived from sociometric analysis[J]. Psychometrika, 1953,18(1): 39-43.
[7]	PECH R , HAO D , LEE Y L ,et al. Link prediction via linear optimization[J]. Physica A:Statistical Mechanics and Its Applications, 2019,528: 121319.
[8]	JACCARD P . étude comparative de la distribution florale dans une portion des Alpes et des Jura[J]. Bull Soc Vaudoise Sci Nat, 1901,37: 547-579.
[44]	BRIN S , PAGE L . The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks, 1998,30: 107-117.
[45]	JEH G , WIDOM J . SimRank:a measure of structural-context similarity[C]// Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2002: 538-543.
[9]	HU H , ZHU C , AI H ,et al. LPI-ETSLP:lncRNA-protein interaction prediction using eigenvalue transformation-based semi-supervised link prediction[J]. Molecular Biosystems, 2017,13(9): 1781-1787.
[10]	王守辉, 于洪涛, 黄瑞阳 ,等. 基于模体演化的时序链路预测方法[J]. 自动化学报, 2016,42(5): 735-745.
[46]	LICHTENWALTER R N , LUSSIER J T , CHAWLA N V . New perspectives and methods in link prediction[C]// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2010: 243-252.
[47]	李勇军, 尹超, 于会 ,等. 基于最大熵模型的微博传播网络中的链路预测[J]. 物理学报, 2016,65(2): 31-41.
[10]	WANG S H , YU H T , HUANG R Y ,et al. Time series link prediction method based on phantom evolution[J]. Acta Automatica Sinica, 2016,42(5): 735-745.
[11]	GAO H , HUANG J B , CHENG Q ,et al. Link prediction based on linear dynamical response[J]. Physica A:Statistical Mechanics and Its Applications, 2019,527: 121397
[47]	LI Y C , YIN C , YU H ,et al. Link prediction in microblog retweet network based on maximum entropy model[J]. Acta Physica Sinica, 2016,65(2): 31-41.
[48]	翟东升, 刘鹤, 张杰 ,等. 一种基于链路预测的技术机会挖掘方法[J]. 情报学报, 2016,35(10): 1090-1100.
[12]	WU J H , SHEN J , ZHOU B ,et al. General link prediction with influential node identification[J]. Physica A:Statistical Mechanics and its Applications, 2019,523: 996-1007.
[13]	王凯, 李星, 兰巨龙 ,等. 一种基于资源传输路径拓扑有效性的链路预测方法[J]. 电子与信息学报, 2020,42(3): 653-660.
[48]	ZHAI D S , LIU H , ZHANG J ,et al. Approach to mining technology opportunity based on link prediction[J]. Journal of the China Society for Scientific and Technical Information, 2016,35(10): 1090-1100.
[49]	HAND D J . Measuring classifier performance:a coherent alternative to the area under the ROC curve[J]. Machine Learning, 2009,77(1): 103-123.
[13]	WANG K , LI X , LAN J L ,et al. A new link prediction method for complex networks based on topological effectiveness of resource transmission paths[J]. Journal of Electronics ＆ Information Technolo-gy, 2020,42(3): 653-660.
[14]	舒坚, 张学佩, 刘琳岚 ,等. 基于深度卷积神经网络的多节点之间链路预测方法[J]. 电子学报, 2018,46(12): 2970-2977.
[50]	DAVIS J , GOADRICH M . The relationship between precision-recall and ROC curves[C]// Proceedings of the 23rd International Conference on Machine Learning. New York:ACM Press, 2006: 233-240.
[51]	肖婧, 张永建, 许小可 . 复杂网络模糊重叠社区检测研究进展[J]. 复杂系统与复杂性科学, 2017,14(3): 8-29.
[14]	SHU J , ZHANG X P , LIU L L ,et al. Multi-nodes link prediction method based on deep convolution neural networks[J]. Acta Electro-nica Sinica, 2018,46(12): 2970-2977.
[15]	DORIGO M , BLUM C . Ant colony optimization theory:a survey[J]. Theoretical Computer Science, 2005,344(2-3): 243-278.
[16]	FADAEE S A , AMIR H M . Classification using link prediction[J]. Neurocomputing, 2019,359: 395-407.
[17]	LICHTENWALTER R N , CHAWLA N V . Vertex collocation profiles:subgraph counting for link analysis and prediction[C]// Proceedings of the 21st International Conference on World Wide Web. New York:ACM Press, 2012: 1019-1028.
[18]	张子柯 . 在线社交网络信息传播机制与动力学研究综述[J]. 情报学报, 2017,36(4): 422-431.
	ZHANG Z K . Mechanisms and dynamics of information spreading on online social networks:a state-of-the-art survey[J]. Journal of the China Society for Scientific and Technical Information, 2017,36(4): 422-431.
[19]	ZHANG Q M , LYU L , WANG W Q ,et al. Potential theory for directed networks[J]. PLos One, 2013,8(2): e55437.
[20]	胡文斌, 王欢, 严丽平 ,等. 混合指标量子群智能社会网络事件检测方法[J]. 软件学报, 2016,27(11): 2747-2762.
[51]	XIAO J , ZHANG Y J , XU X K . Research progress of fuzzy overlap-ping community detection in complex networks[J]. Complex Systems and Complexity Science, 2017,14(3): 8-29.
[52]	叶小莺, 万梅, 唐蓉 ,等. 基于图聚类与蚁群优化算法的社交网络聚类算法[J]. 计算机应用研究, 2020,37(6): 1670-1674,1687.
[20]	HU W B , WANG H , YAN L P ,et al. Hybrid quantum swarm intelli-gence indexing for event detection in social networks[J]. Journal of Software, 2016,27(11): 2747-2762.
[21]	郭丽媛, 王智强, 梁吉业 . 基于边重要度的矩阵分解链路预测算法[J]. 模式识别与人工智能, 2018,31(2): 150-157.
	GUO L Y , WANG Z Q , LIANG J Y . Link prediction algorithm by matrix factorization based on importance of edges[J]. Pattern Recogni-tion and Artificial Intelligence, 2018,31(2): 150-157.
[22]	GONG N Z , TALWALKAR A , MACKEY L ,et al. Joint link prediction and attribute inference using a social-attribute network[J]. ACM Transactions on Intelligent Systems and Technology, 2014,5(2): Article 27.
[23]	GORI M , MONFARDINI G , SCARSELLI F . A new model for learning in graph domains[C]// Proceedings of the 2005 IEEE International Joint Conference on Neural Networks. Piscataway:IEEE Press, 2005: 729-734.
[24]	BRONSTEIN M M , BRUNA J , LECUN Y ,et al. Geometric deep learning:going beyond euclidean data[J]. IEEE Signal Processing Magazine, 2017,34(4): 18-42.
[25]	白铂, 刘玉婷, 马驰骋 ,等. 图神经网络[J]. 中国科学:数学, 2020,(3): 367-384.
	BAI B , LIU Y T , MA C P ,et al. Graph neural network[J]. Scientia Sinica (Mathematica), 2020,(3): 367-384.
[26]	FAN W Q , MA Y , LI Q ,et al. Graph neural networks for social recommendation[C]// The World Wide Web Conference.New York:ACM Press. 2019: 417-426.
[27]	郭嘉琰, 李荣华, 张岩 ,等. 基于图神经网络的动态网络异常检测算法[J]. 软件学报, 2020,31(3): 748-762.
	GUO J Y , LI R H , ZHANG Y ,et al. Graph neural network based ano-maly detection in dynamic networks[J]. Journal of Software, 2020,31(3): 748-762.
[28]	李冬, 申德荣, 寇月 ,等. 基于层次化混合特征图的链路预测方法[J]. 中国科学（信息科学）, 2020,50(2): 221-238.
[52]	YE X Y , WAN M , TANG R ,et al. Clustering algorithm of social net-work based on graph clustering and ant colony optimization algo-rithm[J]. Application Research of Computers, 2020,37(6): 1670-1674,1687.

数据集	节点个数/个	边数/边	平均聚类系数	密度	同配性系数	SCC中的节点个数/个	SCC中的节点边数/边	估计直径	SCC	平均节点出度
新浪微博	37 864	593 832	67.40%	3.40%	54.90%	28 994	487 732	32	241	8.47
Twitter	49 822	709 223	59.10%	3.80%	38.10%	42 542	684 483	24	127	6.44
Facebook	38 942	493 801	72.40%	1.70%	39.40%	29 475	387 492	26	110	5.64
hep-ph	15 393	239 840	54.80%	0.40%	63.70%	13 874	203 342	14	173	9.83
astro-ph	19 831	493 208	65.00%	0.30%	49.20%	13 220	467 743	16	236	7.28
dblp-collab	389 403	2 783 964	59.40%	0.10%	39.10%	278 331	2 344 900	27	8 943	9.44
dblp-cite	26 495	398 504	14.30%	1.20%	-1.70%	11 048	284 931	8	5 639	8.28
polblogs	2 448	48 754	17.40%	2.40%	-3.50%	1227	35 622	6	374	12.09
patent-colla	609 444	5 890 483	60.40%	0.10%	27.10%	287 366	2 473 816	47	39 849	8.89

数据集	加权(yes/no)	控制(yes/no)	节点个数/个	边数/边	节点增加数/个	边增加数/边	平均聚类系数	密度	同配性系数	SCC中的节点个数/个	SCC中的节点边数/边	估计直径	SCC	平均节点出度
新浪微博	no	no	42 093	617 898	4 229	24 066	68.30%	4.10%	52.70%	29 864	509 483	31	487	10.78
Twitter	no	no	55 891	790 937	6 069	81 714	60.50%	4.70%	39.10%	43 880	728 839	21	268	9.89
Facebook	no	no	42 965	528 908	4 023	35 107	71.10%	1.60%	38.70%	31 285	459 833	24	139	7.84
hep-ph	no	no	17 833	268 337	2 440	28 497	55.20%	0.50%	65.70%	14 087	220 983	13	340	13.09
astro-ph	no	no	20 931	509 838	1 100	16 630	63.00%	0.20%	50.40%	16 908	567 480	15	309	9.89
dblp-collab	yes	no	390 084	2 980 456	681	196 492	59.20%	0.10%	40.90%	289 844	3 192 086	25	4 059	14.58
dblp-cite	yes	yes	27 709	409 836	1 214	11 332	15.20%	1.00%	-2.00%	16 094	310 929	7	6 784	10.35
polblogs	no	yes	2 694	51 297	246	2 543	24.50%	2.60%	-4.60%	2 094	43 957	5	509	11.98
patent-colla	yes	no	687 943	5 984 760	78 499	94 277	62.20%	0.10%	23.60%	309 821	3 587 939	42	40 939	16.83

参数	定义
TP	正确预测链接的数量
TN	正确的未预测链接的数量
FP	错误预测链接的数量
FN	错误的未预测链接的数量

基于子图演化与改进蚁群优化算法的社交网络链路预测方法

Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 52

相关文章 15

Metrics

推荐阅读 0

[1]	王璿, 张瑜, 周军锋, 陈子阳. 基于社交网络的影响力最大化算法[J]. 通信学报, 2022, 43(8): 151-163.
[2]	彭滔, 钟文韬, 王国军, 罗恩韬, 熊金波, 刘忆宁, Hao Wang. 移动社交网络中面向隐私保护的精确好友匹配[J]. 通信学报, 2022, 43(11): 90-103.
[3]	顾秋阳, 吴宝, 池仁勇. 基于高阶路径相似度的复杂网络链路预测方法[J]. 通信学报, 2021, 42(7): 61-69.
[4]	舒坚, 王启宁, 刘琳岚. 基于深度图嵌入的无人机自组网链路预测[J]. 通信学报, 2021, 42(7): 137-149.
[5]	何元智, 彭聪, 于季弘, 刘韵. 面向密集多波束组网的卫星通信系统资源调度算法[J]. 通信学报, 2021, 42(4): 109-118.
[6]	吴翼腾,于洪涛,黄瑞阳,李华巍. 采用组合方法进行链路预测的理论极限研究[J]. 通信学报, 2020, 41(6): 34-50.
[7]	刘树新,李星,陈鸿昶,王凯. 基于资源传输匹配度的复杂网络链路预测方法[J]. 通信学报, 2020, 41(6): 70-79.
[8]	卢毅,徐梦颖,周杰. 基于改进的免疫克隆蛙跳算法的多约束QoS路由优化研究[J]. 通信学报, 2020, 41(5): 141-149.
[9]	刘真,王娜娜,王晓东,孙永奇. 位置社交网络中谱嵌入增强的兴趣点推荐算法[J]. 通信学报, 2020, 41(3): 197-206.
[10]	陈晶,祁子怡. 基于时序关系的社交网络影响最大化算法研究[J]. 通信学报, 2020, 41(10): 211-221.
[11]	毕俊蕾,李致远. 机会社交网络中基于时变兴趣社区的查询消息路由算法[J]. 通信学报, 2019, 40(9): 86-94.
[12]	李凤华,孙哲,牛犇,曹进,李晖. 跨社交网络的隐私图片分享框架[J]. 通信学报, 2019, 40(7): 1-13.
[13]	黄海平,王凯,汤雄,张东军. 基于边介数模型的差分隐私保护方案[J]. 通信学报, 2019, 40(5): 88-97.
[14]	王晓萌, 方滨兴, 张宏莉, 王星. TSL：基于连接强度的Facebook消息流行度预测模型[J]. 通信学报, 2019, 40(10): 1-9.
[15]	闫光辉, 张萌, 罗浩, 李世魁, 刘婷. 融合高阶信息的社交网络重要节点识别算法[J]. 通信学报, 2019, 40(10): 109-118.