Chinese Journal of Network and Information Security ›› 2020, Vol. 6 ›› Issue (5): 89-100.doi: 10.11959/j.issn.2096-109x.2020059
• Papers • Previous Articles Next Articles
Xuelei ZHAO(),Xinsheng JI,Shuxin LIU,Yu ZHAO
Revised:
2020-02-13
Online:
2020-10-15
Published:
2020-10-19
Supported by:
CLC Number:
Xuelei ZHAO,Xinsheng JI,Shuxin LIU,Yu ZHAO. Link prediction methods based on generalized common neighbor in directed network[J]. Chinese Journal of Network and Information Security, 2020, 6(5): 89-100.
"
数据集 | |V| | |E| | kout_max | Kin_max | <K> | C |
HS | 70 | 366 | 18 | 12 | 5.23 | 0.46 |
RS | 217 | 2 672 | 34 | 51 | 12.31 | 0.36 |
AH | 2 539 | 12 969 | 27 | 10 | 5.11 | 0.15 |
PH | 241 | 1 098 | 26 | 9 | 4.56 | 0.31 |
UA | 1 574 | 28 236 | 294 | 302 | 17.94 | 0.5 |
OF | 2 939 | 30 501 | 236 | 237 | 10.38 | 0.45 |
CE | 297 | 2 345 | 134 | 39 | 7.9 | 0.29 |
SM | 3 084 | 10 412 | 121 | 104 | 3.38 | 0.15 |
KH | 4 469 | 12 729 | 51 | 735 | 2.85 | 0.21 |
WV | 7 115 | 103 689 | 457 | 893 | 14.57 | 0.14 |
CH | 7 301 | 65 001 | 140 | 152 | 8.9 | 0.18 |
AC | 1 226 | 2 613 | 20 | 24 | 2.13 | 0.07 |
"
数据集 | CN | GMCN | PA | LP | Katz |
HS | 0.843 | 0.893 | 0.646 | 0.872 | 0.878 |
RH | 0.883 | 0.912 | 0.666 | 0.891 | 0.892 |
AH | 0.717 | 0.807 | 0.684 | 0.779 | 0.877 |
PH | 0.76 | 0.863 | 0.71 | 0.849 | 0.933 |
UA | 0.971 | 0.975 | 0.953 | 0.976 | 0.964 |
OF | 0.972 | 0.98 | 0.933 | 0.986 | 0.981 |
CE | 0.795 | 0.882 | 0.806 | 0.85 | 0.867 |
SM | 0.895 | 0.927 | 0.956 | 0.969 | 0.997 |
KH | 0.922 | 0.931 | 0.982 | 0.982 | 0.999 |
WV | 0.921 | 0.95 | 0.982 | 0.979 | 0.985 |
CH | 0.787 | 0.906 | 0.886 | 0.919 | 0.944 |
AC | 0.608 | 0.7 | 0.857 | 0.699 | 0.9 |
"
数据集 | Salton | GMSalton | Jaccard | GMJaccard | S?renson | GMS?renson | HPI | GMHPI | HDI | GMHDI | LHN | GMLHN | AA | GMAA | RA | GMRA |
HS | 0.845 | 0.899 | 0.844 | 0.888 | 0.847 | 0.879 | 0.843 | 0.887 | 0.844 | 0.888 | 0.862 | 0.924 | 0.845 | 0.881 | 0.843 | 0.901 |
RH | 0.887 | 0.919 | 0.885 | 0.91 | 0.886 | 0.904 | 0.882 | 0.901 | 0.882 | 0.906 | 0.872 | 0.899 | 0.886 | 0.903 | 0.881 | 0.89 |
AH | 0.717 | 0.808 | 0.715 | 0.809 | 0.716 | 0.808 | 0.715 | 0.808 | 0.717 | 0.807 | 0.711 | 0.805 | 0.714 | 0.751 | 0.716 | 0.735 |
PH | 0.755 | 0.861 | 0.756 | 0.853 | 0.758 | 0.857 | 0.758 | 0.861 | 0.756 | 0.854 | 0.751 | 0.875 | 0.746 | 0.836 | 0.744 | 0.775 |
UA | 0.953 | 0.961 | 0.949 | 0.954 | 0.951 | 0.952 | 0.923 | 0.936 | 0.949 | 0.952 | 0.872 | 0.872 | 0.972 | 0.977 | 0.974 | 0.984 |
OF | 0.968 | 0.976 | 0.967 | 0.975 | 0.967 | 0.976 | 0.962 | 0.97 | 0.966 | 0.975 | 0.954 | 0.96 | 0.974 | 0.979 | 0.974 | 0.975 |
CE | 0.785 | 0.856 | 0.785 | 0.821 | 0.784 | 0.844 | 0.789 | 0.84 | 0.781 | 0.816 | 0.777 | 0.787 | 0.802 | 0.871 | 0.801 | 0.811 |
SM | 0.893 | 0.925 | 0.895 | 0.921 | 0.893 | 0.925 | 0.894 | 0.925 | 0.893 | 0.923 | 0.893 | 0.921 | 0.87 | 0.909 | 0.888 | 0.923 |
KH | 0.923 | 0.94 | 0.924 | 0.932 | 0.923 | 0.939 | 0.922 | 0.945 | 0.924 | 0.932 | 0.925 | 0.931 | 0.894 | 0.917 | 0.923 | 0.93 |
WV | 0.918 | 0.941 | 0.919 | 0.93 | 0.919 | 0.944 | 0.914 | 0.94 | 0.919 | 0.932 | 0.911 | 0.914 | 0.922 | 0.943 | 0.919 | 0.943 |
CH | 0.789 | 0.903 | 0.79 | 0.904 | 0.788 | 0.903 | 0.79 | 0.902 | 0.789 | 0.904 | 0.789 | 0.9 | 0.787 | 0.904 | 0.789 | 0.909 |
AC | 0.606 | 0.7 | 0.606 | 0.699 | 0.606 | 0.696 | 0.606 | 0.698 | 0.609 | 0.699 | 0.607 | 0.697 | 0.603 | 0.677 | 0.615 | 0.693 |
"
数据集 | CN | GMCN | PA | LP | Katz |
HS | 0.159 | 0.093 | 0.397 | 0.152 | 0.139 |
RH | 0.12 | 0.094 | 0.358 | 0.111 | 0.112 |
AH | 0.256 | 0.17 | 0.316 | 0.201 | 0.123 |
PH | 0.188 | 0.102 | 0.297 | 0.11 | 0.06 |
UA | 0.027 | 0.023 | 0.048 | 0.024 | 0.035 |
OF | 0.025 | 0.019 | 0.068 | 0.015 | 0.018 |
CE | 0.178 | 0.114 | 0.199 | 0.143 | 0.13 |
SM | 0.131 | 0.098 | 0.042 | 0.045 | 0.003 |
KH | 0.084 | 0.067 | 0.017 | 0.018 | 0.001 |
WV | 0.077 | 0.052 | 0.02 | 0.02 | 0.015 |
CH | 0.139 | 0.071 | 0.119 | 0.07 | 0.054 |
AC | 0.232 | 0.192 | 0.145 | 0.197 | 0.089 |
"
数据集 | Salton | GMSalton | Jaccard | GMJaccard | S?renson | GMS?renson | HPI | GMHPI | HDI | GMHDI | LHN | GMLHN | AA | GMAA | RA | GMRA |
HS | 0.15 | 0.085 | 0.151 | 0.087 | 0.151 | 0.097 | 0.154 | 0.091 | 0.153 | 0.091 | 0.137 | 0.118 | 0.135 | 0.115 | 0.136 | 0.093 |
RH | 0.117 | 0.098 | 0.118 | 0.098 | 0.118 | 0.104 | 0.119 | 0.105 | 0.121 | 0.102 | 0.119 | 0.103 | 0.104 | 0.089 | 0.104 | 0.082 |
AH | 0.256 | 0.17 | 0.256 | 0.17 | 0.256 | 0.17 | 0.256 | 0.17 | 0.256 | 0.17 | 0.255 | 0.175 | 0.257 | 0.181 | 0.255 | 0.178 |
PH | 0.187 | 0.101 | 0.188 | 0.11 | 0.188 | 0.104 | 0.187 | 0.103 | 0.189 | 0.109 | 0.177 | 0.115 | 0.176 | 0.12 | 0.175 | 0.112 |
UA | 0.046 | 0.039 | 0.048 | 0.047 | 0.048 | 0.047 | 0.074 | 0.064 | 0.05 | 0.049 | 0.126 | 0.124 | 0.027 | 0.022 | 0.025 | 0.02 |
OF | 0.03 | 0.024 | 0.03 | 0.025 | 0.03 | 0.025 | 0.035 | 0.029 | 0.031 | 0.026 | 0.042 | 0.039 | 0.024 | 0.017 | 0.022 | 0.016 |
CE | 0.187 | 0.156 | 0.19 | 0.18 | 0.19 | 0.153 | 0.183 | 0.164 | 0.192 | 0.182 | 0.241 | 0.188 | 0.166 | 0.128 | 0.165 | 0.113 |
SM | 0.131 | 0.101 | 0.131 | 0.103 | 0.131 | 0.101 | 0.131 | 0.101 | 0.131 | 0.103 | 0.136 | 0.106 | 0.166 | 0.128 | 0.135 | 0.105 |
KH | 0.084 | 0.068 | 0.084 | 0.078 | 0.084 | 0.072 | 0.084 | 0.067 | 0.084 | 0.079 | 0.079 | 0.069 | 0.119 | 0.092 | 0.078 | 0.066 |
WV | 0.081 | 0.055 | 0.08 | 0.071 | 0.08 | 0.057 | 0.083 | 0.061 | 0.08 | 0.068 | 0.086 | 0.073 | 0.075 | 0.059 | 0.076 | 0.057 |
CH | 0.14 | 0.072 | 0.139 | 0.071 | 0.139 | 0.072 | 0.14 | 0.074 | 0.139 | 0.072 | 0.14 | 0.076 | 0.139 | 0.072 | 0.138 | 0.071 |
AC | 0.233 | 0.193 | 0.233 | 0.194 | 0.233 | 0.193 | 0.233 | 0.193 | 0.233 | 0.194 | 0.244 | 0.198 | 0.248 | 0.206 | 0.244 | 0.197 |
[1] | BENSON A , KLEINBERG J . Link prediction in networks with core-fringe data[C]// The World Wide Web Conference. 2019: 94-104. |
[2] | PUJARI M , KANAWATI R . Link prediction in complex networks[M]// Advanced Methods for Complex Network Analysis. IGI Global, 2016: 58-97. |
[3] | LYU L Y , ZHOU T . Link prediction in complex networks:a survey[J]. Physica A Statistical Mechanics & Its Applications, 2011,390(6): 1150-1170. |
[4] | 吕琳媛 . 复杂网络链路预测[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. | |
[5] | 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. |
[6] | 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. |
[7] | DORAN D , . Stochastic blockmodeling[M]// Network Role Mining and Analysis. 2017: 63-76. |
[8] | 王凯, 刘树新, 陈鸿昶 ,等. 一种基于节点间资源承载度的链路预测方法[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. | |
[9] | 刘树新, 季新生, 刘彩霞 ,等. 局部拓扑信息耦合促进网络演化[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. | |
[10] | 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. |
[11] | 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. |
[12] | 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. |
[13] | LORRAIN F , WHITE H C . Structural equivalence of individuals in social networks[J]. Social Networks, 1977,1(1): 67-98. |
[14] | 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. |
[15] | SCHALL K K , DANIEL M .Link prediction in directed social networks[J]. Social Network Analysis and Mining, 2014,4(1): 157-334. |
[16] | 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. |
[17] | 张扬夫 . 有向与加权网络的链路预测[D]. 湘潭:湘潭大学, 2011. |
ZHANG Y F . Link prediction for directed and weighted networks[D]. Xiangtan:Xiangtan University, 2011. | |
[18] | SALTON G , MCGILL M J . Introduction to modern information retrieval[M]. 1983. |
[19] | 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. |
[20] | 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. |
[21] | RAVASZ E , SOMERA A L , MONGRU D A ,et al. Hierarchical organization of modularity in metabolic networks[J]. Science, 2002,297(5586): 1551-1555. |
[22] | ZHOU T , LYU L , ZHANG Y C . Predicting missing links via local information[J]. The European Physical Journal B, 2009,71(4): 623-630. |
[23] | LEICHT E A , HOLME P , NEWMAN M E J . Vertex similarity in networks[J]. Physical Review E, 2006,73(2):026120. |
[24] | ADAMIC L A , ADAR E . Friends and neighbors on the Web[J]. Social Networks, 2003,25(3): 211-230. |
[25] | 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. |
[26] | 杨瑞琪, 张月霞 . 一种时序有向社会网络中的链路预测算法[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. | |
[27] | BARABáSI A L , ALBERT R . Emergence of scaling in random networks[J]. Science, 1999,286(5439): 509-512. |
[28] | 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. |
[29] | KATZ L . A new status index derived from sociometric analysis[J]. Psychometrika, 1953,18(1): 39-43. |
[30] | 潘永昊, 于洪涛, 吴翼腾 . 基于复杂网络动力学模型的链路预测方法[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 | |
[31] | 常圣, 马宏, 刘树新 . 基于三元组结构的有向网链路预测方法[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. | |
[32] | 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. |
[33] | 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. |
[34] | 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. |
[35] | ZHOU T , REN J , MEDO M ,et al. Bipartite network projection and personal recommendation[J]. Physical Review E, 2007,76(4):046115. |
[36] | KISH L ,et al.Introduction to mathematical sociology[J]. Social Forces, 1965,44(2): 252-253. |
[37] | 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. |
[38] | MOODY J . Peer influence groups:identifying dense clusters in large networks[J]. Social Networks, 2001,23(4): 261-283. |
[39] | COLEMAN J , MENZEL K H . The diffusion of an innovation among physicians[J]. Sociometry, 1957,20(4): 253-270. |
[40] | OPSAHL T . Why anchorage is not (that) important:binary ties and sample selection[EB]. |
[41] | OPSAHL T , AGNEESSENS F , SKVORETZ J . Node centrality in weighted networks:generalizing degree and shortest paths[J]. Social Networks, 2010,32(3): 245-251. |
[42] | WATTS D J , STROGATZ S H . Collective dynamics of‘small-world’networks[J]. Nature, 1998,393(6684):440. |
[43] | BATAGELJ V , MRVAR A . Pajek—analysis and visualization of large networks[J]. Lecture Notes in Computer Science, 2002,2265: 77-103. |
[44] | 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. |
[45] | KUNEGIS J . Handbook of Network Analysis[KONECT -- the Koblenz Network Collection][J]. Computer Science, 2014(2): 1343-1350. |
[1] | Yuhang ZHU, Lixin JI, Yingle LI, Haitao LI, Shuxin LIU. Temporal link prediction method based on community multi-features fusion and embedded representation [J]. Chinese Journal of Network and Information Security, 2023, 9(1): 67-82. |
[2] | Cong LI, Xinsheng JI, Ushuxin LI, Jinsong LI, Haitao LI. Link prediction method for dynamic networks based on matching degree of nodes [J]. Chinese Journal of Network and Information Security, 2022, 8(4): 131-143. |
[3] | Yonghao PAN,Hongtao YU,Yiteng WU. Link prediction method based on complex network dynamics model [J]. Chinese Journal of Network and Information Security, 2019, 5(6): 67-74. |
[4] | Sheng CHANG, Hong MA, Shuxin LIU. 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. |
[5] | Yonghao PAN,Hongtao YU,Shuxin LIU. Neural network-based link prediction algorithm [J]. Chinese Journal of Network and Information Security, 2018, 4(7): 30-38. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||
|