Representing significant dependencies with variable orders in networks

Higher-order networks (HONs) have demonstrated remarkable effectiveness in capturing higher-order dependencies in complex systems, revealing crucial non-Markovian group interactions involving three or more components. However, existing HON models face two primary limitations: (1) inadequate handling of the coexistence of dependencies with variable orders, and (2) low model interpretability. To address these challenges, we propose Significant Dependencies with Variable Orders Mining (SDVOM), a method utilizing hypothesis testing and Markov Chain Monte Carlo (MCMC) techniques to automatically identify statistically significant dependencies with variable orders from data. Furthermore, we introduce the SDVO-HON model, a novel HON framework that embeds these significant dependencies in a higher-order pattern tree structure, enhancing model interpretability through the explicit representation of dependencies with variable orders. Evaluations on synthetic clickstream datasets embedding user preference patterns with variable orders demonstrate that SDVOM uniquely maintains a low Type I error rate while generating zero Type II errors across all experimental settings, outperforming existing state-of-the-art methods. We further applied SDVOM and the SDVO-HON model to real-world transportation and communication networks, demonstrating that SDVOM identifies significant dependencies with 99% confidence and eliminates over 97% of non-significant dependencies. The SDVO-HON model significantly improves network analysis tasks, enhancing the identification of high-impact employees in organizational networks and hub cities in high-speed rail systems. Overall, the proposed method provides a powerful tool for analyzing complex real-world data, substantially advancing the interpretability and representative power of HON models.