×

Sampling-based algorithm for link prediction in temporal networks. (English) Zbl 1433.62274

Summary: The problem of link prediction in temporal networks has attracted considerable recent attention from various domains, such as sociology, anthropology, information science, and computer science. In this paper, we propose a fast similarity-based method to predict the potential links in temporal networks. In this method, we first combine the snapshots of the temporal network into a weighted graph. A proper damping factor is used to assign greater importance to more recent snapshots. Then, we construct a sub-graph centered at each node in the weighted graph by a random walk from the node. The sub-graph constructed consists of a set of paths starting from the given node. Because the similarity score is computed within such small sub-graphs centered at each node, the algorithm can greatly reduce the computation time. By choosing a proper number of sampled paths, we can restrict the error of the estimated similarities within a given threshold. While other random walk-based algorithms require \(O(n^3)\) time for a network with \(n\) nodes, the computation time of our algorithm is \(O(n^{2})\), which is the lowest time complexity of a similarity-based link prediction algorithm. Moreover, because the proposed method integrates temporal and global topological information in the network, it can yield more accurate results. The experimental results on real networks show that our algorithm demonstrates the best or comparable quality results in less time than other methods.

MSC:

62M20 Inference from stochastic processes and prediction
90B15 Stochastic network models in operations research
60G50 Sums of independent random variables; random walks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmed, H. S.; Faouzi, B. M.; Caelen, J., Detection and classification of the behavior of people in an intelligent building by camera, Int. J. Smart Sensing Intel. Syst., 6, 4, 1317-1342 (2013)
[2] Aiello, L. M.; Barrat, A.; Schifanella, R., Friendship prediction and homophily in social media, ACM Trans. Web (TWEB), 6, 2, 9 (2012)
[3] Antonellis, I.; Molina, H. G.; Chang, C. C., Smrank++: query rewriting through link analysis of the click graph, PVLDB, 1, 1, 408-421 (2008)
[4] Bao, Z. F.; Zeng, Y.; Tay, Y. C.; son, LP, social network link prediction by principal component regression, (Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (2013)), August
[5] Barbieri, N.; Bonchi, F.; Manco, G., Who to follow and why: link prediction with explanations, (Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2014)), 1266-1275
[6] Bliss, C. A.; Frank, MorganR.; Danforth, C. M.; Dodds, P. S., An evolutionary algorithm approach to link prediction in dynamic social networks, J. Comput. Sci., 5, 5, 750-764 (2014), September
[7] Bringmann, B.; Berlingerio, M.; Bonchi, F.; Gionis, A., Learning and predicting the evolution of social networks, IEEE Intell. Syst., 26-34 (2010)
[8] Chaintreau, A.; Hui, P.; Crowcroft, J.; Diot, C.; Gass, R.; Scott, J., Impact of human mobility on opportunistic forwarding algorithms, IEEE Trans. Mob. Comput., 6, 6, 606-620 (2007)
[9] Chen, B.; Chen, L.; Li, B., A fast algorithm for predicting links to nodes of interest, Inf. Sci., 329, 552-567 (2016)
[10] Eagle, N.; Pentland, A., Reality mining: sensing complex social systems, Person. Ubiquitous Comput., 10, 4, 255-268 (2006)
[11] Gao, S.; Denoyer, L.; Gallinari, P., Probabilistic latent tensor factorization model for link pattern prediction in multi-relational networks, J. China Univ. Posts Telecommun., 19, 172-181 (2012)
[12] Gao, S.; Denoyer, L.; Gallinari, P., Temporal link prediction by integrating content and structure information, CIKM’11, , Glasgow, Scotland, UK, 1169-1174 (2011), October
[13] Ge, M. Q.; Li, A.; Wang, M. H., A bipartite network-based method for prediction of long non-coding rna-protein interactions, Genomics, Proteomics Bioinf., 14, 1, 62-71 (2016)
[14] Hanneke, S.; Fu, W. J.; Xing, E. P., Discrete temporal models of social networks, Electron. J. Stat., 4, 585-605 (2010) · Zbl 1329.91113
[15] He, Y. L.; Liu, J. N.K.; Hu, Y. X.; Wang, X. Z., OWA operator based link prediction ensemble for social network, Expert Syst. Appl., 42, 1, 21-50 (2015)
[16] Hu, F. Y.; Wong, H. S., Labelling of human motion based on CBGA and probabilistic model, Int. J. Smart Sensing Intel. Syst., 6, 2, 583-609 (2013)
[18] Jia, X.; Xin, F.; Chuan, W. R., Adaptive spray routing for opportunistic networks, Int. J. Smart Sensing Intell. Syst., 6, 1, 95-119 (2013)
[19] Kaya, B.; Poyraz, M., Supervised link prediction in symptom networks with evolving case, Measurement, 56, 231-238 (2014)
[20] Kaya, B.; Poyraz, M., Unsupervised link prediction in evolving abnormal medical parameter networks, Int. J. Mach. Learn. Cybern., 7, 1, 145-155 (2016)
[21] Kim, H.; Tang, J.; Anderson, R.; Mascolo, C., Centrality prediction in dynamic human contact networks, Comput. Netw., 56, 983-996 (2012)
[22] Klimek, P.; Jovanovic, A. S.; Egloff, R.; Schneider, R., Successful fish go with the flow: citation impact prediction based on centrality measures for term-document networks, Scientometrics, 107, 3, 1265-1282 (2016)
[23] Li, Y.; Long, P. M.; Srinivasan, A., Improved bounds on the sample complexity of learning, J. Comput. Syst. Sci., 62, 3, 516-527 (2001) · Zbl 0990.68081
[24] Li, Y. H.; Wen, A. M.; Lin, Q.; Li, R. X.; Lu, D., Name disambiguation in scientific cooperation network by exploiting user feedback, Artif. Intell. Rev., 41, 4, 563-578 (2014)
[25] Liu, J.; Denga, G., Link prediction in a user_object network based on time-weighted resource allocation, Physica A, 388, 3643-3650 (2009)
[26] Liu, W.; Lü, L., Link prediction based on local random walk, Europhys. Lett., 89, 5, 58007 (2010)
[27] Liu, Z. H.; Ma, J. F.; Zeng, Y., Secrecy transfer for sensor networks: from random graphs to secure random geometric graphs, Int. J. Smart Sensing Intell. Syst., 6, 1, 77-94 (2013)
[28] Lü, L.; Jin, C. H.; Zhou, T., Similarity index based on local paths for link prediction of complex networks, Phys. Rev. E, 80, Article 046122 pp. (2009)
[29] Lü, L. Y.; Zhou, T., Link prediction in complex networks: a survey, Physica A, 390, 1150-1170 (2011)
[30] Murata, T.; Moriyasu, S., Link prediction based on structural properties of online social networks, New Generat. Comput., 26, 3, 245-257 (2008)
[31] Nanongkai, D.; Sarma, A. D.; Pandurangan, G., A tight unconditional lower bound on distributed random walk computation, PODC, 257-266 (2011) · Zbl 1321.68486
[32] Nigam, A.; Chawla, N. V., Link prediction in a semi-bipartite network for recommendation, Lect. Notes Comput. Sci., 9622, 127-135 (2016)
[33] O’Madadhain, J.; Hutchins, J.; Smyth, P., Prediction and ranking algorithms for event-based network data, (Proceeding of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2005)), 23-30
[34] Opsahl, T.; Panzarasa, P., Clustering in weighted networks, Soc. Netw., 31, 2, 155-163 (2009)
[35] Pujari, M.; Kanawati, R., Supervised rank aggregation approach for link prediction in complex networks, WWW 2012 Companion, Lyon, France, 1189-1196 (2012), April 16-20
[37] Sarma, A. D.; Molla, A. R.; Pandurangan, G., Near-optimal random walk sampling in distributed networks, INFOCOM, 2906-2910 (2012)
[38] Sarma, A. D.; Molla, A. R.; Pandurangan, G., Distributed computation in dynamic networks via random walks, Theor. Comput. Sci., 58, 1, 45-66 (2015) · Zbl 1315.68017
[39] Sarma, A. D.; Nanongkai, D.; Pandurangan, G., Fast distributed random walks, PODC, 161-170 (2009) · Zbl 1291.05189
[40] Sarma, A. D.; Nanongkai, D.; Pandurangan, G.; Tetali, P., Efficient distributed random walks with applications, PODC, 201-210 (2010) · Zbl 1315.68268
[41] Sarma, A. D.; Nanongkai, D.; Pandurangan, G.; Tetali, P., Distributed random walks, J. ACM, 60, 1, 2 (2013) · Zbl 1281.68225
[42] Savić, M.; Ivanović, M.; Radovanović, M.; Ognjanović, Z.; Pejović, A.; Krüger, T. J., The structure and evolution of scientific collaboration in Serbian mathematical journals, Scientometrics, 101, 3, 1805-1830 (2014)
[43] Sherkat, E.; Rahgozar, M.; M. Asadpour, Structural link prediction based on ant colony approach in social networks, Physica A, 419, 1, 80-94 (2015)
[44] Sun, D.; Zhou, T.; Liu, J. G.; Liu, R. R.; Jia, C. X.; Wang, B. H., Information filtering based on transferring similarity, Phys. Rev. E, 80017101 (2009)
[45] Vu, D. Q.; Asuncion, A. U.; Hunter, D. R.; Smyth, P., Continuous-time regression models for longitudinal networks, (Advances in Neural Information Processing Systems 24: Proceedings of the 25th Annual Conference on Neural Information Processing Systems (2011)), 1-9
[46] Wang, P.; Xu, B. W.; Wu, Y. R.; Zhou, X. Y., Link prediction in social networks: the state-of-the-art, Sci. China Inf. Sci., 58, 1, 1-38 (2015)
[47] Wang, X. M.; Liu, Y.; Xiong, F., Improved personalized recommendation based on a similarity network, Physica A, 456, 15, 271-280 (2016)
[48] Yang, L. T.; Wang, S.; Jiang, H., Cyclic temporal network density and its impact on information diffusion for delay tolerant networks, Int. J. Smart Sensing Intell. Syst., 4, 1, 35-52 (2011)
[49] Zeng, Z. Z.; Chen, K. J.; Zhang, S. B.; Zhang, H. J., A link prediction approach using semi-supervised learning in dynamic networks, (2013 Sixth International Conference on Advanced Computational Intelligence (ICACI) (2013)), 276-280
[50] Zhou, T.; Lü, L.; Zhang, Y. C., Predicting missing links via local information, Eur. Phys J B, 71, 4, 623-630 (2009) · Zbl 1188.05143
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.