Seminar Details
2016-10-18 (14:00) : Network analysis through invariant subspaces: symmetries, graph partitions, and dynamics
At Euler building (A002)
Organized by Mathematical Engineering
Speaker :
Schaub, Michael
Abstract :
Many tools used in network analysis are grounded in the spectral decomposition of a matrix Q associated to the network structure, such as the adjacency matrix A, or the (normalized) Laplacian L; or products of such matrices. From an abstract viewpoint, we may thus interpret all these algorithms as assessing a dominant invariant linear subspace with respect to an appropriately chosen network descriptor matrix.
By limiting the subspace to be one-dimensional, we can recover centrality measures including the famous PageRank algorithm, the Katz centrality, and Kleinberg's HITS score (which is based on the SVD of A). Considering dominant subspaces of larger sizes naturally leads to spectral clustering, and other graph partitioning algorithms.
However, instead of looking only at the dominant invariant subspaces, in this talk we will be concerned with a different class of invariant subspaces, namely, those invariant subspaces that can be spanned by the indicator vectors of a graph partition.
Such invariant subspaces are naturally related to so called (external) equitable graph partitions, which are closely associated to the inherent symmetries in the network. As we will show, by analysing these invariant subspaces and the associated graph partitions, we can gain insights about various kinds of cluster synchronization behaviours in consensus dynamics and networks of coupled oscillators, such as Kuramoto oscillators.
Joint work with N. O'Clery, Y.Billeh, R. Lambiotte, J.-C. Delvenne, and M.Barahona