The science of network analysis is in its infancy. Currently, the structure of real-world networks is described only in terms of coarse and basic details such as diameter, degree distribution, etc. In addition, as networks become large, many problems are intractable as the classical algorithms for these problems run in exponential time with respect to the size of the graph. A large number of important problems (e.g., structural and functional brain dynamics or gene-protein and disease networks) can be formulated as graph problems. A comprehensive mathematical understanding of large networks is needed in order to effectively apply and scale graph-based network analysis techniques for use in DoD-relevant scenarios.
DARPA’s GRAPHS program seeks quantitative understanding to determine network function from its structure, while incorporating considerations such as the evolution of graph structure through time and other network dynamics. A particular emphasis is on discovering high-fidelity approximation algorithms that scale to DoD-size (billions of nodes) networks, particularly if approximation techniques and algorithms can be found with rigorous performance bounds.
The potential GRAPHS gains in algorithm processing time would be applicable to many classes of DoD problems such as neuroscience, operations research (e.g., scheduling, vehicle routing), electrical engineering (e.g., communications networks, electric power grids), mobile communications, cyber-security, air traffic control, battle-space management, sensor networks, supply chain management, genomics, public health and biochemistry.
You are now leaving the DARPA.mil website that is under the control and
management of DARPA. The appearance of hyperlinks does not constitute
endorsement by DARPA of non-U.S. Government sites or the information,
products, or services contained therein. Although DARPA may or may not
use these sites as additional distribution channels for Department of
Defense information, it does not exercise editorial control over all of
the information that you may find at these locations. Such links are
provided consistent with the stated purpose of this website.
After reading this message, click to continue