Representing higher‑order dependencies in networks

Jian Xu, Thanuka L. Wickramarathne, Nitesh V. Chawla

Science Advances 2(5): e1600028, May 2016 published, open access

A network of ports remembers only where each ship is now. Ships passing through Singapore from Tokyo and from Shanghai look identical, even though they tend to sail on to different places. HON learns from the data how many previous steps matter, up to fifth order in our data, and splits nodes like Singapore accordingly. The result is still an ordinary network, so existing clustering, ranking and random-walk methods run on it unchanged and give more accurate answers.

Four panels: A, a table of vessel voyages; B, a first-order network where Singapore is one node; C, a higher-order network where Singapore splits into Singapore given Tokyo and Singapore given Shanghai; D, variable orders of dependency, with nodes conditioned on one or several previous ports. — Fig. 1. Necessity of representing 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.

Why it matters

Network-based representation has quickly emerged as the norm for representing rich interactions among the components of a complex system. The global shipping network, for example, can be built by taking the pairwise traffic between ports as edge weights. For many complex systems, such a conventional first-order network captures only the pairwise connections in the data and misses the variable, higher orders of dependency that may drive the system. The network has to represent the phenomena in the data faithfully, or the analysis built on it reaches wrong conclusions.

Contributions

HON closes the gap between complex interaction data and the network representation. It is a general method that discovers the right orders of dependency from big data automatically and embeds them in the network. We show that HON describes dynamics accurately, scales to big data, and is directly compatible with the existing suite of network analysis and modeling methods, with applications ranging from species invasion modeling at global scale to the analysis of web browsing behavior.

Figures

Comparison of random walk accuracy on first-order and higher-order networks. — Fig. 2. Comparison of random walking accuracies.

Clusters of ports found on different network representations of the global shipping data. — Fig. 3. Clustering of ports on different network representations of the global shipping data.

Change in web page rankings when using HON instead of the first-order network. — Fig. 4. Change of Web page rankings by using HON instead of the first-order network.

Different network representations of the same clickstream data. — Fig. 5. Comparison of different network representations for the same clickstream data.

Follow-up work

Cite

@article{xu2016representing,
  title   = {Representing higher-order dependencies in networks},
  author  = {Xu, Jian and Wickramarathne, Thanuka L. and Chawla, Nitesh V.},
  journal = {Science Advances},
  volume  = {2},
  number  = {5},
  pages   = {e1600028},
  year    = {2016},
  doi     = {10.1126/sciadv.1600028}
}