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

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

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 7

名称	无向网络	有向网络
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) \|}$

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

Metrics

Recommended 0

No Suggested Reading articles found!

名称	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

New method for link prediction in directed networks based on triad patterns

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 29

Related Articles 5

Metrics

Recommended 0

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