Dynamical systems on networks

We obtain results for two distinct dynamical models: the Kuramoto model, a general model for coupled oscillator systems, and a model for opinion formation in social networks. Our main focus is on understanding the fixed points of these systems and their stability. For many models the stability of such fixed points can be studied with a Laplacian matrix. We give a formula for the inertia of these matrices, characterizing the real parts of the spectrum, by relating them to another matrix depending on the network topology. We then study the Kuramoto model, and in particular, the phenomena of synchronization, when all oscillators rotate at a common frequency, which corresponds to a fixed point. This phenomenon is well-known to depend on the natural frequencies of the oscillators and, more specifically, that the chance of synchronization increases if the natural frequencies are more similar. We then give upper and lower bounds for the volume of the set such frequencies in frequency space. Our bounds can be formulated in terms of sums over spanning trees which we further use to deduce that the volume is intimately related to the number of spanning trees for dense networks. We also characterize the structure of fixed points of the Kuramoto model by showing that every fixed point corresponds to a lattice point in a certain set which records how the phase-angles wrap around cycles in the network. As a consequence, under mild conditions, we derive the rate of growth of the number of fixed points as we consider increasingly large graphs with fixed topology. We also consider a model for opinion formation in social networks. More specifically, we characterize the global minima of an energy functional, intuitively the ``most stable" configurations, when the network is ``balanced" as well as show that the number of stable configurations can increase as we increase the strengths of the relationships in the network. Finally, we describe an algorithm for generating certain random networks. These networks are generalizations of Erd\H{o}s-R\'{e}nyi graphs with correlations between pairs of edges depending on the particular pattern they create. We then use this algorithm to study the effect on fixed points of network properties and therefore the dynamics of the Kuramoto model