Graph-theoretic Research in Algorithms and the PHenomenology of Social networks (GRAPHS)

DARPA's GRAPHS program takes the data of real-world social networks and attempts to pull meaningful algorithms and patterns that can be used to analyze how networks react to external stimuli (cyberattacks, power failure) or how existing network structures can be improved (traffic control, public health). GRAPHS was started in 2011, and so far mainly analyzes the graphs themselves. How can graphical data be presented, how can large graphs be made of multiple nodes be effectively utilized, and what algorithms can be developed to make data retrieval faster and more efficient. Eventually, GRAPHS hopes to be able to detect terrorist recruitment or cyberattacks using social network data, as well as optimal troop deployment, minimal-cost path finding, and complex operations scheduling using advanced graph algorithms.

https:// www.darpa.mil/program/graphs

Hierarchical Identify Verify Exploit (HIVE)

In parallel with the hardware development of a HIVE processor, DARPA is working with MIT Lincoln Laboratory and Amazon Web Services (AWS) to host the HIVE Graph Challenge with the goal of developing a trillion-edge dataset. This freely available dataset will spur innovative software and hardware solutions in the broader graph analysis community that will contribute to the HIVE program.

The overall objective is to accelerate innovation in graph analytics to open new pathways for meeting the challenge of understanding an ever-increasing torrent of data. The HIVE program features two primary challenges:

The first is a static graph problem focused on sub-graph Isomorphism. This task is to further the ability to search a large graph in order to identify a particular subsection of that graph.

The second is a dynamic graph problem focused on trying to find optimal clusters of data within the graph.

Both challenges will include a small graph problem in the billions of nodes and a large graph problem in the trillions of nodes.

https:// www.darpa.mil/program/hierarchical-identify-verify-exploit