Abstract
In this work, we are concerned with uncertain networks and focus on the problem of link prediction with edge uncertainty. Networks with edge uncertainty are networks where connections between nodes are observed with some probability. We propose the uncertain version of the popular neighbors-based metrics for link prediction. The metrics are developed by considering all possible worlds generated by the uncertain network. We state that by taking all possible worlds of the uncertain network into account, the performance of link prediction can be improved. Since uncertain edges result in a very large number of possible worlds, we propose an efficient divide and conquer algorithm to reduce time complexity and calculate these metrics. Finally, we evaluate our metrics using existing ground truth to show the effectiveness of our proposed approach against other popular link prediction methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Newman, M.E.: Clustering and preferential attachment in growing networks. Phys. Rev. E 64(2), 025102 (2001)
Salton, G., McGill, M.J.: Introduction to Modern Information Retrieval (1986)
Jaccard, P.: Étude comparative de la distribution florale dans une portion des alpes et des jura. Bull. Soc. Vaudoise Sci. Nat. 37, 547–579 (1901)
Adamic, L.A., Adar, E.: Friends and neighbors on the web. Soc. Netw. 25(3), 211–230 (2003)
Zhou, T., Lü, L., Zhang, Y.-C.: Predicting missing links via local information. Eur. Phys. J. B-Condens. Matter Complex Syst. 71(4), 623–630 (2009)
Lü, L., Jin, C.-H., Zhou, T.: Similarity index based on local paths for link prediction of complex networks. Phys. Rev. E 80(4), 046122 (2009)
Liu, W., Lü, L.: Link prediction based on local random walk. EPL (Europhys. Lett.) 89(5), 58007 (2010)
Liu, Z., Zhang, Q.-M., Lü, L., Zhou, T.: Link prediction in complex networks: a local naïve Bayes model. EPL (Europhys. Lett.) 96(4), 48007 (2011)
Perozzi, B., Al-Rfou, R., Skiena, S.: DeepWalk: online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 701–710. ACM (2014)
Ahmed, N.M., Chen, L.: An efficient algorithm for link prediction in temporal uncertain social networks. Inf. Sci. 331, 120–136 (2016)
Mallek, S., Boukhris, I., Elouedi, Z., Lefevre, E.: Evidential missing link prediction in uncertain social networks. In: Carvalho, J.P., Lesot, M.-J., Kaymak, U., Vieira, S., Bouchon-Meunier, B., Yager, R.R. (eds.) IPMU 2016. CCIS, vol. 610, pp. 274–285. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40596-4_24
Murata, T., Moriyasu, S.: Link prediction of social networks based on weighted proximity measures. In: Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, pp. 85–88. IEEE Computer Society (2007)
Krogan, N.J., et al.: Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature 440(7084), 637 (2006)
Pfeiffer, J.J., Neville, J.: Probabilistic paths and centrality in time. In: Proceedings of the 4th SNA-KDD Workshop, KDD 2010 (2010)
Zhang, C., Zaïane, O.R.: Detecting local communities in networks with edge uncertainty. In: 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 9–16. IEEE (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhang, C., Zaïane, O.R. (2019). Neighbor-Based Link Prediction with Edge Uncertainty. In: Yang, Q., Zhou, ZH., Gong, Z., Zhang, ML., Huang, SJ. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2019. Lecture Notes in Computer Science(), vol 11440. Springer, Cham. https://doi.org/10.1007/978-3-030-16145-3_36
Download citation
DOI: https://doi.org/10.1007/978-3-030-16145-3_36
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-16144-6
Online ISBN: 978-3-030-16145-3
eBook Packages: Computer ScienceComputer Science (R0)