Transcript Brief overview of our MURI proposal

Next Generation
Network Science: An Overview
Michael Kearns and Ali Jadbabaie
University of Pennsylvania
Kick-off Meeting, July 28, 2008
ONR MURI: NexGeNetSci
Team Members
Dave Alderson
Brian Stickler
Jean Carlson
Naval Postgraduate School
UC Santa Barbara
Michael Kearns (PI)
Ali Jadbabaie
Shawndra Hill
University of Pennsylvania
John Doyle
Babak Hassibi
Caltech
Fan Chung Graham
UC San Diego
ONR MURI: NexGeNetSci
Good news:
Spectacular progress
Bad news:
• Persistent errors
and confusion
• Potentially
insurmountable
obstacles?
ONR MURI: NexGeNetSci
Challenges in the NS report:
1. Dynamics, spatial location, and information
propagation in networks.
2. Modeling and analysis of very large networks.
3. Design and synthesis of networks.
4. Increasing the level of rigor and mathematical
structure.
5. Abstracting common concepts across fields.
6. Better experiments and measurements of
network structure.
7. Robustness and security of networks.
ONR MURI: NexGeNetSci
Challenges
Goals
Abstraction (common concepts across fields)
Rigor (& math structure)
Issues
•
Dynamics (location, propagation)
•
Robustness (& security)
Levels of understanding
0.
1.
2.
3.
4.
Verbal
Data & statistics (Experiments & measurements)
Modeling & simulation
Analysis
Design & synthesis
ONR MURI: NexGeNetSci
Theory and the
Internet
Goals
• Abstraction
• Rigor
Issues
• Dynamics
• Robustness
Good news:
Spectacular progress
Levels
0. Verbal
1. Data & stats
2. Modeling & sim
3. Analysis
4. Design & synth
Topics:
• Traffic
• Topology
• Control and
dynamics (C&D)
• Layering/distributed
• Architecture
ONR MURI: NexGeNetSci
Huge and recent progress
Traffic Topology
C&D
Verbal
Data/stat
Mod/sim
Analysis
Synthesis
ONR MURI: NexGeNetSci
Architect
Layering
ure
Addressing challenges
project thrusts
vs. Challenges
Modeling
Analysis
Design and
Synthesis
Experiments
ONR MURI: NexGeNetSci
Network of Investigators
Alderson
Carlson
Doyle
Steckler
ChungGraham
Kearns
Hassibi
Hill
Jadbabaie
Watts
ONR MURI: NexGeNetSci
Thrust 1: Novel Algorithms
• Local, Distributed graph Algorithms (Chung-Graham,
Jadbabaie)
– Graph algorithms for partitioning
• Understanding role of Randomness , and Random graph
models (Chung-Graham, Doyle, Carlson)
– Beyond degree distributions
• Matching and re-identification, data mining (Hill)
– Efficient scoring and identity matching
ONR MURI: NexGeNetSci
Thrust 2: Dynamics on Networks
and Network Models
• Analysis and design of interconnected dynamical
systems over networks, distributed optimization
(Jadbabaie, Doyle, Hassibi)
– Global behaviors translated to local decisions
– Interplay of interconnection and dynamics
• Network formation games (Alderson, Kearns)
• New Models of Networks (Jadbabaie)
– From Graphs to Simplicial Complexes
ONR MURI: NexGeNetSci
Thrust 3:Architecture
•
Comparative Physiology of Network Architecture
(Alderson, Doyle, Carlson)
–
–
•
From Internet to biology
Robustness, fragility and evolvability of complex networks
Optimization , Layering, and games (Jadbabaie, Doyle,
Alderson, Kearns)
–
Layering as a tool for optimization decomposition
ONR MURI: NexGeNetSci
Thrust 4:Network Information
theory
• Entropic Vectors: New tool for network
information theory (Hassibi)
– Entropic vectors and convex optimization
• Fundamental limits in network information theory
(Doyle, Hassibi)
– Connecting fundamental limits due to information,
computation, and dynamics
ONR MURI: NexGeNetSci
Thrust 5: Behavioral Network
Science
• Behavioral and Mathematical models for
collective problem-solving (Kearns)
• Collective problem solving vs. distributed
optimization (Kearns, Jadbabaie)
ONR MURI: NexGeNetSci
Thrust 6:Testbeds and
Demonstrations
• Hastily Formed Networks (Steckler, Alderson)
– Analysis of Field exercise data
• Measurement and statistics of field operations
ONR MURI: NexGeNetSci