The Time-Series Link Prediction Problem with Applications in Communication Surveillance
- 1 May 2009
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 21 (2), 286-303
- https://doi.org/10.1287/ijoc.1080.0292
Abstract
The ability to predict linkages among data objects is central to many data mining tasks, such as product recommendation and social network analysis. Substantial literature has been devoted to the link prediction problem either as an implicitly embedded problem in specific applications or as a generic data mining task. This literature has mostly adopted a static graph representation where a snapshot of the network is analyzed to predict hidden or future links. However, this representation is only appropriate to investigate whether a certain link will ever occur and does not apply to many applications for which the prediction of the repeated link occurrences are of primary interest (e.g., communication network surveillance). In this paper, we introduce the time-series link prediction problem, taking into consideration temporal evolutions of link occurrences to predict link occurrence probabilities at a particular time. Using Enron e-mail data and high-energy particle physics literature coauthorship data, we have demonstrated that time-series models of single-link occurrences achieve comparable link prediction performance with commonly used static graph link prediction algorithms. Furthermore, a combination of static graph link prediction algorithms and time-series models produced significantly better predictions over static graph link prediction methods, demonstrating the great potential of integrated methods that exploit both interlink structural dependencies and intralink temporal dependencies.This publication has 30 references indexed in Scilit:
- Graph evolutionACM Transactions on Knowledge Discovery From Data, 2007
- Inhomogeneous evolution of subgraphs and cycles in complex networksPhysical Review E, 2005
- Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filteringACM Transactions on Information Systems, 2004
- Latent semantic models for collaborative filteringACM Transactions on Information Systems, 2004
- Link miningACM SIGKDD Explorations Newsletter, 2003
- The use of the area under the ROC curve in the evaluation of machine learning algorithmsPattern Recognition, 1997
- Recommender systemsCommunications of the ACM, 1997
- Performance engineering of the World Wide Web: Application to dimensioning and cache designComputer Networks and ISDN Systems, 1996
- An Application of the Seasonal Fractionally Differenced Model to the Monetary AggregatesJournal of the American Statistical Association, 1990
- A new look at the statistical model identificationIEEE Transactions on Automatic Control, 1974