On fast and scalable recurring link's prediction in evolving multi-graph streams. (20th July 2020)

• Record Type: Journal Article
• Authors: Tabassum, Shazia; Veloso, Bruno; Gama, João
• Editors: Cherifi, Hocine; Rocha, Luis M.; Wasserman, Stanley
• Is Part Of: Network science. Volume 8(2020)Supplement 1
• Page Start: S65
• Page End: S81
• Publication Date: 2020-07-20
• Subjects: Hocine Cheri; link prediction, -- evolving network, -- recurring links, -- graph streams, -- temporal networks; Social networks -- Research -- Periodicals; System analysis -- Periodicals; System theory -- Periodicals; Computer science -- Periodicals; 003.72
• DOI: 10.1017/nws.2019.64
• Languages: English
• ISSNs: 2050-1242

Abstract

Abstract: The link prediction task has found numerous applications in real-world scenarios. However, in most of the cases like interactions, purchases, mobility, etc., links can re-occur again and again across time. As a result, the data being generated is excessively large to handle, associated with the complexity and sparsity of networks. Therefore, we propose a very fast, memory-less, and dynamic sampling-based method for predicting recurring links for a successive future point in time. This method works by biasing the links exponentially based on their time of occurrence, frequency, and stability. To evaluate the efficiency of our method, we carried out rigorous experiments with massive real-world graph streams. Our empirical results show that the proposed method outperforms the state-of-the-art method for recurring links prediction. Additionally, we also empirically analyzed the evolution of links with the perspective of multi-graph topology and their recurrence probability over time.