Predicting the Structure of Dynamic Networks

Forecasting the network structure

1. Predicting dynamic networks Sevvandi Kandanaarachchi, Ziqi Xu and Stefan Westerlund

2. Social media networks New connections Energy networks Dynamic networks?

3. Social media networks New connections Energy networks Dynamic networks?

4. Can we predict/forecast a dynamic network at a future time step?

6. Link prediction Given the network, does this link/edge exist? Does not forecast the network structure Train algorithm on some existing links and predict others Forecasting the entire network is different We don’t know the network at the next time point New nodes can come in New edges between existing nodes New edges between new nodes etc . . . Related but different topics

7. Two step approach: Forecast & Optimize

8. Use standard time series methods (ARIMA) Forecast the number of new nodes at For existing nodes forecast the degree Degree: the number of edges it connects to Eg. { 1, 3, 7, 8, 10, 15, 16, 16, . . . } What about new nodes? For each network at time look at the new nodes Find their degree What is the new nodes degree like? Treat that as the forecast degree for new nodes   Step 1: Forecasting

9. For all nodes old and new we have a degree forecast

10. Optimize: Flux Balance Analysis used in metabolic network reconstruction

11. We solve an optimization problem Each edge is a variable - this is what we’re trying to find Each edge has a weight If the edge is seen in the recent past is has a higher weight If not – lower weight Possible new edges from new nodes – another weight Have different weight schemes Linearly/harmonically decaying weights in time Maximize subject to constraints   Step 2: Adapted Flux Balance Analysis

12. Maximize Subject to degree constraints Where is the forecast degree of node I What it does Allocates these edges in a way that maximizes the objective function Because we’re using the node degrees at a future time step We forecast the network   Optimization problem

13. Forecast and optimize strategy!

14. Example Graph forecasts 1 timestep ahead 3 timesteps ahead 5 timesteps ahead

15. Comparison of forecast with actual and other details in paper https://arxiv.org/abs/2401.04280 R package netseer on CRAN Other details

16. Applications in your domain? Thoughts? Input from you …

17. Thank you!