  To ensure the correctness of network analysis methods, the network (as the
input) has to be a sufficiently accurate representation of the underlying data.
However, when representing sequential data from complex systems such as global
shipping traffic or web clickstream traffic as networks, conventional network
representations that implicitly assume the Markov property (first-order
dependency) can quickly become limiting. This assumption holds that when
movements are simulated on the network, the next movement depends only on the
current node, discounting the fact that the movement may depend on several
previous steps. However, we show that data derived from many complex systems
can show up to fifth-order dependencies. In these cases, the oversimplifying
assumption of the first-order network representation can lead to inaccurate
network analysis results. To address this problem, we propose the Higher-Order
Network (HON) representation that can discover and embed variable orders of
dependencies in a network representation. Through a comprehensive empirical
evaluation and analysis, we establish several desirable characteristics of HON,
including accuracy, scalability, and direct compatibility with the existing
suite of network analysis methods. We illustrate how HON can be applied to a
broad variety of tasks, such as random walking, clustering, and ranking, and we
demonstrate that by using it as input, HON yields more accurate results without
any modification to these tasks.
