Predicting variable-length paths in networked systems using multi-order generative models
Abstract 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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2023-09-01
|
| Series: | Applied Network Science |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s41109-023-00596-x |
| _version_ | 1797577430466035712 |
|---|---|
| author | Christoph Gote Giona Casiraghi Frank Schweitzer Ingo Scholtes |
| author_facet | Christoph Gote Giona Casiraghi Frank Schweitzer Ingo Scholtes |
| author_sort | Christoph Gote |
| collection | DOAJ |
| description | Abstract 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. |
| first_indexed | 2024-03-10T22:09:10Z |
| format | Article |
| id | doaj.art-3953d41fb2e247478feaf133a2d2811f |
| institution | Directory Open Access Journal |
| issn | 2364-8228 |
| language | English |
| last_indexed | 2024-03-10T22:09:10Z |
| publishDate | 2023-09-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Applied Network Science |
| spelling | doaj.art-3953d41fb2e247478feaf133a2d2811f2023-11-19T12:41:59ZengSpringerOpenApplied Network Science2364-82282023-09-018112010.1007/s41109-023-00596-xPredicting variable-length paths in networked systems using multi-order generative modelsChristoph Gote0Giona Casiraghi1Frank Schweitzer2Ingo Scholtes3Chair of Systems Design, ETH ZurichChair of Systems Design, ETH ZurichChair of Systems Design, ETH ZurichChair for Machine Learning for Complex Networks, Julius-Maximilians-Universität WürzburgAbstract 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.https://doi.org/10.1007/s41109-023-00596-xGraph miningSequential pattern miningSequence predictionSupervised learning |
| spellingShingle | Christoph Gote Giona Casiraghi Frank Schweitzer Ingo Scholtes Predicting variable-length paths in networked systems using multi-order generative models Applied Network Science Graph mining Sequential pattern mining Sequence prediction Supervised learning |
| title | Predicting variable-length paths in networked systems using multi-order generative models |
| title_full | Predicting variable-length paths in networked systems using multi-order generative models |
| title_fullStr | Predicting variable-length paths in networked systems using multi-order generative models |
| title_full_unstemmed | Predicting variable-length paths in networked systems using multi-order generative models |
| title_short | Predicting variable-length paths in networked systems using multi-order generative models |
| title_sort | predicting variable length paths in networked systems using multi order generative models |
| topic | Graph mining Sequential pattern mining Sequence prediction Supervised learning |
| url | https://doi.org/10.1007/s41109-023-00596-x |
| work_keys_str_mv | AT christophgote predictingvariablelengthpathsinnetworkedsystemsusingmultiordergenerativemodels AT gionacasiraghi predictingvariablelengthpathsinnetworkedsystemsusingmultiordergenerativemodels AT frankschweitzer predictingvariablelengthpathsinnetworkedsystemsusingmultiordergenerativemodels AT ingoscholtes predictingvariablelengthpathsinnetworkedsystemsusingmultiordergenerativemodels |