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.

arXiv comment38 pages, 9 figures, 3 tables, 2 algorithms

References in corpus (18)

• Maps of random walks on complex networks reveal community structure
• The architecture of complex weighted networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Analysis of weighted networks
• The complex network of global cargo ship movements
• Random Walks on Multiplex Networks
• Analysis of the Airport Network of India as a complex weighted network
• Memory in network flows and its effects on spreading dynamics and community detection
• Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
• On Prediction Using Variable Order Markov Models
• Scaling laws for the movement of people between locations in a large city
• Multilinear PageRank
• Detecting Memory and Structure in Human Navigation Patterns Using Markov Chain Models of Varying Order
• Tensor Spectral Clustering for Partitioning Higher-order Network Structures
• Predictability of conversation partners
• Higher-Order Aggregate Networks in the Analysis of Temporal Networks: Path structures and centralities
• Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution
• Using Triangles to Improve Community Detection in Directed Networks

Cited by in corpus (37)

• Random walks and diffusion on networks
• Simplicial Closure and higher-order link prediction
• Ranking in evolving complex networks
• Modeling sequences and temporal networks with dynamic community structures
• Current and future directions in network biology
• Mapping higher-order network flows in memory and multilayer networks with Infomap
• When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks
• Fast influencers in complex networks
• Mapping flows on hypergraphs
• Efficient modeling of higher-order dependencies in networks: from algorithm to application for anomaly detection
• The Mobility Network of Scientists: Analyzing Temporal Correlations in Scientific Careers
• The maximum capability of a topological feature in link prediction
• Circulation of a digital community currency
• Randomizing growing networks with a time-respecting null model
• HONEM: Learning Embedding for Higher Order Networks
• The long-term impact of ranking algorithms in growing networks
• HYPA: Efficient Detection of Path Anomalies in Time Series Data on Networks
• Higher-Order Networks Representation and Learning: A Survey
• Maps of sparse Markov chains efficiently reveal community structure in network flows with memory
• Understanding Complex Systems: From Networks to Optimal Higher-Order Models
• Higher-order models capture changes in controllability of temporal networks
• Convexity in complex networks
• Predicting Sequences of Traversed Nodes in Graphs using Network Models with Multiple Higher Orders
• Modeling multi-scale data via a network of networks
• Locating Community Smells in Software Development Processes Using Higher-Order Network Centralities
• Finding the right scale of a network: Efficient identification of causal emergence through spectral clustering
• Learning higher-order sequential structure with cloned HMMs
• Making Communities Show Respect for Order
• Optimal timescale for community detection in growing networks
• The Atlas for the Aspiring Network Scientist
• Flow-based Community Detection in Hypergraphs
• Learning the Markov order of paths in a network
• Economic and environmental impacts of ballast water management on Small Island Developing States and Least Developed Countries
• Computational Human Dynamics
• Controlling network dynamics
• Quantifying the Impact of Scholarly Papers Based on Higher-Order Weighted Citations
• Adaptive Shrinkage Estimation for Streaming Graphs