Complex Networked Systems Program
Complex Networked Systems Program
Complex Networked Systems Program
Authors:
James M. Brase
David L. Brown
Lawrence Livermore National Laboratory
May 2009
Front and back covers: Diagrams of the Abstract Syntax Tree (AST) internal
representation of a simple C++ program. The firework burst patterns are
namespaces and different parts of the internal classes, functions and code within
functions. The front cover shows the AST for source code, while the back cover
shows a similar AST used to represent the structure of binary executables for
analysis.
Source: Dan Quinlan, Center for Applied Scientific Computing, Lawrence Livermore
National Laboratory
Disclaimer
This document was prepared as an account of work sponsored by an agency of the United States government. Neither
the United States government nor Lawrence Livermore National Security, LLC, nor any of their employees makes any
warranty, expressed or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or
usefulness of any information, apparatus, product, or process disclosed, or represents that its use would not infringe
privately owned rights. Reference herein to any specific commercial product, process, or service by trade name,
trademark, manufacturer, or otherwise does not necessarily constitute or imply its endorsement, recommendation, or
favoring by the United States government or Lawrence Livermore National Security, LLC. The views and opinions of
authors expressed herein do not necessarily state or reflect those of the United States government or Lawrence
Livermore National Security, LLC, and shall not be used for advertising or product endorsement purposes.
LLNL-TR-412733
This work performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory
under Contract DE-AC52-07NA27344.
Executive Summary
Many complex systems of importance to the U.S. Department of Energy consist of
networks of discrete components. Examples are cyber networks, such as the
internet and local area networks over which nearly all DOE scientific, technical and
administrative data must travel, the electric power grid, social networks whose
behavior can drive energy demand, and biological networks such as genetic
regulatory networks and metabolic networks. In spite of the importance of these
complex networked systems to all aspects of DOEs operations, the scientific basis
for understanding these systems lags seriously behind the strong foundations that
exist for the physically-based systems usually associated with DOE research
programs that focus on such areas as climate modeling, fusion energy, high-energy
and nuclear physics, nano-science, combustion, and astrophysics.
DOE has a clear opportunity to develop a similarly strong scientific basis for
understanding the structure and dynamics of networked systems by supporting a
strong basic research program in this area. Such knowledge will provide a broad
basis for, e.g., understanding and quantifying the efficacy of new security
approaches for computer networks, improving the design of computer or
communication networks to be more robust against failures or attacks, detecting
potential catastrophic failure on the power grid and preventing or mitigating its
effects, understanding how populations will respond to the availability of new
energy sources or changes in energy policy, and detecting subtle vulnerabilities in
large software systems to intentional attack.
This white paper outlines plans for an aggressive new research program designed to
accelerate the advancement of the scientific basis for complex networked systems of
importance to the DOE. It will focus principally on four research areas:
(1) understanding network structure,
(2) understanding network dynamics,
(3) predictive modeling and simulation for complex networked systems, and
(4) design, situational awareness and control of complex networks.
The program elements consist of a group of Complex Networked Systems Research
Institutes (CNSRI), tightly coupled to an associated individual-investigator-based
Complex Networked Systems Basic Research (CNSBR) program. The CNSRIs will be
principally located at the DOE National Laboratories and are responsible for
identifying research priorities, developing and maintaining a networked systems
modeling and simulation software infrastructure, operating summer schools,
workshops and conferences and coordinating with the CNSBR individual
investigators. The CNSBR individual investigator projects will focus on specific
challenges for networked systems. Relevancy of CNSBR research to DOE needs will
be assured through the strong coupling provided between the CNSBR grants and the
CNSRIs.
Can
we
detect a potential catastrophic failure on the
fundamentally an
power grid and prevent or mitigate its effects?
information enterprise
Can we understand how populations will respond to the
that depends on assuring
availability of new energy sources, or to changes in
the underlying complex
energy policy?
Can we understand the behavior of large-scale
information networks.
software systems at a level that allows us to detect
In addition to cyber
subtle vulnerabilities to attack?
networks, such as the
internet and local area
networks, other complex
Graph models are used extensively to model network structure. How can
these mathematical structures extend to incorporate dynamics? How can
they scale as the networks grow?
Modeling dynamic processes in complex networks will require machine
learning methods incorporating multivariate time-varying statistics16.
Understanding the performance of these approaches in noisy, nonstationary
environments raises many open mathematical problems. The learning
process itself becomes a dynamic system coupled to the system being
modeled.
Emergent behavior is one of the hallmarks of complex network dynamics17.
Capturing the nonlinear interactions that produce these effects is an
important component of the network model. Developing stability conditions
and understanding phase transitions will be required.
Understanding the foundations of network dynamics requires providing
theoretical bounds on reconstructability of network dynamics and estimates
of confidence in model structure and parameters.
Figure 1: The DOE Complex Networked Systems program consists of two main elements, the
Networked Systems Research Institute (CNSRI) program, and the Networked Systems Basic
Research (CNSBR) program. The CNSRI' s are DOE Lab-directed institutes that coordinate
large program sub-areas, while the CNSBRs are individual investigator research efforts based
largely in academia and industry. To assure DOE-relevance, each of the CNSBRs is affiliated
with one or more of the CNSRIs.
The CNSRIs will also run summer research programs, workshops and conferences
that will bring PIs from the CNSBR program, and other federal or international
programs, to promote exchange of ideas and to encourage the development of
collaborative partnerships.
Complementing the integrative function of the DOE Laboratory-based CNSRIs, the
finer-grained CNSBR program is an essential component of the complex network
research program. These projects will perform investigations in focused areas of
complex network research. Each project in the CNSBR program will be affiliated
with one of the CNSRIs whose responsibility it is to integrate the research effort
into the full-scale program.
This program structure also provides natural interfaces to other DOE programs in
the specific focus areas. For example a CNSRI on Information Network Simulation
would provide powerful tools and capabilities to DOE and NNSA cybersecurity and
networking programs.
10
Brown, D. L., et. al., Applied Mathematics at the U. S. Department of Energy: Past,
Present and a View to the Future, Lawrence Livermore National Laboratory Report
LLNL-TR-401536, May 2008.
2
Carreras, B. A., Lynch, V.E., Dobson I., and Newman, D. E., Critical points and
transitions in an electric power transmission model for cascading failure blackouts,
Chaos 12, 985-994, (2002).
Arionos, S., Bonpard, E., Carbone, A., and Xue, F., Power Grid Vulnerability: A
Complex Network Approach, Chaos 19, 1, March 2009.
6
Amaral, L. A. N., and Ottino, J. M., Complex networks, Eur. Phys. J. B 38, 147-162
(2004).
Newman, M. E. J., The structure and function of complex networks, SIAM Review
45, 167-256 (2003).
8
Eubank, S., Kumar, V.S.A., Marathe, M. V., and Srinivasan, A., Structural and
algorithmic aspects of massive social networks, in: Discrete Methods in
Epidemiology, Abello J, Cormode, G (ed.). DIMACS Series in Discrete Mathematics
and Theoretical Computer Science, 70, 2006:179-185.
11
Sen, P., Namata, G., Bilgic, M., Getoor, L., Gallagher, B., and Eliassi-Rad, T.,
Collective classification in network data, AI Magazine, 29(3), 93-106 (2008).
12
Aguiar, M. and Bar-Yam, Y., Spectral analysis and the dynamic response of
complex networks, Phys. Rev. E 7, 016106 (2005).
13
12
14
Strogatz, S., Exploring complex networks, nature 410, 268, 8 March 2001.
Motter, A., Matias, M., Kurths, J., and Ott, E., Dynamics on Complex Networks and
Applications, Physica D 224, 2006.
15
Sun, J., Tsourakakis, C., Hoke, E., Faloutsos, C., and Eliassi-Rad, T., Two Heads
Better Than One: Pattern Discovery in Time-evolving Multi-aspect Data, Data
Mining and Knowledge Discovery, 17(1), 111-128 (2008).
16
Sole, R. and Valverde, S., Information transfer and phase transitions in a model of
Internet traffic, Physica A 289, 595, 2001.
17
Huberman, B., and Glance, N., Evolutionary games and computer simulations,
Proc. National Academy of Science USA 90, 7716, 1993.
19
LLNL-TR-412733