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

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

摘要/Abstract

摘要：

当前链路预测的研究主要集中在无向网络，然而现实世界中存在大量的有向网络，忽略链路的方向会缺失一些重要信息甚至使预测失去意义，而直接将无向网络的预测方法应用于有向网络又存在预测精度降低的问题。为此，提出了一个基于三元组的有向网络链路预测算法，该算法针对有向网络和无向网络三元组结构的不同，应用势理论对三元组进行筛选，通过统计分析不同三元组闭合的可能性，以网络整体三元组闭合指数作为权重计算节点间的相似性。在9个真实数据集上的实验表明，所提方法比基准方法的预测精度提高了4.3%。

关键词: 链路预测, 有向网络, 三元组

Abstract:

Almost all current studies on link prediction problem focus on undirected networks.Unfortunately,many complex networks in the real world are directed.Ignoring the direction of a link will overlook some important information or even make the prediction meaningless.Directly applying the methods for undirected networks to directed networks will reduce the accuracy of prediction.A new method for link prediction in directed networks based on triad patterns was proposed.The proposed metric compare the difference of triad structures between undirected and directed networks and use potential theory to filter the triad patterns.By statistics of triad closeness in various networks,new method calculate the similarity between nodes using the triad closeness index of a network as the weight for different triad patterns.Experiments on nine real networks show that accuracy of proposed method is 4.3% better than benchmark methods.

Key words: link prediction, directed networks, triad patterns

中图分类号:

TP393

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

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.

图/表 7

图1

图2

图3

图4

表1

表2

基于局部的链路预测算法"

名称	无向网络	有向网络
CN	$s (x, y) = \| Γ (x) \cap Γ (y) \|$	$s (x, y) = \| Γ out (x) \cap Γ in (y) \|$
AA	$s (x, y) = \sum_{z \in Γ (x) \cap Γ (y)} \frac{1}{\log \| Γ (z) \|}$	$s (x, y) = \sum_{z \in Γ out (x) \cap Γ in (y)} \frac{1}{\log \| Γ out (z) \|}$
RA	$s (x, y) = \sum_{z \in Γ (x) \cap Γ (y)} \frac{1}{\| Γ (z) \|}$	$s (x, y) = \sum_{z \in Γ out(x) \cap Γ in (y)} \frac{1}{\| Γ out (z) \|}$
JA	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\| Γ (x) \cup Γ (y) \|}$	$s (x, y) = \frac{\| Γ out (x) \cap Γ in (y) \|}{\| Γ out (x) \cup Γ in (y) \|}$
SA	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\sqrt{\| Γ (x) \| \times \| Γ (y) \|}}$	$s (x, y) = \frac{\| Γ out (x) \cap Γ in (y) \|}{\sqrt{\| Γ out (x) \| \times \| Γ in (y) \|}}$
SO	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\| Γ (x) \| + \| Γ (y) \|}$	$s (x, y) = \frac{\| Γ out (x) \cap Γ in (y) \|}{\| Γ out (x) \| + \| Γ in (y) \|}$
HPI	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\min {\| Γ (x) \|, \| Γ (y) \|}}$	$s (x, y) = \frac{\| Γ o u t (x) \cap Γ i n (y) \|}{\min {\| Γ o u t (x) \|, \| Γ i n (y) \|}}$
HDI	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\max {\| Γ (x) \|, \| Γ (y) \|}}$	$s (x, y) = \frac{\| Γ out (x) \cap Γ in (y) \|}{\max {\| Γ out (x) \|, \| Γ in (y) \|}}$
LHN	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\| Γ (x) \| \times \| Γ (y) \|}$	$s (x, y) = \frac{\| Γ out (x) \cap Γ in (y) \|}{\| Γ out (x) \| \times \| Γ in (y) \|}$

表2

表3

参考文献 29

[1]	LYU L , ZHOU T . Link prediction in complex networks:a survey[J]. Physica A:Statistical Mechanics And Its Applications, 2011,390(6): 1150-1170.
[2]	吕琳媛, 周涛 . 链路预测[M]. 北京: 教育出版社, 2013.
	LYU L Y , ZHOU T . Link prediction[M]. Beijing: Higher Education PressPress, 2013.
[3]	CLAUSET A , MOORE C , NEWMAN M E J . Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008,453: 98-101.
[4]	GUIMERA R , SALES-PARDO M . Missing and spurious interactions and the reconstruction of complex networks[J]. Proc Natl Sci Acad USA, 2009,106(52): 22073-22078.
[5]	ADAMIC L A , ADAR E . Friends and neighbors on the Web[J]. Social Networks, 2003,25(3): 211-230.
[6]	SALTON G , MCGILL M J . Introduction to modern information retrieval[M]. Auckland: MuGraw-HillPress, 1983.
[7]	JACCARD P . Etude comparative de la distribution floraledansune portion des Alpes et des Jura[J]. Bulletin de la SociétéVaudoise des Science Naturelles, 1901,37: 547-579.
[8]	ZHOU T , LYU L , ZHANG Y C . Predicting missing links via local information[J]. EurPhys J B, 2009,71(4): 623-630.
[9]	KATZ L . A new status index derived from sociometric analysis[J]. Psychometrika, 1953,18(1): 39-43.
[10]	BRIN S , PAGE L . The anatomy of a large-scale hypertextual Web search engine[J]. ComputNetw＆ ISDN Syst, 1998,30(1-7): 107-117.
[11]	NARAYANAN A , SHI E , RUBINSTEIN B I P . Link prediction by de-anonymization:how we won the kaggle social network challenge[C]// The 2011 International Joint Conference on Neural Networks (IJCNN). 2011: 1825-1834.
[12]	CORLETTE D , SHIPMAN F M . Link prediction applied to an open large-scale online social network[C]// The 21st ACM Conference on Hypertext and Hypermedia. 2010: 135-140.
[13]	LICHTENWALTER R N , LUSSIER J T , CHAWLA N V . New perspectives and methods in link prediction[C]// The 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2010: 243-252.
[14]	ZHANG Q M , LYU L , WANG W Q ,et al. Potential theory for directed networks[J]. PloS One, 2013,8(2):e55437.
[15]	AGHABOZORGI F , KHAYYAMBASHI M R . A new similarity measure for link prediction based on local structures in social networks[J]. Physica A:Statistical Mechanics and its Applications, 2018,501: 12-23.
[16]	BüTüN E , KAYA M , ALHAJJ R . Extension of neighbor-based link prediction methods for directed,weighted and temporal social networks[J]. Information Sciences, 2018.
[17]	YIN H , BENSON A R , LESKOVEC J ,et al. Local higher-order graph clustering[C]// The 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017: 555-564.
[18]	YAO Y , ZHANG R , YANG F ,et al. Link prediction in complex networks based on the interactions among paths[J]. Physica A:Statistical Mechanics and its Applications, 2018.
[19]	BAIRD D , LUCZKOVICH J , CHRISTIAN R R . Assessment of spatial and temporal variability in ecosystem attributes of the st marks national wildlife refuge,apalachee bay,florida[J]. Estuarine,Coastal and Shelf Science, 1998,47(3): 329-349.
[20]	WATTS D J , STROGATZ S H . Collective dynamics of“small-world” networks[J]. Nature, 1998,393(6684):440.
[21]	ADAMIC L A , GLANCE N . The political blogosphere and the 2004 US election:divided they blog[C]// The 3rd International Workshop on Link discovery. 2005: 36-43.
[22]	LESKOVEC J , HUTTENLOCHER D , KLEINBERG J . Predicting positive and negative links in online social networks[C]// The 19th International Conference on World Wide Web. 2010: 641-650.
[23]	LESKOVEC J , KLEINBERG J , FALOUTSOS C . Graph evolution:densification and shrinking diameters[J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2007,1(1):2.
[24]	HANELY J A , MCNEIL B J . The meaning and use of the area under a receiver operating characteristic (ROC) curve[J]. Radiology, 1982,143: 29-36.
[25]	吴祖峰, 梁棋, 刘峤 ,等. 基于 AdaBoost 的链路预测优化算法[J]. 通信学报, 2014,35(3): 116-123.
	WU Z F , LIANG Q , LIU Q ,et al. Modified link prediction algrithm based on AdaBoost[J]. Journal on Communications, 2014,35(3): 116-123.
[26]	SORENSEN T . 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]. BiolSkr, 1948,5(4): 1-34.
[27]	RAVASZ E , SOMERA A L , MONGRU D A ,et al. Hierarchical organization of modularity in metabolic networks[J]. Science, 2002,297(5586): 1553-1555.
[28]	LEICHT E A , HOLME P , NEWMAN M E J . Vertex similarity in networks[J]. Phys Rev E, 2006,73:026120.
[29]	DEVI S J , SINGH B . Analysis of link prediction in directed and weighted social network structure[C]// The International Symposium on Intelligent Systems Technologies and Applications. 2017: 1-13.

名称	S1数量	闭合指数	S2数量	闭合指数	S3数量	闭合指数	S4数量	闭合指数
E-mail	1 173 174	0.229 8	1 099 434	0.245 2	1 374 856	0.196 0	1 173 174	0.213 5
Kohonen	96 893	0.071 0	64 724	0.163	1 062 268	0.006 5	96 893	0
SmaGri	33 556	0.129 4	45 576	0.095 2	194 988	0.022 3	33 556	0
FWMW	16 010	0.353 6	35 242	0.160 6	26 372	0.214 7	16 010	0.134 4
CElegans	19 783	0.163 4	38 832	0.083 3	23 802	0.135 8	19 783	0.048 4
PB	503 959	0.247 5	1 244 750	0.099 4	697 328	0.178 9	503 959	0.094 7
Scimet	49 539	0.096 0	94 560	0.050 3	129 984	0.036 6	49 539	0.000 1
Wikivote	3 675 208	0.146 1	6 953 586	0.077 2	11 413 432	0.047 0	3 675 208	0.025 4
Gnutella	114 608	0.007 1	256 050	0.003 2	234 234	0.003 5	114 608	0.000 5
平均值	631 414	0.160 4	1 092 528	0.101 8	1 684 140	0.100 5	631 414	0.057

名称	无向网络	有向网络
CN	$s (x, y) = \| Γ (x) \cap Γ (y) \|$	$s (x, y) = \| Γ out (x) \cap Γ in (y) \|$
AA	$s (x, y) = \sum_{z \in Γ (x) \cap Γ (y)} \frac{1}{\log \| Γ (z) \|}$	$s (x, y) = \sum_{z \in Γ out (x) \cap Γ in (y)} \frac{1}{\log \| Γ out (z) \|}$
RA	$s (x, y) = \sum_{z \in Γ (x) \cap Γ (y)} \frac{1}{\| Γ (z) \|}$	$s (x, y) = \sum_{z \in Γ out(x) \cap Γ in (y)} \frac{1}{\| Γ out (z) \|}$
JA	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\| Γ (x) \cup Γ (y) \|}$	$s (x, y) = \frac{\| Γ out (x) \cap Γ in (y) \|}{\| Γ out (x) \cup Γ in (y) \|}$
SA	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\sqrt{\| Γ (x) \| \times \| Γ (y) \|}}$	$s (x, y) = \frac{\| Γ out (x) \cap Γ in (y) \|}{\sqrt{\| Γ out (x) \| \times \| Γ in (y) \|}}$
SO	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\| Γ (x) \| + \| Γ (y) \|}$	$s (x, y) = \frac{\| Γ out (x) \cap Γ in (y) \|}{\| Γ out (x) \| + \| Γ in (y) \|}$
HPI	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\min {\| Γ (x) \|, \| Γ (y) \|}}$	$s (x, y) = \frac{\| Γ o u t (x) \cap Γ i n (y) \|}{\min {\| Γ o u t (x) \|, \| Γ i n (y) \|}}$
HDI	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\max {\| Γ (x) \|, \| Γ (y) \|}}$	$s (x, y) = \frac{\| Γ out (x) \cap Γ in (y) \|}{\max {\| Γ out (x) \|, \| Γ in (y) \|}}$
LHN	$s (x, y) = \frac{\| Γ (x) \cap Γ (y) \|}{\| Γ (x) \| \times \| Γ (y) \|}$	$s (x, y) = \frac{\| Γ out (x) \cap Γ in (y) \|}{\| Γ out (x) \| \times \| Γ in (y) \|}$

名称	CN	AA	RA	JA	SA	SO	HPI	HDI	LHN	PTI	FPTI
E-mail	0.948 4	0.947 7	0.921 5	0.933 5	0.943 6	0.941 7	0.926 6	0.936 2	0.888 8	0.952	0.952 4
Kohonen	0.925 3	0.894 5	0.925 1	0.925 1	0.925	0.925 3	0.925 4	0.929 4	0.924 9	0.948 7	0.947 1
SmaGri	0.9085	0.883 4	0.907 9	0.905 7	0.906 4	0.905 8	0.907 6	0.905 6	0.905	0.945 5	0.937 7
FWMW	0.771 7	0.743 1	0.677 4	0.728 5	0.696 9	0.694 6	0.699 9	0.694 7	0.6163	0.736 3	0.717 8
CElegans	0.802 9	0.791 9	0.788 3	0.788 7	0.795	0.791 9	0.798 7	0.790 4	0.7861	0.876 9	0.868
PB	0.927	0.92	0.895 4	0.907	0.906 8	0.907 5	0.900 5	0.907 5	0.8783	0.941 2	0.940 2
Scimet	0.894 1	0.873	0.894 1	0.893 9	0.893 9	0.894 1	0.893 8	0.893 9	0.893 9	0.925 3	0.924 1
Wikivote	0.924 1	0.923 9	0.922 3	0.921 3	0.920 9	0.921 6	0.92	0.921 9	0.916 8	0.953 4	0.950 6
Gnutella	0.513 7	0.513 4	0.514	0.513 7	0.513 9	0.513 9	0.513 9	0.513 7	0.513 9	0.529 2	0.529 2