Program Summary
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.