Open Access
Issue
Published:
25 January 2018
DeepEye: Link Prediction in Dynamic Networks Based on Non-negative Matrix Factorization
Ling Chen(
),
),
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
Download citation
1006
Views
49
Downloads
Citations
51
Crossref
48
WoS
62
Scopus
0
CSCD
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.
menu
Abstract
Full text
Outline
About this article
DeepEye: Link Prediction in Dynamic Networks Based on Non-negative Matrix Factorization
Ling Chen(
),
),
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 prediction, matrix factorization, dynamic network
References(49)
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[9]
Kaya B. and Poyraz M., Age-series based link prediction in evolving disease networks, Comput. Biol. Med., vol. 63, pp. 1-10, 2015.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[18]
Fournet J. and Barrat A., Contact patterns among high school students, PLoS One, vol. 9, no. 9, p. 107878, 2014.
[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.
[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.
[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.
[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.
[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.
[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.
[25]
Kaya B. and Poyraz M., Supervised link prediction in symptom networks with evolving case, Measurement, vol. 56, pp. 231-238, 2014.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[33]
Liu W. P. and Lü L. Y., Link prediction based on local random walk, Europhys Lett, vol. 89, no. 5, p. 58007, 2010.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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]
[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
Publication history
Copyright
Acknowledgements
Rights and permissions
Publication history
Received: 27 July 2017
Accepted: 28 November 2017
Published:
25 January 2018
Issue date: March 2018
Copyright
© The author(s) 2018
Acknowledgements
This research was supported in part by the National Natural Science Foundation of China (Nos. 61379066, 61702441, 61379064, 61472344, 61402395, 61702441, and 61602202); the Natural Science Foundation of Jiangsu Province (Nos. BK20130452, BK2012672, BK2012128, and BK20140492); the Natural Science Foundation of Education Department of Jiangsu Province (Nos. 12KJB520019, 13KJB520026, and 09KJB20013), and Six-talent-peak Project in Jiangsu Province (No. 2011-DZXX-032).
FEEDBACK 
TOP