Georgi S. Medvedev

Georgi S. Medvedev

A unified approach to studying convergence and stochastic stability of continuous time consensus protocols (CPs) is presented in this work. Our method applies to networks with directed information flow; both cooperative and noncooperative interactions; networks under weak stochastic forcing; and those whose topology and strength of connections may vary in time. The graph theoretic interpretation of the analytical results is emphasized. We show how the spectral properties, such as algebraic connectivity and total effective resistance, as well as the geometric properties, such the dimension and the structure of the cycle subspace of the underlying graph, shape stability of the corresponding CPs. In addition, we explore certain implications of the spectral graph theory to CP design. In particular, we point out that expanders, sparse highly connected graphs, generate CPs whose performance remains uniformly high when the size of the network grows unboundedly. Similarly, we highlight the benefits of using random versus regular network topologies for CP design. We illustrate these observations with numerical examples and refer to the relevant graph-theoretic results. Keywords: consensus protocol, dynamical network, synchronization, robustness to noise, algebraic connectivity, effective resistance, expander, random graph

Georgi S. Medvedev, Matthew S. Mizuhara

Motivated by the study of attractors in the Kuramoto model (KM) on graphs approximating the Sierpinski gasket (SG), we revisit the problem of harmonic maps (HMs) from SG to the circle, first considered by Strichartz. We provide a geometric proof of Strichartz's theorem, which states that for a prescribed degree and suitable boundary conditions, there exists a unique HM from SG to the circle. We extend this result to HMs on post-critically finite (p.c.f.) fractals. For continuous functions on SG, we define a degree given by vector of integers of arbitrary finite length. We show that the degree determines a homotopy class on SG with values in the circle. This provides an analog of the Hopf degree theorem on SG. We move on to analyze HMs. At the heart of our method lies an original construction of covering spaces. After lifting continuous functions on SG with values in the unit circle to continuous real-valued functions on the covering space, we use the harmonic extension algorithm to obtain a harmonic function on the covering space. The desired HM is obtained by restricting the domain of the harmonic function to the fundamental domain and projecting the range to the circle. Each covering space is constructed separately for HMs of a given homotopy class, capturing its intrinsic topology. We show that with suitable modifications the method applies to p.c.f. fractals, a large class of self-similar domains. We illustrate our method using numerical examples of HMs from SG to the circle and discuss the construction of covering spaces for several representative p.c.f. fractals, including the 3-level SG, hexagasket, and pentagasket. The results of this paper provide the foundation for a follow-up work where we give a complete description of attractors in the KM on graphs approximating p.c.f. fractals. Specifically, we show that all HMs identified in this paper are stable steady states of the KM.