第1页 / 共264页
第2页 / 共264页
第3页 / 共264页
第4页 / 共264页
第5页 / 共264页
第6页 / 共264页
第7页 / 共264页
第8页 / 共264页
lectures on network systems.pdf
Preface
Contents
I Linear Systems
1 Motivating Problems and Systems
1.1 Social influence networks: opinion dynamics
1.2 Wireless sensor networks: averaging algorithms
1.3 Compartmental systems: dynamical flows among compartments
1.4 Appendix: Robotic networks in cyclic pursuit and balancing
1.5 Appendix: Design problems in wireless sensor networks
1.6 Appendix: List of examples and applications
1.7 Historical notes and further reading
1.8 Exercises
2 Elements of Matrix Theory
2.1 Linear systems and the Jordan normal form
2.2 Row-stochastic matrices and their spectral radius
2.3 Perron–Frobenius theory
2.4 Historical notes and further reading
2.5 Exercises
3 Elements of Graph Theory
3.1 Graphs and digraphs
3.2 Paths and connectivity in undirected graphs
3.3 Paths and connectivity in digraphs
3.4 Weighted digraphs
3.5 Appendix: Database collections and software libraries
3.6 Historical notes and further reading
3.7 Exercises
4 Elements of Algebraic Graph Theory
4.1 The adjacency matrix
4.2 Algebraic graph theory: basic and prototypical results
4.3 Graph theoretical characterization of irreducible matrices
4.4 Graph theoretical characterization of primitive matrices
4.5 Elements of spectral graph theory
4.6 Historical notes and further reading
4.7 Exercises
5 Discrete-time Averaging Systems
5.1 Averaging systems achieving consensus
5.2 Averaging with reducible matrices with multiple sinks
5.3 Appendix: Design of graphs weights
5.4 Appendix: Design and computation of centrality measures
5.5 Historical notes and further reading
5.6 Exercises
6 The Laplacian Matrix
6.1 The Laplacian matrix
6.2 Properties of the Laplacian matrix
6.3 Symmetric Laplacian matrices and the algebraic connectivity
6.4 Appendix: Community detection via algebraic connectivity
6.5 Appendix: Control design for clock synchronization
6.6 Historical notes and further reading
6.7 Exercises
7 Continuous-time Averaging Systems
7.1 Example systems
7.2 Continuous-time linear systems and their convergence properties
7.3 The Laplacian flow
7.4 Second-order Laplacian flows
7.5 Appendix: Design of weight-balanced digraphs
7.6 Historical notes and further reading
7.7 Exercises
8 The Incidence Matrix and its Applications
8.1 The incidence matrix
8.2 Properties of the incidence matrix
8.3 Cuts and cycles
8.4 Appendix: Distributed estimation from relative measurements
8.5 Historical notes and further reading
8.6 Exercises
9 Positive and Compartmental Systems
9.1 Example systems
9.2 Positive systems and Metzler matrices
9.3 Compartmental systems
9.4 Appendix: Symmetric physical flow systems
9.5 Appendix: A static nonlinear flow problem
9.6 Tables of asymptotic behaviors for averaging and positive systems
9.7 Historical notes and further reading
9.8 Exercises
II Topics in Averaging Systems
10 Convergence Rates, Scalability and Optimization
10.1 Some preliminary calculations and observations
10.2 Convergence factors for row-stochastic matrices
10.3 Cumulative quadratic disagreement for symmetric matrices
10.4 Circulant network examples and scalability analysis
10.5 Appendix: Accelerated averaging algorithm
10.6 Appendix: Design of fastest distributed averaging
10.7 Historical notes and further reading
10.8 Exercises
11 Time-varying Averaging Algorithms
11.1 Examples and models of time-varying discrete-time algorithms
11.2 Models of time-varying averaging algorithms
11.3 Convergence over time-varying graphs connected at all times
11.4 Convergence over time-varying digraphs connected over time
11.5 A new analysis method for convergence to consensus
11.6 Time-varying algorithms in continuous-time
11.7 Historical notes and further reading
11.8 Exercises
12 Randomized Averaging Algorithms
12.1 Examples of randomized averaging algorithms
12.2 A brief review of probability theory
12.3 Randomized averaging algorithms
12.4 Historical notes and further reading
12.5 Table of asymptotic behaviors for averaging systems
III Nonlinear Systems
13 Motivating Problems and Systems
13.1 Lotka-Volterra population models
13.2 Kuramoto coupled-oscillator models
13.3 Exercises
14 Stability Theory for Dynamical Systems
14.1 On sets and functions
14.2 Dynamical systems and stability notions
14.3 First main convergence tool: the Lyapunov Stability Criteria
14.4 Second main convergence tool: the Krasovskiı-LaSalle Invariance Principle
14.5 Application #1: Linear and linearized systems
14.6 Application #2: Negative gradient systems
14.7 Application #3: Continuous-time averaging systems and Laplacian matrices
14.8 Application #4: Positive linear systems and Metzler matrices
14.9 Historical notes and further reading
14.10 Exercises
15 Lotka-Volterra Population Dynamics
15.1 Two-species model and analysis
15.2 General results for Lotka-Volterra models
15.3 Cooperative Lotka-Volterra models
15.4 Historical notes and further reading
15.5 Exercises
16 Networks of Coupled Oscillators
16.1 Preliminary notation and analysis
16.2 Synchronization of identical oscillators
16.3 Synchronization of heterogeneous oscillators
16.4 Historical notes and further reading
16.5 Exercises
Bibliography
Subject Index
Lectures onNetwork SystemsFrancesco BulloWith contributions byJorge CortésFlorian DörflerSonia Martínez
Lectures on Network Systems
Francesco Bullo
Edition 1, 2018
CreateSpace (print-on-demand book publishing service)
ISBN 978-1-986425-64-3
With contributions by
Jorge Cortés, Florian Dörer, and Sonia Martínez
Citation Information:
F. Bullo, Lectures on Network Systems, ed. 1, CreateSpace, 2018, ISBN 978-1986425643, with
contributions by J. Cortés, F. Dörer, and S. Martínez
Book Website: Electronic versions of this document and updates are available at:
http://motion.me.ucsb.edu/book-lns
Book Copyright Notice: This document is intended for personal non-commercial use only: you may not
use this material for commercial purposes and you may not copy and redistribute this material in any
medium or format.
© Francesco Bullo 2012-18
edition 1 (revision v1.0 – May 1, 2018)
Figures Copyright Notice: All gures in this book are available at the book website and licensed under
the Creative Commons Attribution-ShareAlike 4.0 International License (CC BY-SA 4.0), available at:
https://creativecommons.org/licenses/by-sa/4.0. Exception to this gure license are:
(i) Permission is granted to reproduce Figure 13.5 as part of this work in both print and electronic formats,
for distribution worldwide in the English language; all other copyrights belong to its owner.
(ii) Figures 7.1a, 7.1b, 13.2a and 13.2b are in the public domain.
(iii) Figure 13.2c is picture "Hyänen und Löwe im Morgenlicht" by lubye134, licensed under Creative
Commons Attribution 2.0 Generic (BY 2.0).
To Marcello, Gabriella, and Lily
Preface
Books which try to digest, coordinate, get rid of the duplication, get rid of the less fruitful methods and
present the underlying ideas clearly of what we know now, will be the things the future generations will
value. Richard Hamming (1915-1998)
Topics These lecture notes provide a mathematical introduction to multi-agent dynamical systems, including
their analysis via algebraic graph theory and their application to engineering design problems. The focus is on
fundamental dynamical phenomena over interconnected network systems, including consensus and disagreement
in averaging systems, stable equilibria in compartmental ow networks, and synchronization in coupled oscillators
and networked control systems. The theoretical results are complemented by numerous examples arising from the
analysis of physical and natural systems and from the design of network estimation, control, and optimization
systems.
The book is organized in three parts: Linear Systems, Topics in Averaging Systems, and Nonlinear Systems.
The Linear Systems part, together with part on the Topics in Averaging Systems, includes
(i) several key motivating examples systems drawn from social, sensor, and compartmental networks, as well
as additional ones from robotics,
(ii) basic concepts and results in matrix and graph theory, with an emphasis on Perron–Frobenius theory,
algebraic graph theory and linear dynamical systems,
(iii) averaging systems in discrete and continuous time, described by static, time-varying and random matrices,
and
(iv) positive and compartmental systems, described by Metzler matrices, with examples from ecology, epidemiol-
ogy and chemical kinetics.
The Nonlinear Systems part includes
(v) networks of phase oscillator systems with an emphasis on the Kuramoto model and models of power
networks, and
(vi) population dynamic models, describing mutualism, competition and cooperation in multi-species systems.
Teaching instructions This book is intended for rst-year graduate students in science, technology, engineering,
and mathematics programs. For the rst part on Linear Systems, the required background includes competency in
linear algebra and only very basic notions of dynamical systems. For the third part on Nonlinear Systems, the
v
vi
required background includes a calculus course. The treatment is self-contained and does not require a nonlinear
systems course.
These lecture notes are meant to be taught over a quarter-long or semester-long course with a total 35 to 40
hours of contact time. On average, each chapter should require approximately 2 hours of lecture time or more.
Indeed, these lecture notes are an outgrowth of an introductory graduate course that I taught at UC Santa Barbara
over the last several years.
Part I is the core of the course. The order of Parts II and III is exchangeable. For example, it is possible to teach
Lyapunov stability theory in Chapter 14 before the analysis of time-varying averaging systems in Chapter 11.
Book versions These lecture notes are provided in multiple formats:
• a printed paperback version, published by CreateSpace (7in×10in, gray-scale), ISBN 978-1-986425-64-3,
• a tablet PDF version, optimized for viewing on tablets (3 × 4 aspect ratio, color), freely downloadable from
the book website,
• three documents meant for instructors and classroom teaching:
(i) a slides PDF version, that is an abbreviated version suited for displaying on a classroom projector, and
(ii) a classroom markup PDF version, that is, an abbreviated version of these notes (letter size, with large
sans-serif fonts, small margins), meant as markup copy for classroom teaching (i.e., print, mark, teach,
discard), and
(iii) a solution manual, available upon request by instructors at accredited institutions.
The book website is:
http://motion.me.ucsb.edu/book-lns
Self-publishing print-on-demand books There are several reasons why I decided to self-publish this book
via the print-on-demand book publishing service by Amazon CreateSpace. I appreciate being able to
(i) retain the full copyrights of all the material,
(ii) make the document freely available online in multiple versions (see above),
(iii) keep the paperback publication costs to a minimum and set a small price in a transparent manner,
(iv) update the book revision at any time (simply re-upload the PDF le, minimal turn-around time, no need for
any permission, and never out-of-print), and
(v) make available a high-quality paperback book through a broad distribution network.
Similar arguments are presented in the write-up Why I Self-Publish My Mathematics Texts With Amazon by Robert
Ghrist, the self-publishing author of (Ghrist, 2014).
This book is in rst edition and, specically, in its revision v1.0 – May 1, 2018. It is my intention to update the
document regularly and keep it available as a print-on-demand book by CreateSpace.
Acknowledgments
“Networks of Coupled Oscillators,” Sections 5.4, 6.4, 8.3 and 10.3, and a large number of exercises.
I am extremely grateful to Florian Dörer for his extensive contributions to Chapter 16
I am extremely grateful to Jorge Cortés and Sonia Martínez for their fundamental contribution to my under-
standing and our joint work on distributed algorithms and robotic networks; their scientic contribution is most
obviously present in Chapter 1 “Motivating Problems and Systems,” and Chapter 3 “Elements of Graph Theory.”
Lectures on Network Systems, F. Bullo, edition 1 (revision v1.0 – May 1, 2018). Tablet PDF version. Copyright © 2012-18.
vii
I am extremely grateful to Noah Friedkin, Alessandro Giua, Roberto Tempo, and Sandro Zampieri for numerous
detailed comments and insightful suggestions; their inputs helped shape the numerous chapters, especially the
treatment of averaging and social inuence networks. I wish to thank Enrique Mallada, Stacy Patterson, Victor
Preciado, and Tao Yang for adopting an early version of these notes and providing me with detailed feedback. I
wish to thank Jason Marden and Lucy Pao for their invitation to visit the University of Colorado at Boulder and
deliver an early version of these lecture notes.
A special thank you goes to all all senior and young scientists who read these notes and send me feedback.
Particular thanks go to Alex Olshevsky, Ashish Cherukuri, Bala Kameshwar Poolla, Basilio Gentile, Catalin Arghir,
Deepti Kannapan, Fabio Pasqualetti, Francesca Parise, Hideaki Ishii, John W. Simpson-Porco, Luca Furieri, Marcello
Colombino, Paolo Frasca, Pedro Cisneros-Velarde, Peng Jia, Saber Jafarpour, Shadi Mohagheghi, Tyler Summers,
Dominic Groß, Vaibhav Srivastava, Wenjun Mei, and Xiaoming Duan for their contributions to these lecture notes
and related homework.
I also would like to acknowledge the generous support received from funding agencies. This book is based on
work supported in part by the Army Research Oce through grants W911NF-11-1-0092 and W911NF-15-1-0577,
the Air Force Oce of Scientic Research through grant FA9550-15-1-0138, and the National Science Foundation
through grants CPS-1035917 and CPS-1135819. I wish to thank the the contributing authors and maintainers of
LATEX, openclipart.org and wikipedia.org.
Finally, I wish to thank Marcello, Gabriella, Lily, and my whole family for their loving support.
Santa Barbara, California, USA
29 Mar 2012 — 3 May 2018
Francesco Bullo
Lectures on Network Systems, F. Bullo, edition 1 (revision v1.0 – May 1, 2018). Tablet PDF version. Copyright © 2012-18.
Preface
Contents
I Linear Systems
1 Motivating Problems and Systems
.
Social inuence networks: opinion dynamics .
.
1.1
.
1.2 Wireless sensor networks: averaging algorithms .
.
1.3 Compartmental systems: dynamical ows among compartments .
.
1.4 Appendix: Robotic networks in cyclic pursuit and balancing .
1.5 Appendix: Design problems in wireless sensor networks
.
.
.
.
.
1.6 Appendix: List of examples and applications .
.
.
.
.
1.7 Historical notes and further reading .
1.8
.
.
.
.
.
Exercises .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Elements of Matrix Theory
Linear systems and the Jordan normal form .
2.1
.
2.2 Row-stochastic matrices and their spectral radius
.
2.3
.
.
2.4 Historical notes and further reading .
2.5
.
.
Perron–Frobenius theory .
Exercises .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Elements of Graph Theory
.
.
.
.
.
.
.
.
.
.
.
.
Paths and connectivity in undirected graphs .
Paths and connectivity in digraphs .
.
.
.
.
3.1 Graphs and digraphs
.
3.2
.
3.3
3.4 Weighted digraphs .
.
3.5 Appendix: Database collections and software libraries .
3.6 Historical notes and further reading .
.
.
.
3.7
Exercises .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4 Elements of Algebraic Graph Theory
viii
Contents
v
viii
1
3
3
4
5
6
8
10
11
13
15
16
20
22
27
28
33
33
35
35
38
39
40
41
43
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
