Measuring the significance of higher-order dependency in networks

Abstract

Higher-order networks (HONs), which go beyond the limitations of pairwise relation modeling by graphs, capture higher-order dependencies involving three or more components for various systems. As the number of potential higher-order dependencies increases exponentially with both network size and the order of dependency, it is of particular importance for HON models to balance their representation power against model complexity. In this study, we propose a method, significant k -order dependencies mining (S k DM), based on hypothesis testing and the Markov chain Monte Carlo (MCMC), to identify significant higher-order dependencies in real systems. Through synthetic clickstreams with elaborately designed higher-order dependencies, S k DM shows a powerful ability to correctly identify all significant dependencies at preset significance levels of $\alpha = \textrm{{0}}\textrm{{.01, 0}}\textrm{{.05, 0}}\textrm{{.10}}$ , performing as the only method, in comparison to the state of the arts, that can robustly maintain the Type I error rate, and without generating any Type II error across all the experimental settings. We further apply the S k DM method to various empirical networks, including journal citations, air traffic, and email communications. Empirical results show that among those tested networks, only 6.03%, 1.47%, and 1.28% of all potential dependencies are of statistical significance ( $\alpha = \textrm{{0}}\textrm{{.01}}$ ). The proposed S k DM method, therefore, provides an efficient tool for higher-order network analysis tasks at reduced computational complexity.

Keywords

• higher-order dependencies
• higher-order networks
• higher-order Markov models
• hypothesis testing
• significance