By 
Army researchers developed a novel algorithm to protect networks by allowing for the detection of adversarial actions that can be missed by current analytical methods, ARL announced August 17. The main idea of this research is to build a higher-order network to 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 instance, 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.
“We developed a scalable and parameter-free algorithm for higher-order network representation, BuildHON+, building on our prior work,” said Dr. Lance Kaplan, researcher with the U.S. Army Combat Capabilities Development Command’s Army Research Laboratory. “We demonstrate the efficiency of BuildHON+ through comprehensive complexity and performance analysis on global ship movement data, which is known to exhibit dependencies beyond the fifth order, meaning, for example, we predict the next port based upon more than the past five ports that the shipment has passed through.”
This work is the result of a collaboration under the laboratory’s now concluded Network Science Collaborative Technology Alliance between Kaplan, Mandana Saebi, Jian Xu, and Nitesh Chawla from the University of Notre Dame, and Bruno Ribeiro from Purdue University.
According to Kaplan, 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, he said. This is especially relevant when the data is noisy and has sequential dependencies within indirect pathways.
By building up higher-order networks from the data streams at adjacent time intervals, he said, one can detect subtle changes in the data streams that traditional first-order networks would miss. This research has numerous applications, ranging from information flow to human interaction activity on a website to transportation to invasive species management to drug and human tracking, Kaplan said. For Soldiers, it could be applied to a supply/chain network used both by Soldiers and Civilians within an area of interest.
“The higher-order network analysis can find weak signals in a logistics network of adversarial actions that would be missed by first-order network representations,” Kaplan said. “This can include preparations by non-state actors to launch an attack in support of a peer adversary.”
Moving forward with this research, there are still a number of scientific questions that the team, and the scientific community at large, will continue to pursue.
“The concept of higher order networks opens up many different interesting avenues of investigation within network science to better predict the coevolution of networks and detect weak signals of adversarial behaviors,” Kaplan said.
Source: ARL
