Predicting Graph Structure via Adapted Flux Balance Analysis
This addresses the problem of graph structure prediction for applications like anomaly detection in dynamic networks, but it appears incremental as it combines existing time series methods with an adapted FBA approach.
The paper tackled the problem of predicting future graph structures in dynamic networks where vertices can change, by adapting flux balance analysis (FBA) from biochemistry to incorporate constraints for growing graphs. The result showed efficacy in empirical evaluations on synthetic and real datasets, though no concrete numbers were provided.
Many dynamic processes such as telecommunication and transport networks can be described through discrete time series of graphs. Modelling the dynamics of such time series enables prediction of graph structure at future time steps, which can be used in applications such as detection of anomalies. Existing approaches for graph prediction have limitations such as assuming that the vertices do not to change between consecutive graphs. To address this, we propose to exploit time series prediction methods in combination with an adapted form of flux balance analysis (FBA), a linear programming method originating from biochemistry. FBA is adapted to incorporate various constraints applicable to the scenario of growing graphs. Empirical evaluations on synthetic datasets (constructed via Preferential Attachment model) and real datasets (UCI Message, HePH, Facebook, Bitcoin) demonstrate the efficacy of the proposed approach.