By Benjamin A. Miller, Rajmonda S. Caceres
In the last several years, network science has grown significantly as a field at the intersection of mathematics, computer science, social science, and engineering. Topics of interest include modeling and analysis of network phenomena, large-scale computation and data management, models for information and epidemic spreading through networks, and inference of information about entities based on observable connections. While basic research focuses on developing understanding in each of these areas, the ultimate goal in a practical setting is to use this understanding to achieve some application-specific objective.
In diverse mission areas, such as cyber security, counterterrorism/counterinsurgency, air traffic control, and bioengineering, the data of interest are inherently interconnected. Using a network or graph representation for the data allows for an additional level of insight not available when considering the data independently.
In 2010, as part of a research effort funded by the Office of Naval Research, staff at Massachusetts Institute of Technology’s Lincoln Laboratory in Lexington, Massachusetts, a Federally Funded Research and Development Center (FFRDC) for the United States Department of Defense, set out to build a community of interest through a symposium specifically focused on exploitation of graph data. The goal was to bring together academic researchers, industry practitioners, and end users to discuss problems of interest to the U.S. Government, and match these with the state-of-the-art models and techniques developed in the network science research community. Since its inception, the Graph Exploitation Symposium (GraphEx) has been held annually as a meeting to facilitate this interaction.
The following themes outline the current research frontier within the network science field, much of which was in evidence at the sixth annual GraphEx Symposium, held last July in Dedham, Massachusetts.
Controllability of large-scale, complex networks
Many human-engineered systems—including computational infrastructures, transportation systems, and electrical power grids—behave like large-scale, complex networks with different layers and components interacting in non-trivial ways. The susceptibility of such systems to local shocks is amplified by network cascading effects. Researchers currently lack the ability to quantify vulnerability and resilience of large-scale, complex networks at the system level. Symposium speakers at GraphEx 2015 put forward several suggestions to address this important challenge:
- Combine network science approaches with existing rich methodologies from the fields of control theory and decision theory to model dynamically changing demands on the engineered complex system.
- Rigorously measure, model, and assess the system architecture at different levels and under different constraints and disruptions.
- Design complex systems that are dynamic and stable by adaptively allocating resources/services through closed-loop feedback channels (e.g. software-defined wireless networks and intelligent transportation systems).
- Design complex network control mechanisms that can robustly handle stochastic cascades on the network while also localizing control effects.
User-centric algorithms
A number of talks addressed the concept of combining user-centric, private, rich data with global, incomplete, publically-available data, in ways ranging from estimating systemic risk in transportation networks to designing recommender systems on social networks. Mathematical models and algorithms that can handle a seamless and efficient integration of the two data regimes have implications beyond accuracy improvements on inference tasks. Such models have the potential to become enabling technologies as society enters the new era of data democratization and user self-awareness and empowerment.
Noise and interference in networks
Exploiting graphs in the presence of noise and interference is another recent topic of interest in the community, and several presentations touched on this point. In practice, users typically have some prior knowledge (or domain expertise) that suggests probable structure within the network, and algorithms should be developed in consideration of the fact that some of the structure is uninteresting. The symposium included discussions about experimental design in the presence of interference in order to optimize inference ability from the measurements. As community detection relies on metrics that are sensitive to noise in the data, metrics that are resilient to noisy observations was another topic of interest.
Adversarial network analysis
Adversarial interference is an important special case in noisy graph analysis. In this setting, an adversary specifically manipulates the data to counter and misdirect the exploitation task. This area has significant implications for tasks in cyber security and counterterrorism, when a common objective is to uncover a subgraph of interest in which actors are deliberately covert. Presentations on this topic included models for attacker behavior and classes of methods to mitigate the effects of purposeful data corruption.
Multi-modal, multi-layer networks
Since networks change over time and have different connections when seen through different media, analyzing dynamic graphs and multigraphs has become a necessity. Multiple presentations addressed fusion of information over time and across multiple observations. Challenges identified in this area include development of models for temporal evolution of graphs, optimal fusion of information across modalities, and quantification of the benefits and limitations of inference across observations.
Big data analysis and management
Graphs are frequently extracted from extremely large datasets, and dealing with data of this scale and variety is a challenge inherent in modern network analysis. In this context, the symposium included presentations on personalized recommendations from global data and exploitation of open source and social media data for disaster response. From the perspective of big data management, there are currently active efforts toward native implementation of key computational kernels for graph exploitation algorithms in a large-scale database system.
Bringing together unique perspectives from research, applications, and operations, the sixth annual GraphEx Symposium helped influence the direction of basic network science research in support of current critical technological needs. As capabilities and technologies evolve, the symposium organizers intend to maintain GraphEx as a venue for ensuring continued research-to-practice connectivity.
Information about Lincoln Laboratory’s Graph Exploitation Symposium, including proceedings of past meetings, can be found here.
This work is sponsored by the Assistant Secretary of Defense for Research & Engineering under Air Force Contract FA8721-05-C-0002. Opinions, interpretations, conclusions, and recommendations are those of the authors and are not necessarily endorsed by the United States Government.
Rajmonda S. Caceres and Benjamin A. Miller are Technical Staff in the Cyber Analytics and Decision Systems Group at MIT Lincoln Laboratory.