AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Big Data Mining and Analytics Article
PDF (6.9 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

DeepEye: Link Prediction in Dynamic Networks Based on Non-negative Matrix Factorization

Nahla Mohamed Ahmed, Ling Chen( ), Yulong Wang, Bin Li, Yun Li, Wei Liu
College of Information Engineering, Yangzhou University, Yangzhou 225009, China.
College of Mathematical Sciences, Khartoum University, Khartoum, Sudan.
State Key Lab of Novel Software Tech, Nanjing University, Nanjing 210093, China.
College of Agriculture, Yangzhou University, Yangzhou 225009, China.
Show Author Information

Abstract

A Non-negative Matrix Factorization (NMF)-based method is proposed to solve the link prediction problem in dynamic graphs. The method learns latent features from the temporal and topological structure of a dynamic network and can obtain higher prediction results. We present novel iterative rules to construct matrix factors that carry important network features and prove the convergence and correctness of these algorithms. Finally, we demonstrate how latent NMF features can express network dynamics efficiently rather than by static representation, thereby yielding better performance. The amalgamation of time and structural information makes the method achieve prediction results that are more accurate. Empirical results on real-world networks show that the proposed algorithm can achieve higher accuracy prediction results in dynamic networks in comparison to other algorithms.

Keywords

link predictionmatrix factorizationdynamic network

References

[1]
Ahmed N. M. and Chen L., An efficient algorithm for link prediction in temporal uncertain social networks, Inf. Sci., vol. 331, pp. 120-136, 2016.
Crossref Google Scholar
[2]
Buccafurri F., Fotia L., Lax G., and Saraswat V., Analysis-preserving protection of user privacy against information leakage of social-network Likes, Inf. Sci., vol. 328, pp. 340-358, 2016.
Crossref Google Scholar
[3]
Jankowski-Lorek M., Jaroszewicz S., Ostrowski Ł, and Wierzbicki A., Verifying social network models of Wikipedia knowledge community, Inf. Sci., vol. 339, pp. 158-174, 2016.
Crossref Google Scholar
[4]
Saito K., Kimura M., Ohara K., and Motoda H., Super mediator—A new centrality measure of node importance for information diffusion over social network, Inf. Sci., vol. 329, pp. 985-1000, 2016.
Crossref Google Scholar
[5]
Bhuyan M. H., Bhattacharyya D. K., and Kalita J. K., A multi-step outlier-based anomaly detection approach to network-wide traffic, Inf. Sci., vol. 348, pp. 243-271, 2016.
Crossref Google Scholar
[6]
Liao H., Zeng A., and Zhang Y. C., Predicting missing links via correlation between nodes, Physica A Stat. Mech. Appl., vol. 436, pp. 216-223, 2015.
Crossref Google Scholar
[7]
Wang P., Xu B. W., Wu Y. R., and Zhou X. Y., Link prediction in social networks: The state-of-the-art, Sci. China Inf. Sci., vol. 58, no. 1, pp. 1-38, 2015.
Crossref Google Scholar
[8]
Wang X. M., Liu Y., and Xiong F., Improved personalized recommendation based on a similarity network, Physica A Stat. Mech. Appl., vol. 456, pp. 271-280, 2016.
Crossref Google Scholar
[9]
Kaya B. and Poyraz M., Age-series based link prediction in evolving disease networks, Comput. Biol. Med., vol. 63, pp. 1-10, 2015.
Crossref Google Scholar
[10]
Guimerà R., Sales-Pardo M., and Stanley H. E., Missing and spurious interactions and the reconstruction of complex networks, Proc. Natl. Acad. Sci. USA, vol. 106, no. 52, pp. 22073-22078, 2009.
Crossref
[11]
Nigam A. and Chawla N. V., Link prediction in a semi-bipartite network for recommendation, in Intelligent Information and Database Systems, Nguyen N. T., Trawi ki B., Fujita H., and Hong T. P., eds. Springer, 2016, pp. 127-135.
Crossref
[12]
Xie F., Chen Z., Shang J. X., Feng X. P., and Li J., A link prediction approach for item recommendation with complex number, Knowl-Based Syst., vol. 81, pp. 148-158, 2015.
Crossref Google Scholar
[13]
Sun Z., Peng Q. K., Lv J., and Zhang J., A prediction model of post subjects based on information lifecycle in forum, Inf. Sci., vols. 337&338, pp. 59-71, 2016.
Crossref Google Scholar
[14]
Klimek P., Jovanovic A. S., Egloff R., and Schneider R., Successful fish go with the flow: Citation impact prediction based on centrality measures for term–document networks, Scientometrics, vol. 107, no. 3, pp. 1265-1282, 2016.
Crossref Google Scholar
[15]
Kaya B. and Poyraz M., Unsupervised link prediction in evolving abnormal medical parameter networks, Int.J. Mach. Learn. Cybern., vol. 7, no. 1, pp. 145-155, 2016.
Crossref Google Scholar
[16]
Ge M. Q., Li A., and Wang M. H., A bipartite network-based method for prediction of long non-coding RNA–protein interactions, Genomics Proteomics Bioinformatics, vol. 14, no. 1, pp. 62-71, 2016.
Crossref Google Scholar
[17]
Buccafurri F., Lax G., Nocera A., and Ursino D., Discovering missing me edges across social networks, Inf. Sci., vol. 319, pp. 18-37, 2015.
Crossref Google Scholar
[18]
Fournet J. and Barrat A., Contact patterns among high school students, PLoS One, vol. 9, no. 9, p. 107878, 2014.
Crossref Google Scholar
[19]
Ibrahim N. M. A. and Chen L., Link prediction in dynamic social networks by integrating different types of information, Appl. Intell., vol. 42, no. 4, pp. 738-750, 2015.
Crossref Google Scholar
[20]
Papadimitriou A., Symeonidis P., and Manolopoulos Y., Fast and accurate link prediction in social networking systems, J. Syst. Softw., vol. 85, no. 9, pp. 2119-2132, 2012.
Crossref Google Scholar
[21]
Sun Y. Z., Barber R., Gupta M., Aggarwal C. C., and Han J. W., Co-author relationship prediction in heterogeneous bibliographic networks, in Proc. 2011 Int. Conf. Advances in Social Networks Analysis and Mining (ASONAM 2011), Kaohsiung, China, 2011, pp. 121-128.
Crossref
[22]
Li J., Zhang L. L., Meng F., and Li F. H., Recommendation algorithm based on link prediction and domain knowledge in retail transactions, Procedia Comput. Sci., vol. 31, pp. 875-881, 2014.
Crossref Google Scholar
[23]
Li X. and Chen H., Recommendation as link prediction in bipartite graphs: A graph kernel-based machine learning approach, Decis. Supp. Syst., vol. 54, no. 2, pp. 880-890, 2013.
Crossref Google Scholar
[24]
Vidmer A., Zeng A., Medo M., and Zhang Y. C., Prediction in complex systems: The case of the international trade network, Physica A Stat. Mech. Appl., vol. 436, pp. 188-199, 2015.
Crossref Google Scholar
[25]
Kaya B. and Poyraz M., Supervised link prediction in symptom networks with evolving case, Measurement, vol. 56, pp. 231-238, 2014.
Crossref Google Scholar
[26]
Ma X., Liao J. L., Djouadi S. M., and Cao Q., LIPS: Link prediction as a service for data aggregation applications, Ad Hoc Networks, vol. 19, pp. 43-58, 2014.
Crossref Google Scholar
[27]
Aiello L. M., Barrat A., Schifanella R., Cattuto C., Markines B., and Menczer F., Friendship prediction and homophily in social media, ACM Trans. Web (TWEB), vol. 6, no. 2, p. 9, 2012.
Crossref Google Scholar
[28]
Ahn M. W. and Jung W. S., Accuracy test for link prediction in terms of similarity index: The case of WS and BA models, Phys. A Stat. Mech. Appl., vol. 429, pp. 177-183, 2015.
Crossref Google Scholar
[29]
Hoffman M., Steinley D., and Brusco M. J., A note on using the adjusted rand index for link prediction in networks, Soc. Networks, vol. 42, pp. 72-79, 2015.
Crossref Google Scholar
[30]
Lü L. Y. and Zhou T., Link prediction in complex networks: A survey, Phys. A Stat. Mech. Appl., vol. 390, no. 6, pp. 1150-1170, 2011.
Crossref Google Scholar
[31]
Wang X. J., Zhang X., Zhao C. L., Xie Z., Zhang S. J., and Yi D. Y., Predicting link directions using local directed path, Phys. A Stat. Mech. Appl., vol. 419, pp. 260-267, 2015.
Crossref Google Scholar
[32]
Das Sarma A., Molla A. R., and Pandurangan G., Distributed computation in dynamic networks via random walks, Theor. Comput. Sci., vol. 581, pp. 45-66, 2015.
Crossref Google Scholar
[33]
Liu W. P. and Lü L. Y., Link prediction based on local random walk, Europhys Lett, vol. 89, no. 5, p. 58007, 2010.
Crossref Google Scholar
[34]
Hu F. Y. and Wong H. S., Labeling of human motion based on cbga and probabilistic model, Int.J. Smart Sens. Intell. Syst., vol. 6, no. 2, pp. 583-609, 2013.
Crossref Google Scholar
[35]
Barbieri N., Bonchi F., and Manco G., Who to follow and why: Link prediction with explanations, in Proc. 20th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, New York, NY, USA, 2014, pp. 1266-1275.
Crossref
[36]
Gao S., Denoyer L., and Gallinari P., Temporal link prediction by integrating content and structure information, in Proc. 20th ACM Int. Conf. Information and Knowledge Management, 2011, pp. 1169-1174.
Crossref
[37]
Zeng Z. Z., Chen K. J., Zhang S. B., and Zhang H. J., A link prediction approach using semi-supervised learning in dynamic networks, in Proc. Sixth Int. Conf. Advanced Computational Intelligence (ICACI), Hangzhou, China, 2013, pp. 276-280.
Crossref
[38]
Pujari M. and Kanawati R., Supervised rank aggregation approach for link prediction in complex networks, in Proc. 21st Int. Conf. World Wide Web, Lyon, France, 2012, pp. 1189-1196.
Crossref
[39]
Bao Z. F., Zeng Y., and Tay Y. C., sonLP: Social network link prediction by principal component regression, in Proc. 2013 IEEE/ACM Int. Conf. Advances in Social Networks Analysis and Mining, Niagara Falls, Canada, 2013, pp. 364-371.
Crossref
[40]
He Y. L., Liu J. N. K., Hu Y. X., and Wang X. Z., OWA operator based link prediction ensemble for social network, Expert Syst. Appl., vol. 42, no. 1, pp. 21-50, 2015.
Crossref Google Scholar
[41]
Bliss C. A., Frank M. R., Danforth C. M., and Dodds P. S., An evolutionary algorithm approach to link prediction in dynamic social networks, J. Comput. Sci., vol. 5, no. 5, pp. 750-764, 2014.
Crossref Google Scholar
[42]
Sherkat E., Rahgozar M., and Asadpour M., Structural link prediction based on ant colony approach in social networks, Phys. A Stat. Mech. Appl., vol. 419, pp. 80-94, 2015.
Crossref Google Scholar
[43]
Chen B. L., Chen L., and Li B., A fast algorithm for predicting links to nodes of interest, Inf. Sci., vol. 329, pp. 552-567, 2016.
Crossref Google Scholar
[44]
Ding J. Y., Jiao L. C., Wu J. S., Hou Y. T., and Qi Y. T., Prediction of missing links based on multi-resolution community division, Phys. A Stat. Mech. Appl., vol. 417, pp. 76-85, 2015.
Crossref Google Scholar
[45]
Vu D. Q., Asuncion A. U., Hunter D. R., and Smyth P., Continuous-time regression models for longitudinal networks, in Advances in Neural Information Processing Systems 24, Proc. 25th Annual Conf. Neural Information Processing Systems, 2011, pp. 1-9.
[46]
http://www.cs.cmu.edu/~enron/, 2017.
[47]
http://konect.uni-koblenz.de/networks/enron, 2017.
[48]
http://nodobo.com/release.html, 2017.
[49]
SocioPatterns. DATASET: INFECTIOUS SocioPatterns dynamic contact networks, http://www.sociopatterns.org/datasets/infectious-sociopatterns-dynamic-contact-networks, 2011
Big Data Mining and Analytics
Volume 1 Issue 1,
March 2018
Pages 19-33
DOI: 10.26599/BDMA.2017.9020002
Cite this article:
Ahmed NM, Chen L, Wang Y, et al. DeepEye: Link Prediction in Dynamic Networks Based on Non-negative Matrix Factorization. Big Data Mining and Analytics, 2018, 1(1): 19-33. https://doi.org/10.26599/BDMA.2017.9020002

1090

Views

56

Downloads

57

Crossref

51

Web of Science

66

Scopus

0

CSCD

Altmetrics
Received: 27 July 2017
Accepted: 28 November 2017
Published: 25 January 2018
© The author(s) 2018
Return