title: Representing higher-order dependencies in networks.
abstract: 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.
authors.affiliation: Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA.; Interdisciplinary Center for Network Science and Applications, University of Notre Dame, Notre Dame, IN 46556, USA.Department of Electrical Engineering, University of Notre Dame, Notre Dame, IN 46556, USA.Environmental Change Initiative, University of Notre Dame, Notre Dame, IN 46556, USA.
authors.forename: Jian
authors.initials: J
authors.lastname: Xu
authors.affiliation: Interdisciplinary Center for Network Science and Applications, University of Notre Dame, Notre Dame, IN 46556, USA.Department of Electrical Engineering, University of Notre Dame, Notre Dame, IN 46556, USA.Environmental Change Initiative, University of Notre Dame, Notre Dame, IN 46556, USA.; Interdisciplinary Center for Network Science and Applications, University of Notre Dame, Notre Dame, IN 46556, USA.Department of Electrical Engineering, University of Notre Dame, Notre Dame, IN 46556, USA.Environmental Change Initiative, University of Notre Dame, Notre Dame, IN 46556, USA.; Interdisciplinary Center for Network Science and Applications, University of Notre Dame, Notre Dame, IN 46556, USA.Department of Electrical Engineering, University of Notre Dame, Notre Dame, IN 46556, USA.Environmental Change Initiative, University of Notre Dame, Notre Dame, IN 46556, USA.
authors.forename: Thanuka L
authors.initials: TL
authors.lastname: Wickramarathne
authors.affiliation: Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA.; Interdisciplinary Center for Network Science and Applications, University of Notre Dame, Notre Dame, IN 46556, USA.Department of Electrical Engineering, University of Notre Dame, Notre Dame, IN 46556, USA.Environmental Change Initiative, University of Notre Dame, Notre Dame, IN 46556, USA.; Interdisciplinary Center for Network Science and Applications, University of Notre Dame, Notre Dame, IN 46556, USA.Department of Electrical Engineering, University of Notre Dame, Notre Dame, IN 46556, USA.Environmental Change Initiative, University of Notre Dame, Notre Dame, IN 46556, USA.
authors.forename: Nitesh V
authors.initials: NV
authors.lastname: Chawla
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D057225:Data Mining; D015233:Models, Statistical; D016571:Neural Networks, Computer; D015203:Reproducibility of Results
keywords: Markovian; Network science; clustering; community detection; data mining; network structure; random walk; ranking