Graph Theoretic Methods in Networked Dynamic Systems
Tuesday, June 19, 2018, 14:00-17:45
Organized by:
Airlie Chapman
University of Melbourne
Australia
Mehran Mesbahi
University of Washington
USA
Tutorial Summary
In this half-day tutorial session, two leading researchers in the area of networked systems provide a concise, yet thorough tutorial on the key concepts in graph theory that have proved instrumental in the analysis and synthesis of multi-agent networked systems. The tutorial will first motivate a number of applications where the interaction topology between dynamic nodes plays a fundamental role on their stability and performance properties. These examples include robotic networks, formation flight, aerial swarms, distributed estimation and filtering, and distributed optimization, as well as infrastructure and social-cyber-physical systems. Examining system theoretic properties of such systems have direct implications for their performance, resilience, and security; as such, they provide a compelling motivation for abstracting these networks-and how their structure dictates their system theoretic properties-in terms of graph theoretical constructs.
Graphs are useful abstractions for networked systems that facilitate examining the role of the underlying information-exchange and interaction geometry on the behavior (e.g., noise attenuation, tracking, robustness, synchronization patterns) that these systems exhibit. In the meantime, graph theory is an elegant branch of discrete mathematics with a rich history and a number of sub-disciplines, such as algebraic graph theory, random graphs, and extremal graph theory. When graphs are embedded in linear control systems, the (linear) algebraic framework for analyzing graphs becomes particularly useful. One of the key components of this tutorial is delving into the necessary theoretical and computational results that highlight the elegance and the utility of such linear algebraic perspective that have been particularly useful for networked systems. In the meantime, the speakers will also provide insights and connections to other areas of graph theory that complements this linear algebraic framework for the analysis and synthesis of networked systems.
Tutorial Outline – Topics to be Covered
The tutorial is organized along the following topics:
- Motivation for networked systems
a. Centralized vs. decentralization
Dichotomy between centralization, decentralization, and networked systems. Fundamental aspects of coordination in large-scale systems with particular attention to trade-offs between computation, sensing, and communication.
b. Information-exchange
What are the mechanisms for information exchange through sensing and communication? Overview of models and parameterizations for sensing and communication networks.
c. Structure vs. function
Why does the structure matter in the performance and behavior of certain networked systems? We provide examples of scenarios where networks play a central role in characterizing dynamic behavior of systems as well as instances where the network structure plays a secondary role.
d. Representing networks as graphs; what aspects of networks are captured by graphs and what information is lost through such an abstraction.
- Graph theory
a. Basic concepts from graph theory, including walks, paths, cycles, diameter, cutsets, and partitions.
b. Linear algebra of graphs
Matrices associated with graphs, including adjacency, incidence, and Laplacian matrices and their variants; their eigenvalues and eigenvectors. What do spectral properties of networks say about the structure of the underlying network? Introduction to spectral graph theory.
c. Introduction to algebraic graph theory
Algebraic properties of graphs, characteristic polynomials and their coefficients and roots.
d. Operations of graphs, e.g., joints, unions, products.
e. Some useful operations on graphs with prescribed effect on the algebraic properties, including, joining graphs or taking various products of graphs, including Cartesian and tensor products.
- Graph-theoretic methods for analysis of networked systems
a. Connectivity and convergence rate
How network connectivity dictates convergence properties of distributed dynamic processes evolving on the network.
b. Lyapunov analysis on networks
How spectral graph theory has been used in the context of Lyapunov stability analysis?
c. Cycle structure and H2 performance
d. What is the role of cycles and other substructures in the network on the H2 performance and coherence?
e. Effective resistance and noise attenuation
How is effective resistance of the graph related to its noise attenuation properties and properties of random walks.
f. Symmetry and controllability/observability
How network symmetry can be parameterized and how it is related to controllability and observability of networked systems?
- Graph-theoretic methods for synthesis of networked systems
a. Network synthesis via semi-definite programming
How networks can be synthesized so that they have favorable structures as viewed from a system theoretic perspective?
b. bistributed learning on networks
How networks can evolve in a distributed manner to attain a favorable structure over time, as viewed from a system theoretic perspective; connections with distributed optimization and online learning.
If time permits, the speakers will also delve into distributed optimization and techniques for characterizing networks from time-series data, including connections between spectral graph theory, system identification, and reduced order modeling techniques such as principle component analysis and dynamic mode decomposition.
Hand-outs and exercises
This half-day tutorial session will provide a concise introduction to the necessary theoretical framework as well as computational means of analyzing and synthesizing networks in the context of networked dynamic systems. The participants will have access to the hand-outs and exercises that will accompany the tutorial.