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

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

摘要/Abstract

摘要：

链路预测利用已知网络节点及结构等信息预测网络未知连接或未来连接。现有主流方法多应用于无向网络，而且部分有向链路预测方法忽视了共同邻居在有向网络下的多样异构特征。针对上述问题，提出了一种广义共同邻居算法。该方法首先对有向网络定义了广义共同邻居，通过网络中有向邻居异构体的连边概率衡量不同结构对连边贡献程度，然后利用该定义对现有的局部相似性指标进行了优化，重定义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.

Key words: directed network, link prediction, common neighbor, heterogeneous fusion

中图分类号:

TP301.6

赵学磊,季新生,刘树新,赵宇. 基于广义共同邻居的有向网络链路预测方法[J]. 网络与信息安全学报, 2020, 6(5): 89-100.

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.

图/表 9

图1

表1

表2

表3

表4

图2

表5

表6

图3

参考文献 45

[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.

结构编号	结构数目	连边数目	连边率
S1	1 022	244	23.90%
S2	4 239	327	7.70%
S3	3546	772	21.80%
S4	3 546	327	9.20%
S5	4 239	1 232	29.10%
S6	15 396	395	2.60%
S7	20 438	2 596	12.70%
S8	39 786	3 056	7.70%
S9	15 396	2 151	14.00%

数据集	\|V\|	\|E\|	k_{out_max}	K_{in_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