Seminar Details
2017-11-02 (11:00) : Graph embeddings and community detection -- a control theoretic perspective
At Euler building (room A002)
Organized by Mathematical Engineering
Speaker :
Schaub, Michael
Abstract :
Community detection, the task of partitioning a network into groups of nodes similar to each other according to some criterion, has received enormous attention in the past decade.
Many different notions of what constitutes a good community exist in the literature, some based on finding groups with high edge-density, a small cut between the different groups, or by assuming a particular (generative) model for the structure of the network as a whole.
In this talk we focus on a dynamical notion of community structure: we think of our system under study as a network of coupled dynamical units, and aim to find groups of nodes which influence the system in a coherent way for a particular time-scale.
Previous work, focusing on diffusion processes, has shown that such a perspective can indeed be fruitful, and that notions such as Modularity, spectral clustering and various other well-known graph partitioning heuristics can be recovered using this point of view.
In this talk we reconsider such a dynamical approach towards community detection using a more control-theoretic perspective.
This enables us not only to consider more general system descriptions, such as networks with both positive and negative edges, but also reveals interesting connections to ideas used in dimensionality reduction and graph embeddings.
More importantly, however, it also allows us to connect to concepts considered in Control Theory, such as controllability and observability Gramians, thereby offering a fresh perspective on the problems of community detection and graph embeddings.