Predicting variable-length paths in networked systems using multi-order generative models

Applied Network Science

Research

Ingo Scholtes¹  Frank Schweitzer²  Giona Casiraghi²  Christoph Gote³ 

[1] Chair for Machine Learning for Complex Networks, Julius-Maximilians-Universität Würzburg, Würzburg, Germany;Data Analytics Group, University of Zurich, Zurich, Switzerland;Chair of Systems Design, ETH Zurich, Zurich, Switzerland;Chair of Systems Design, ETH Zurich, Zurich, Switzerland;Chair for Machine Learning for Complex Networks, Julius-Maximilians-Universität Würzburg, Würzburg, Germany;Data Analytics Group, University of Zurich, Zurich, Switzerland;

关键词: Graph mining;    Sequential pattern mining;    Sequence prediction;    Supervised learning;   

DOI  :  10.1007/s41109-023-00596-x

 received in 2023-06-08, accepted in 2023-09-13,  发布年份 2023

来源: Springer

【 摘 要 】

Apart from nodes and links, for many networked systems, we have access to data on paths, i.e., collections of temporally ordered variable-length node sequences that are constrained by the system’s topology. Understanding the patterns in such data is key to advancing our understanding of the structure and dynamics of complex systems. Moreover, the ability to accurately model and predict paths is important for engineered systems, e.g., to optimise supply chains or provide smart mobility services. Here, we introduce MOGen, a generative modelling framework that enables both next-element and out-of-sample prediction in paths with high accuracy and consistency. It features a model selection approach that automatically determines the optimal model directly from data, effectively making MOGen parameter-free. Using empirical data, we show that our method outperforms state-of-the-art sequence modelling techniques. We further introduce a mathematical formalism that links higher-order models of paths to transition matrices of random walks in multi-layer networks.

【 授权许可】

CC BY   
© Springer Nature Switzerland AG 2023

【 图 表 】

42004_2023_995_Article_IEq42.gif

Fig. 4

Fig. 3

Fig. 3

Fig. 1

12888_2023_5172_Article_IEq23.gif

13690_2023_1170_Article_IEq111.gif

12888_2023_5172_Article_IEq22.gif

Fig. 2

Fig. 6

Fig. 12

Fig. 2

Fig. 3

Fig. 2

Fig. 6

Fig. 2

Fig. 6

Fig. 3

Fig. 2

Fig. 2

12888_2023_5172_Article_IEq20.gif

Fig. 1

Fig. 6

Fig. 1

Fig. 2

Fig. 6

13690_2023_1170_Article_IEq13.gif

42004_2023_995_Article_IEq1.gif

Fig. 2

Fig. 1

Fig. 1

Fig. 1

Fig. 4

Fig. 2

13690_2023_1170_Article_IEq225.gif

Fig. 4

Fig. 9

Fig. 6

Fig. 3

Fig. 5

Fig. 2

Fig. 4

12888_2023_5172_Article_IEq6.gif

13690_2023_1170_Article_IEq223.gif

12888_2023_5172_Article_IEq5.gif

12888_2023_5172_Article_IEq4.gif

13690_2023_1170_Article_IEq220.gif

13690_2023_1170_Article_IEq219.gif

Fig. 2

Fig. 1

Fig. 2

Fig. 2

Fig. 5

Fig. 2

Fig. 2

Fig. 1

Fig. 5

Fig. 1

Fig. 2

Fig. 3

12938_2023_1153_Article_IEq25.gif

13690_2023_1170_Article_IEq208.gif

13690_2023_1170_Article_IEq207.gif

13690_2023_1170_Article_IEq77.gif

Fig. 7

13690_2023_1170_Article_IEq76.gif

13690_2023_1170_Article_IEq200.gif

12888_2023_5142_Article_IEq12.gif

13690_2023_1170_Article_IEq183.gif

Fig.3

13690_2023_1170_Article_IEq182.gif

Fig. 6

12951_2023_2095_Article_IEq11.gif

Fig. 1

13690_2023_1170_Article_IEq66.gif

Fig. 1

Fig. 1

Fig. 1

Fig. 6

Fig. 2

Fig. 1

40798_2023_628_Figh_HTML.png

40798_2023_628_Figg_HTML.png

Fig. 4

Fig. 2

Fig. 2

Fig. 3

13690_2023_1170_Article_IEq165.gif

13690_2023_1170_Article_IEq164.gif

Fig. 10

13690_2023_1170_Article_IEq53.gif

13690_2023_1170_Article_IEq160.gif

Fig. 6

Fig. 4

Fig. 5

Fig. 5

Fig. 3

Fig. 3

Fig. 1

Fig. 4

Fig. 3

Fig. 4

Fig. 1

Fig. 4

Fig. 3

Fig. 2

Fig. 2

Fig. 1

Fig. 2

Fig. 3

Fig. 2

Fig. 4

Fig. 1

Fig. 1

Fig. 1

Fig. 1

12888_2023_5142_Article_IEq11.gif

Fig. 5

Fig. 2

13690_2023_1170_Article_IEq182.gif

Fig. 6

13690_2023_1170_Article_IEq72.gif

Fig. 4

Fig. 3

Fig. 2

Fig. 1

13690_2023_1170_Article_IEq172.gif

Fig. 1

Fig. 5

Fig. 2

13690_2023_1170_Article_IEq169.gif

Fig. 1

12888_2023_5159_Article_IEq1.gif

40249_2023_1135_Article_IEq8.gif

40249_2023_1135_Article_IEq7.gif

40249_2023_1135_Article_IEq6.gif

Fig. 4

13690_2023_1170_Article_IEq167.gif

12951_2023_2095_Article_IEq4.gif

Fig. 6

12951_2023_2095_Article_IEq3.gif

Fig. 8

40798_2023_628_Figd_HTML.png

Fig. 7

Fig. 7

12862_2023_2158_Article_IEq45.gif

42004_2023_990_Article_IEq63.gif

Fig.1

Fig. 12

Fig. 2

Fig. 4

Fig. 2

Fig. 1