Link prediction in dynamic networks using random dot product graphs
The problem of predicting links in large networks is a crucial task in a variety of practical applications, including social sciences, biology and computer security. In this paper, statistical techniques for link prediction based on the popular random dot product graph model are carefully presented, analysed and extended to dynamic settings. Motivated by a practical application in cyber-security, this paper demonstrates that random dot product graphs not only represent a powerful tool for inferring differences between multiple networks, but are also efficient for prediction purposes and for understanding the temporal evolution of the network. The probabilities of links are obtained by fusing information at multiple levels of resolution: time series models are used to score connections at the edge level, and spectral methods provide estimates of latent positions for each node. In this way, traditional link prediction methods, usually based on decompositions of the entire network adjacency matrix, are extended using edge-specific information. The methods presented in this article are applied to a number of simulated and real-world computer network graphs, showing promising results.
READ FULL TEXT