Representing higher-order dependencies in networks

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.

Cite as: Jian Xu, Thanuka L. Wickramarathne, and Nitesh V. Chawla. "Representing higher-order dependencies in networks." Science Advances 2, no. 5 (2016): e1600028.

HoNVis: Visualizing and Exploring Higher-Order Networks

Unlike the conventional first-order network (FoN), the higher-order network (HoN) provides a more accurate description of transitions by creating additional nodes to encode higher-order dependencies. However, there exists no visualization and exploration tool for the HoN. For applications such as the development of strategies to control species invasion through global shipping which is known to exhibit higher-order dependencies, the existing FoN visualization tools are limited. In this paper, we present HoNVis, a novel visual analytics framework for exploring higher-order dependencies of the global ocean shipping network. Our framework leverages coordinated multiple views to reveal the network structure at three levels of detail (i.e., the global, local, and individual port levels). Users can quickly identify ports of interest at the global level and specify a port to investigate its higher-order nodes at the individual port level. Investigating a larger-scale impact is enabled through the exploration of HoN at the local level. Using the global ocean shipping network data, we demonstrate the effectiveness of our approach with a real-world use case conducted by domain experts specializing in species invasion. Finally, we discuss the generalizability of this framework to other real-world applications such as information diffusion in social networks and epidemic spreading through air transportation.

Cite as: Jun Tao, Jian Xu, Chaoli Wang, and Nitesh V. Chawla. "HoNVis: Visualizing and Exploring Higher-Order Networks". IEEE PacificVis, 2017

Detecting Anomalies in Sequential Data with Higher-order Networks

A major branch of anomaly detection methods relies on dynamic networks: raw sequence data is first converted to a series of networks, then critical change points are identified in the evolving network structure. However, existing approaches use first-order networks (FONs) to represent the underlying raw data, which may lose important higher-order sequence patterns, making higher-order anomalies undetectable in subsequent analysis. We present a novel higher-order anomaly detection method that is both parameter-free and scalable, building on an improved higher-order network (HON) construction algorithm. We show the proposed higher-order anomaly detection algorithm is effective in discovering variable orders of anomalies. Our data includes a synthetic 11 billion web clickstreams and a real-world taxi trajectory data.

Cite as: Jian Xu, Mandana Saebi, Bruno Ribeiro, Lance M Kaplan, and Nitesh V Chawla. "Detecting Anomalies in Sequential Data with Higher-order Networks". arXiv preprint arXiv:1712.09658

In the news

Complex inter-dependent data: Looking beyond conventional networks can lead to better predictions, by ScienceDaily

New research suggests that current algorithms to represent networks have not truly considered the complex inter-dependencies in data, which can lead to erroneous analysis or predictions. Scientists have now developed a new algorithm that offers the promise of more precise network representation and accurate analysis.... Click to view more

We're Modeling Networks All Wrong, by Motherboard, Vice

Current network analysis algorithms are missing or skipping over some crucial details, argues a team of computer science researchers from the University of Notre Dame in the current issue of Science Advances. The result, they say, is a widespread pattern of oversimplification profound enough to lead to erroneous results and interpretations. Naturally, the scientists have developed a new and improved alternative capable of spotting missed interdependencies... Click to view more