Higher-order Network (HON)
Paper / Science AdvancesGeneral Info
Network-based representation has quickly emerged as the norm in representing rich interactions among the components of a complex system for analysis and modeling. For example, the global shipping network can be constructed by taking the pairwise shipping traffic between ports as the edge weights in the network. However, for a variety of complex systems like global shipping, representing them with the conventional first-order (Markov property) networks, which is the norm, captures only the first order relationship connections in the underlying data, missing the variable and higher order of dependencies that might be driving the system. It is thus critical for the network to truly represent the inherent phenomena in the complex system to avoid incorrect analysis results or conclusions.
Contributions
We propose the Higher-order Network (HON), which remedies the gap between complex interaction data and the network representation. It is a fundamental and transformative advance in network representation by offering a generalized method to automatically discover the right orders of dependencies from big data and ensure those dependencies can be embedded in networks. We demonstrate how HON is accurate in describing dynamics, scalable for big data, and directly compatible with the existing suite of network analysis and modeling methods. We illustrate the effectiveness of HON through interdisciplinary applications from species invasion modeling at the global scale to Web user browsing behavior analysis.
Fig.1 Necessity of representing dependencies in networks.
Fig.2 Comparison of random walking accuracies.
Fig.3 Clustering of ports on different network representations of the global shipping data.
Fig.4 Change of Web page rankings by using HON instead of first-order network.
Fig.5 Comparison of different network representations for the same clickstream data.