Abstract
Currently, data in many applications have naturally been modeled as streams over the massive graph infrastructure, e.g., social networks and electronic business. Graph streams are rapidly changing, enormous and endless networks that are too large to maintain in memory or on disks. An important problem in networks is link prediction, which aims to estimate the likelihood of the existence of a specific link. However, in graph streams, predicting the existence of links connected to one vertex is more common. For example, in social networks, we generally want to recommend several friends to a user rather than determining whether a specific user is your friend. Rapidly and accurately predicting groups of links becomes a formidable challenge because of the tremendous size and rapidly updated information of graph streams. In this paper, we propose the problem of link prediction for vertex in graph streams, which aims to predict the top-k vertices, i.e., the top-k links, that are most likely to connect to the target vertex in graph streams. A two-phase selection framework is proposed to predict top-k links with high efficiency and without loss of accuracy. We also propose a novel method for estimating common neighbor in graph streams, which is a very important measure in link prediction. Extensive experiments show that our algorithms are more efficient and more accurate than state-of-the-art methods.
F. Zhao—This work was supported in part by National Natural Science Foundation of China under Grants No. 61672256 and Guandong Science and Technology Plan under Grants no. 2017B030305003.
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
Li, X., Chen, H.: Recommendation as link prediction in bipartite graphs: a graph kernel-based machine learning approach. Decis. Support Syst. 54(2), 880–890 (2013)
McGregor, A.: Graph stream algorithms: a survey. ACM SIGMOD Rec. 43(1), 9–20 (2014)
Menche, J., et al.: Uncovering disease-disease relationships through the incomplete interactome. Science 347(6224), 1257601 (2015)
Song, C., Ge, T., Chen, C., Wang, J.: Event pattern matching over graph streams. Proc. VLDB Endow. 8(4), 413–424 (2014)
Wang, P., Xu, B., Wu, Y., Zhou, X.: Link prediction in social networks: the state-of-the-art. Sci. China Inf. Sci. 58(1), 1–38 (2015)
Zhao, P., Aggarwal, C., He, G.: Link prediction in graph streams. In: Proceedings of 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pp. 553–564. IEEE (2016)
Zhao, P., Aggarwal, C.C., Wang, M.: gSketch: on query estimation in graph streams. Proc. VLDB Endow. 5(3), 193–204 (2011)
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
Xiao, Y., Huang, H., Zhao, F., Jin, H. (2019). TPLP: Two-Phase Selection Link Prediction for Vertex in Graph Streams. 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_40
Download citation
DOI: https://doi.org/10.1007/978-3-030-16145-3_40
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)