Researchers developed a novel algorithm to protect networks by allowing for the detection of adversarial actions that can be missed by current analytical methods. A higher-order network could look for subtle changes in a stream of data that could point to suspicious activity.

Most analytics build up first-order networks, where edges represent a movement between two nodes; for example, airports connected by direct flights. The history of multi-hop travel by people is lost in such networks. Higher-order networks include additional nodes to also represent the dominant (multi-hop) flows in the data. The research focuses on harvesting social signals to detect emerging phenomena by looking beyond first-order Markov patterns over network data.

The work developed a representation that embeds higher-order dependencies into the network such that it reflects real-world phenomena and scales for big data and existing network analysis tools. It uses the representation to perform network analytics to identify influential nodes, detect anomalies, and predict co-evolution of multi-genre networks.

The scalable and parameter-free algorithm for higher-order network representation, BuildHON+, builds on the performance of BuildHON+ in the task of network-based anomaly detection on both real-world and synthetic taxi trajectory datasets. To do this, the researchers created a synthetic dataset of origins and destinations for taxi cabs. In the real-world data set, there was only one abnormal day that could be detected. The synthetic data set enabled a more systematic comparison of the BuildHON+ against first-order network approaches.

Using a large-scale synthetic taxi movement data with 11 billion taxi movements, the team showed how multiple existing anomaly detection methods that depend on first-order network collectively fail to capture anomalous navigation behaviors beyond first order and how BuildHON+ can solve the problem. Most analysis of streams over network data assume first-order Markov evolution, i.e., the probability that a ship or taxi visits a port/location depends solely on its current location in the network. The ability to represent higher-order dependencies enables one to distinguish more subtle traffic patterns.

The higher-order network representation results in a more accurate representation of the underlying trends and patterns in the behavior of a complex system and is the correct way of constructing the network to not miss any important dependencies or signals. This is especially relevant when the data is noisy and has sequential dependencies within indirect pathways.

This research has applications ranging from information flow and human interaction activity on a website, to transportation and invasive species management, to drug and human tracking. In the military, it could be applied to a supply/chain network used both by soldiers and civilians within an area of interest.

For more information, contact the U.S. Army CCDC Army Research Laboratory Public Affairs at 703-693-6477.