Contents
1 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Basic Definitions and Examples . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Paths and Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Matrices and Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Examples of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5.1 Circulant Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5.2 Product Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.3 Cayley Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5.4 De Bruijn Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2 Averaging in Time-Invariant Networks . . . . . . . . . . . . . . . . . . . . . . 31
2.1 Rendezvous and Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2 Averaging on Symmetric Regular Graphs . . . . . . . . . . . . . . . . . . 33
2.3 Stochastic Matrices and Averaging . . . . . . . . . . . . . . . . . . . . . . 35
2.4 Convergence Rate and Eigenvalues . . . . . . . . . . . . . . . . . . . . . . 40
2.5 Consensus Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.6 Stochastic Matrices Adapted to a Graph . . . . . . . . . . . . . . . . . . . 44
2.7 Convergence Rate: Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.8 Reversible Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3 Averaging in Time-Varying Networks . . . . . . . . . . . . . . . . . . . . . . . 69
3.1 Time-Varying Updates: Uniform Connectivity . . . . . . . . . . . . . . 69
3.2 Time-Varying Updates: Cut-Balanced Interactions . . . . . . . . . . . 73
3.3 Randomized Updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4 Performance and Robustness of Averaging Algorithms . . . . . . . . . . 93
4.1 A Deeper Analysis of the Convergence to Consensus . . . . . . . . . 93
4.2 Rendezvous and Linear-Quadratic Control . . . . . . . . . . . . . . . . . 96
4.3 Robustness Against Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.4 Robustness Against Quantization Errors . . . . . . . . . . . . . . . . . . . 100
4.5 Distributed Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5 Averaging with Exogenous Inputs and Electrical Networks . . . . . . . 109
5.1 Electrical Networks and Harmonic Functions . . . . . . . . . . . . . . . 109
5.2 Effective Resistance in Electrical Networks . . . . . . . . . . . . . . . . 116
5.3 Averaging Dynamics with Stubborn Agents . . . . . . . . . . . . . . . . 119
5.4 Estimation from Relative Measurements . . . . . . . . . . . . . . . . . . . 121
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133