TY - JOUR

T1 - Spectral theory for dynamics on graphs containing attractive and repulsive interactions

AU - Bronski, Jared C.

AU - Deville, Lee

PY - 2014

Y1 - 2014

N2 - Many applied problems can be posed as a dynamical system defined on a network with attractive and repulsive interactions. Examples include synchronization of nonlinear oscillator networks; the behavior of groups, or cliques, in social networks; and the study of optimal convergence for consensus algorithm. It is important to determine the index of a matrix, i.e., the number of positive and negative eigenvalues, and the dimension of the kernel. In this paper we consider the common examples where the matrix takes the form of a signed graph Laplacian. We show that the there are topological constraints on the index of the Laplacian matrix related to the dimension of a certain homology group. When the homology group is trivial, the index of the operator is determined only by the topology of the network and is independent of the strengths of the interactions. In general, these constraints give bounds on the number of positive and negative eigenvalues, with the dimension of the homology group counting the number of eigenvalue crossings. The homology group also gives a natural decomposition of the dynamics into "fixed" degrees of freedom, whose index does not depend on the edge weights, and an orthogonal set of "free" degrees of freedom, whose index changes as the edge weights change. We also explore the spectrum of the Laplacians of signed random matrices.

AB - Many applied problems can be posed as a dynamical system defined on a network with attractive and repulsive interactions. Examples include synchronization of nonlinear oscillator networks; the behavior of groups, or cliques, in social networks; and the study of optimal convergence for consensus algorithm. It is important to determine the index of a matrix, i.e., the number of positive and negative eigenvalues, and the dimension of the kernel. In this paper we consider the common examples where the matrix takes the form of a signed graph Laplacian. We show that the there are topological constraints on the index of the Laplacian matrix related to the dimension of a certain homology group. When the homology group is trivial, the index of the operator is determined only by the topology of the network and is independent of the strengths of the interactions. In general, these constraints give bounds on the number of positive and negative eigenvalues, with the dimension of the homology group counting the number of eigenvalue crossings. The homology group also gives a natural decomposition of the dynamics into "fixed" degrees of freedom, whose index does not depend on the edge weights, and an orthogonal set of "free" degrees of freedom, whose index changes as the edge weights change. We also explore the spectrum of the Laplacians of signed random matrices.

KW - Dynamics on networks

KW - Graph Laplacian

KW - Social networks

KW - Spectral graph theory

UR - http://www.scopus.com/inward/record.url?scp=84931569479&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84931569479&partnerID=8YFLogxK

U2 - 10.1137/130913973

DO - 10.1137/130913973

M3 - Article

AN - SCOPUS:84931569479

VL - 74

SP - 83

EP - 105

JO - SIAM Journal on Applied Mathematics

JF - SIAM Journal on Applied Mathematics

SN - 0036-1399

IS - 1

ER -