Link prediction in dynamic networks using random dot product graphs
File(s)
Author(s)
Sanna Passino, Francesco
Bertiger, Anna S
Neil, Joshua C
Heard, Nicholas A
Type
Journal Article
Abstract
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.
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.
Date Issued
2021-09-01
Date Acceptance
2021-07-21
Citation
Data Mining and Knowledge Discovery, 2021, 35 (5), pp.2168-2199
ISSN
1384-5810
Publisher
Springer Verlag
Start Page
2168
End Page
2199
Journal / Book Title
Data Mining and Knowledge Discovery
Volume
35
Issue
5
Copyright Statement
© The Author(s) 2021. This article is licensed under a Creative Commons Attribution 4.0 International License, which
permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give
appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence,
and indicate if changes were made. The images or other third party material in this article are included
in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If
material is not included in the article’s Creative Commons licence and your intended use is not permitted
by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the
copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give
appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence,
and indicate if changes were made. The images or other third party material in this article are included
in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If
material is not included in the article’s Creative Commons licence and your intended use is not permitted
by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the
copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
License URL
Identifier
https://www.springerprofessional.de/link-prediction-in-dynamic-networks-using-random-dot-product-gra/19547128
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science, Information Systems
Computer Science
Adjacency spectral embedding
Dynamic networks
Link prediction
Random dot product graph
STOCHASTIC BLOCKMODELS
TIME-SERIES
MODELS
stat.AP
stat.AP
cs.SI
Artificial Intelligence & Image Processing
0801 Artificial Intelligence and Image Processing
0804 Data Format
0806 Information Systems
Publication Status
Published
Date Publish Online
2021-08-05