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

Qiuyang GU; Chunhua JU; Gongxing WU

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

您当前的位置：

首页 >

文章列表页 >

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

Papers | 更新时间：2024-06-05

- Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm
- Journal on Communications Vol. 41, Issue 12, Pages: 21-35(2020)
- 作者机构：
  
  1. 浙江工业大学管理学院，浙江杭州 310023
  2. 浙江工业大学中国中小企业研究院，浙江杭州 310023
  3. 宁波诺丁汉大学商学院，浙江宁波 315175
  4. 浙江工商大学管理工程与电子商务学院，浙江杭州 310018
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(71571162);Zhejiang Social Science Planning Key Projects Fundation(20NDJC10Z);The Natural Science Foundation of Zhejiang Province(LQ20G010002)
- DOI：10.11959/j.issn.1000-436X.2020223
  CLC： TP391
- Online First：2020-12，
  
  Published：25 December 2020
- 稿件说明：
移动端阅览
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.
DOI：

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. DOI： 10.11959/j.issn.1000-436X.2020223.

摘要

基于改进蚁群优化算法与子图演化，提出了一种新型非监督社交网络链路预测（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.

关键词

Keywords

references

李永立 , 罗鹏 , 张书瑞 . 基于决策分析的社交网络链路预测方法 [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 .

WANG Z , LIANG J , LI R . A fusion probability matrix factorization framework for link prediction [J ] . Knowledge-Based Systems , 2018 , 159 : 72 - 85 .

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 .

王智强 , 梁吉业 , 李茹 . 基于信息融合的概率矩阵分解链路预测方法 [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 .

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 .

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 .

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 .

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 .

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 .

王守辉 , 于洪涛 , 黄瑞阳 , 等 . 基于模体演化的时序链路预测方法 [J ] . 自动化学报 , 2016 , 42 ( 5 ): 735 - 745 .

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 .

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

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 .

王凯 , 李星 , 兰巨龙 , 等 . 一种基于资源传输路径拓扑有效性的链路预测方法 [J ] . 电子与信息学报 , 2020 , 42 ( 3 ): 653 - 660 .

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 .

舒坚 , 张学佩 , 刘琳岚 , 等 . 基于深度卷积神经网络的多节点之间链路预测方法 [J ] . 电子学报 , 2018 , 46 ( 12 ): 2970 - 2977 .

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 .

DORIGO M , BLUM C . Ant colony optimization theory:a survey [J ] . Theoretical Computer Science , 2005 , 344 ( 2-3 ): 243 - 278 .

FADAEE S A , AMIR H M . Classification using link prediction [J ] . Neurocomputing , 2019 , 359 : 395 - 407 .

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 .

张子柯 . 在线社交网络信息传播机制与动力学研究综述 [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 .

ZHANG Q M , LYU L , WANG W Q , et al . Potential theory for directed networks [J ] . PLos One , 2013 , 8 ( 2 ): e55437 .

胡文斌 , 王欢 , 严丽平 , 等 . 混合指标量子群智能社会网络事件检测方法 [J ] . 软件学报 , 2016 , 27 ( 11 ): 2747 - 2762 .

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 .

郭丽媛 , 王智强 , 梁吉业 . 基于边重要度的矩阵分解链路预测算法 [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 .

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 .

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 .

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 .

白铂 , 刘玉婷 , 马驰骋 , 等 . 图神经网络 [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 .

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 .

郭嘉琰 , 李荣华 , 张岩 , 等 . 基于图神经网络的动态网络异常检测算法 [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 .

李冬 , 申德荣 , 寇月 , 等 . 基于层次化混合特征图的链路预测方法 [J ] . 中国科学（信息科学） , 2020 , 50 ( 2 ): 221 - 238 .

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 .

方哲 , 游宏梁 , 薛非 , 等 . 专家知识协作加权超网络模型及其超链路预测研究 [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 .

尚凤军 , 龚文娟 , 耿哲 . 基于链路预测和网络编码的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 .

HUANG Z . Link prediction based on graph topology:the predictive value of generalized clustering coefficient [J ] . SSRN Electronic Journal , 2010 : 1634014 .

黄璐 , 朱一鹤 , 张嶷 . 基于加权网络链路预测的新兴技术主题识别研究 [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 .

LATAPY M . Main-memory triangle computations for very large (sparse (power-law)) graphs [J ] . Theoretical Computer Science , 2008 , 407 ( 1 ): 458 - 473 .

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 .

刘树新 , 李星 , 陈鸿昶 , 等 . 基于资源传输匹配度的复杂网络链路预测方法 [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 .

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 .

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 .

DEAN J , GHEMAWAT S . MapReduce:simplified data processing on large clusters [J ] . Communications of the ACM , 2008 , 51 ( 1 ): 107 - 113 .

NEWMAN M E J . Assortative mixing in networks [J ] . Physical Review Letters , 2002 , 89 ( 20 ): 208701 .

LICHTENWALTER R N , CHAWLA N V . Lpmade:link prediction made easy [J ] . The Journal of Machine Learning Research , 2011 , 12 : 2489 - 2492 .

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 .

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 .

KATZ L . A new status index derived from sociometric analysis [J ] . Psychometrika , 1953 , 18 ( 1 ): 39 - 43 .

BRIN S , PAGE L . The anatomy of a large-scale hypertextual Web search engine [J ] . Computer Networks , 1998 , 30 : 107 - 117 .

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 .

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 .

李勇军 , 尹超 , 于会 , 等 . 基于最大熵模型的微博传播网络中的链路预测 [J ] . 物理学报 , 2016 , 65 ( 2 ): 31 - 41 .

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 .

翟东升 , 刘鹤 , 张杰 , 等 . 一种基于链路预测的技术机会挖掘方法 [J ] . 情报学报 , 2016 , 35 ( 10 ): 1090 - 1100 .

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 .

HAND D J . Measuring classifier performance:a coherent alternative to the area under the ROC curve [J ] . Machine Learning , 2009 , 77 ( 1 ): 103 - 123 .

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 .

肖婧 , 张永建 , 许小可 . 复杂网络模糊重叠社区检测研究进展 [J ] . 复杂系统与复杂性科学 , 2017 , 14 ( 3 ): 8 - 29 .

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 .

叶小莺 , 万梅 , 唐蓉 , 等 . 基于图聚类与蚁群优化算法的社交网络聚类算法 [J ] . 计算机应用研究 , 2020 , 37 ( 6 ): 1670 - 1674 , 1687 .

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 .

Views

2500

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Influence maximization algorithm based on social network

UAV ad hoc network link prediction based on deep graph embedding

Link prediction method based on the similarity of high path

Link prediction method based on matching degree of resource transmission for complex network

Theoretical limit of link prediction using a combination method

Related Author

Yu ZHANG

Junfeng ZHOU

Ziyang CHEN

Xuan WANG

Linlan LIU

Qining WANG

Jian SHU

Renyong CHI

Related Institution

School of Information Management, Shanghai Lixin University of Accounting and Finance

School of Computer Science and Technology, Donghua University

School of Information Engineering, Nanchang Hangkong University

School of Software, Nanchang Hangkong University

Information Technology Institute,Information Engineering University

AI问答

⁰