Graph theoretic Research in Algorithms and the PHenomenology of Social networks (GRAPHS) | Apply Online

Frequently Asked Questions (FAQs) - DARPA GRAPHS (BAA 12-01)

What is the DARPA GRAPHS opportunity?

DARPA's Graph theoretic Research in Algorithms and the PHenomenology of Social networks (GRAPHS) is a research-focused funding opportunity under BAA 12-01. It is aimed at advancing the mathematics and algorithmic foundations needed to understand, analyze, and exploit very large graphs and networks, with an emphasis on practical applicability to Department of Defense (DoD) problem settings.

Which DARPA office is sponsoring GRAPHS?

The opportunity is issued by DARPA's Defense Sciences Office (DSO).

What is the main purpose or motivation of the program?

The central motivation is to develop mathematically rigorous and algorithmically innovative methods that work at the scale of real-world networks (including social networks and other complex systems). DARPA emphasizes results that translate into usable methods for real DoD problems rather than purely abstract theory.

What kinds of networks does the program focus on?

GRAPHS highlights social networks as a key motivating application, but it also explicitly invites approaches for other DoD-relevant networks where graph structure is central, such as communication networks, logistical and supply networks, command-and-control relationships, infrastructure interdependencies, and other complex relational datasets.

What are the main research thrust areas in GRAPHS?

The program is organized around three thrust areas: (1) deeper theoretical underpinnings for the mathematics and dynamics of large-scale networks, (2) creation and development of efficient algorithms (polynomial-time and sub-polynomial) for exact and approximate solutions to DoD problems of interest, and (3) graph and network techniques that generalize beyond social networks to other DoD-relevant networked systems.

What does the first thrust area (network theory and dynamics) cover?

The first thrust seeks deeper theoretical foundations for understanding large-scale network structure and dynamics. This includes how networks evolve over time, how information or influence propagates, and how structure and dynamics interact at scale. It also includes a key application focus on developing a rigorous framework for threat signature detection and identification in networked data.

What does DARPA mean by "threat signature detection and identification" in networked data?

Within GRAPHS, this refers to mathematically grounded methods to define, detect, and characterize patterns of interest in graphs and networks. Examples of the types of patterns described include those that could correspond to malicious activity, coordinated behavior, or other operationally relevant phenomena in relational/network data.

What does the second thrust area (efficient algorithms) emphasize?

The second thrust emphasizes the development of efficient algorithms for massive graphs, including polynomial-time and sub-polynomial approaches, for both exact and approximate solutions to DoD problems of interest. It highlights methods with provable performance guarantees and the development of approximation schemes when exact computation is infeasible.

Are approximate methods acceptable, or is the program only interested in exact solutions?

Approximate methods are explicitly included. The opportunity describes interest in both exact and approximate solutions, particularly where exact computation is infeasible at the scale of massive graphs.

What kind of algorithmic outcomes is DARPA looking for?

DARPA is looking for algorithmic innovations that address the computational realities of very large graphs, including reductions in runtime or sample complexity, provable guarantees, and approaches that make previously intractable network analysis tasks feasible under realistic constraints. The stated intent is to move beyond incremental improvements.

What does the third thrust area (beyond social networks) include?

The third thrust invites graph and network techniques that apply to a wide range of DoD-relevant networks, not only social networks. The key theme is leveraging graph-theoretic and network-science methods in ways that can generalize across domains while remaining grounded in tangible defense applications.

Is this opportunity more about theory or more about applied work?

It is research-focused and mathematically rigorous, but it explicitly prioritizes practical applicability to DoD problem settings. The description emphasizes usable methods for real defense-relevant networks rather than purely abstract theory.

When was the opportunity posted?

The opportunity was posted on October 5, 2011.

What is the closing date for submissions?

The original and current closing date listed is December 15, 2011.

What is the archive date?

The archive date listed is January 13, 2012.

What type of funding opportunity is this?

It is categorized as a discretionary funding opportunity in the science and technology / research and development space.

What is the CFDA number associated with this opportunity?

The CFDA listed is 12.910 (Research and Technology Development).

What award instruments might DARPA use for GRAPHS?

DARPA indicated multiple potential award instruments, including cooperative agreements, grants, and other procurement contracts.

Is cost sharing or matching required?

No. DARPA noted that there is no cost-sharing or matching requirement for this opportunity.

Who is eligible to apply?

Eligibility is described as unrestricted, meaning it is broadly open to various types of proposing organizations, subject to any additional clarifications in the full announcement text.

Where are the full details and proposal instructions?

The full details and specific proposal instructions are contained in DARPA BAA 12-01.

Who is the point of contact?

The Defense Sciences Office BAA Coordinator is listed as the point of contact for access issues.