基于广义共同邻居的有向网络链路预测方法

赵学磊; 季新生; 刘树新; 赵宇

doi:10.11959/j.issn.2096-109x.2020059

您当前的位置：

首页 >

文章列表页 >

基于广义共同邻居的有向网络链路预测方法

学术论文 | 更新时间：2024-06-03

- 基于广义共同邻居的有向网络链路预测方法
- Link prediction methods based on generalized common neighbor in directed network
- 网络与信息安全学报 2020年6卷第5期页码：89-100
- 作者机构：
- 作者简介：
  
  [ "赵学磊（1996- ），男，河北石家庄人，信息工程大学硕士生，主要研究方向为复杂网络链路预测" ]
  [ "季新生（1968- ），男，河南驻马店人，信息工程大学教授、博士生导师，主要研究方向为网络空间安全、移动通信网络安全、拟态安全" ]
  [ "刘树新（1987- ），男，山东潍坊人，信息工程大学助理研究员，主要研究方向链路预测、通信网络安全" ]
  [ "赵宇（1984- ），男，吉林辽源人，信息工程大学讲师，主要研究方向为移动通信网络、新型网络体系结构" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61803384)
- DOI：10.11959/j.issn.2096-109x.2020059
  中图分类号： TP301.6
- 网络首发：2020-10，
  
  纸质出版：2020-10-15
- 稿件说明：
移动端阅览
赵学磊, 季新生, 刘树新, 等. 基于广义共同邻居的有向网络链路预测方法[J]. 网络与信息安全学报, 2020,6(5):89-100.

Xuelei ZHAO, Xinsheng JI, Shuxin LIU, et al. Link prediction methods based on generalized common neighbor in directed network[J]. Chinese Journal of Network and Information Security, 2020, 6(5): 89-100.
赵学磊, 季新生, 刘树新, 等. 基于广义共同邻居的有向网络链路预测方法[J]. 网络与信息安全学报, 2020,6(5):89-100. DOI： 10.11959/j.issn.2096-109x.2020059.

Xuelei ZHAO, Xinsheng JI, Shuxin LIU, et al. Link prediction methods based on generalized common neighbor in directed network[J]. Chinese Journal of Network and Information Security, 2020, 6(5): 89-100. DOI： 10.11959/j.issn.2096-109x.2020059.

摘要

链路预测利用已知网络节点及结构等信息预测网络未知连接或未来连接。现有主流方法多应用于无向网络，而且部分有向链路预测方法忽视了共同邻居在有向网络下的多样异构特征。针对上述问题，提出了一种广义共同邻居算法。该方法首先对有向网络定义了广义共同邻居，通过网络中有向邻居异构体的连边概率衡量不同结构对连边贡献程度，然后利用该定义对现有的局部相似性指标进行了优化，重定义8种基于广义共同邻居的有向相似性指标。在 12 个数据集上的实验表明，所提方法在两个衡量指标下普遍提升了现有预测指标性能。

Abstract

Link prediction aims to predict missing or future links through currently observed information of network.Existing mainstream methods are mostly applied to undirected network

and some methods designed for directed network ignored the diverse heterogeneous features of common neighbor.For this problem

a generalized common neighbor algorithm was proposed.Firstly

a generalized common neighbor was defined for the directed network.Then the degree of contribution of different structures was measured by the joint edge probability of the directed neighbor isomers

and the existing undirected local similarity index is improved by the new definition

redefining eight kinds of directed similarity indicators based on generalized common neighbor.Experiments on 12 datasets show that proposed method generally improves the performance of existing predictive indicators under two metrics.

关键词

Keywords

references

BENSON A , KLEINBERG J . Link prediction in networks with core-fringe data [C ] // The World Wide Web Conference . 2019 : 94 - 104 .

PUJARI M , KANAWATI R . Link prediction in complex networks [M ] // Advanced Methods for Complex Network Analysis . IGI Global , 2016 : 58 - 97 .

LYU L Y , ZHOU T . Link prediction in complex networks:a survey [J ] . Physica A Statistical Mechanics ＆ Its Applications , 2011 , 390 ( 6 ): 1150 - 1170 .

吕琳媛 . 复杂网络链路预测 [J ] . 电子科技大学学报 , 2010 , 39 ( 5 ): 651 - 661 .

LYU L Y . Complex network link prediction [J ] . Journal of Electronic Science and Technology , 2010 , 39 ( 5 ): 651 - 661 .

MERING C V , JENSEN L J , SNEL B , et al . STRING:known and predicted protein–protein associations,integrated and transferred across organisms [J ] . Nucleic Acids Research , 2005 , 33 : 433 - 7 .

SCELLATO S , NOULAS A , MASCOLO C . Exploiting place features in link prediction on location-based social networks [C ] // Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . 2011 : 1046 - 1054 .

DORAN D , . Stochastic blockmodeling [M ] // Network Role Mining and Analysis . 2017 : 63 - 76 .

王凯 , 刘树新 , 陈鸿昶 , 等 . 一种基于节点间资源承载度的链路预测方法 [J ] . 电子与信息学报 , 2019 , 41 ( 05 ): 214 - 223 .

WANG K , LIU S X , CHEN H C , et al . A new link prediction method for complex networks based on resources carrying capacity between nodes [J ] . Journal of Electronics and Information Technology , 2019 , 41 ( 5 ): 1225 - 1234 .

刘树新 , 季新生 , 刘彩霞 , 等 . 局部拓扑信息耦合促进网络演化 [J ] . 电子与信息学报 , 2016 , 38 ( 9 ): 2180 - 2187 .

LIU S X , JI X A , LIU C X , et al . Information coupling of local topology promoting the network evolution [J ] . Journal of Electronics and Information Technology , 2016 , 38 ( 9 ): 2180 - 2187 .

LIU S , JI X , LIU C , et al . Extended resource allocation index for link prediction of complex network [J ] . Physica A Statistical Mechanics ＆ Its Applications , 2017 , 479 : 174 - 183 .

LIU S , JI X , LIU C , et al . Similarity indices based on link weight assignment for link prediction of unweighted complex networks [J ] . International Journal of Modern Physics B , 2016 , 31 ( 2 ):1650254.

CHENG X Q , REN F X , SHEN H W , et al . Bridgeness:a local index on edge significance in maintaining global connectivity [J ] . Journal of Statistical Mechanics:Theory and Experiment , 2010 , 2010 ( 10 ):P10011.

LORRAIN F , WHITE H C . Structural equivalence of individuals in social networks [J ] . Social Networks , 1977 , 1 ( 1 ): 67 - 98 .

SHANG K K , SMALL M , YAN W S . Link direction for link prediction [J ] . Physica A:Statistical Mechanics and its Applications , 2016 , 469 : 767 - 776 .

SCHALL K K , DANIEL M . Link prediction in directed social networks [J ] . Social Network Analysis and Mining , 2014 , 4 ( 1 ): 157 - 334 .

VALVERDE-REBAZA J C , ROCHE M , PONCELET P , et al . The role of location and social strength for friendship prediction in location-based social networks [J ] . Information Processing ＆ Management , 2018 , 54 ( 4 ): 475 - 489 .

张扬夫 . 有向与加权网络的链路预测 [D ] . 湘潭:湘潭大学 , 2011 .

ZHANG Y F . Link prediction for directed and weighted networks [D ] . Xiangtan:Xiangtan University , 2011 .

SALTON G , MCGILL M J . Introduction to modern information retrieval [M ] . 1983 .

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 .

SøRENSEN T A . A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons [J ] . Biol.Skar. , 1948 , 5 : 1 - 34 .

RAVASZ E , SOMERA A L , MONGRU D A , et al . Hierarchical organization of modularity in metabolic networks [J ] . Science , 2002 , 297 ( 5586 ): 1551 - 1555 .

ZHOU T , LYU L , ZHANG Y C . Predicting missing links via local information [J ] . The European Physical Journal B , 2009 , 71 ( 4 ): 623 - 630 .

LEICHT E A , HOLME P , NEWMAN M E J . Vertex similarity in networks [J ] . Physical Review E , 2006 , 73 ( 2 ):026120.

ADAMIC L A , ADAR E . Friends and neighbors on the Web [J ] . Social Networks , 2003 , 25 ( 3 ): 211 - 230 .

OU Q , JIN Y D , ZHOU T , et al . Power-law strength-degree correlation from resource-allocation dynamics on weighted networks [J ] . Physical Review E Statistical Nonlinear ＆ Soft Matter Physics , 2007 , 75 ( 2 Pt 1 ):021102.

杨瑞琪 , 张月霞 . 一种时序有向社会网络中的链路预测算法 [J ] . 计算机工程 , 2019 , 45 ( 3 ): 203 - 207 .

YANG R Q , ZHANG Y X . A link prediction algorithm for temporal directed social network [J ] . Computer Engineering , 2019 , 45 ( 3 ): 203 - 207 .

BARABÁSI A L , ALBERT R . Emergence of scaling in random networks [J ] . Science , 1999 , 286 ( 5439 ): 509 - 512 .

LYU L , JIN C H , ZHOU T . Similarity index based on local paths for link prediction of complex networks [J ] . Physical Review E , 2009 , 80 ( 4 ):046122.

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

潘永昊 , 于洪涛 , 吴翼腾 . 基于复杂网络动力学模型的链路预测方法 [J ] . 网络与信息安全学报 , 2019 , 5 ( 6 ): 67 - 74 .

PAN Y H , YU H T , WU Y T . Link prediction method based on complex network dynamics model [J ] . Chinese Journal of Network and Information Security , 2019 , 5 ( 6 ): 67 - 74

常圣 , 马宏 , 刘树新 . 基于三元组结构的有向网链路预测方法 [J ] . 网络与信息安全学报 , 2019 , 5 ( 5 ): 39 - 47 .

CHANG S , MA H , LIU S X . New method for link prediction in directed networks based on triad patterns [J ] . Chinese Journal of Network and Information Security , 2019 , 5 ( 5 ): 39 - 47 .

BRZOZOWSKI M J , ROMERO D M . Who should I follow? recommending people in directed social networks [C ] // Fifth International AAAI Conference on Weblogs and Social Media . 2011 .

MARTÍNEZ V , BERZAL F , CUBERO J C . A survey of link prediction in complex networks [J ] . ACM Computing Surveys (CSUR) , 2016 , 49 ( 4 ): 1 - 33 .

ZENG G , ZENG E . On the three-way equivalence of AUC in credit scoring with tied scores [J ] . Communications in Statistics-Theory and Methods , 2019 , 48 ( 7 ): 1635 - 1650 .

ZHOU T , REN J , MEDO M , et al . Bipartite network projection and personal recommendation [J ] . Physical Review E , 2007 , 76 ( 4 ):046115.

KISH L , et al . Introduction to mathematical sociology [J ] . Social Forces , 1965 , 44 ( 2 ): 252 - 253 .

FREEMAN L C , WEBSTER C M , KIRKE D M . Exploring social structure using dynamic three-dimensional color images [J ] . Social networks , 1998 , 20 ( 2 ): 109 - 118 .

MOODY J . Peer influence groups:identifying dense clusters in large networks [J ] . Social Networks , 2001 , 23 ( 4 ): 261 - 283 .

COLEMAN J , MENZEL K H . The diffusion of an innovation among physicians [J ] . Sociometry , 1957 , 20 ( 4 ): 253 - 270 .

OPSAHL T . Why anchorage is not (that) important:binary ties and sample selection [EB ] .

OPSAHL T , AGNEESSENS F , SKVORETZ J . Node centrality in weighted networks:generalizing degree and shortest paths [J ] . Social Networks , 2010 , 32 ( 3 ): 245 - 251 .

WATTS D J , STROGATZ S H . Collective dynamics of‘small-world’networks [J ] . Nature , 1998 , 393 ( 6684 ):440.

BATAGELJ V , MRVAR A . Pajek—analysis and visualization of large networks [J ] . Lecture Notes in Computer Science , 2002 , 2265 : 77 - 103 .

LESKOVEC J , HUTTENLOCHER D , KLEINBERG J . Governance in social media:a case study of the Wikipedia promotion process [C ] // Fourth International AAAI Conference on Weblogs and Social Media . 2010 .

KUNEGIS J . Handbook of Network Analysis[KONECT -- the Koblenz Network Collection] [J ] . Computer Science , 2014 ( 2 ): 1343 - 1350 .

浏览量

243

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于SCL-CMM模型的超网络链路预测方法

面向强稀疏性移动社交网络的链路预测深度学习方法

基于节点匹配度的动态网络链路预测方法

基于复杂网络动力学模型的链路预测方法

基于三元组结构的有向网链路预测方法