Trees, Graphs and Clusters: Learning Network Structure through Clustering

Monday, October 24, 2011 - 9:00am - 10:00am
Keller 3-180
Brian Eriksson (University of Wisconsin, Madison), Robert Nowak (University of Wisconsin, Madison)
Graphs are commonly used to represent complex networks, such as the internet or
biological systems. The structure of a graph can be inferred by clustering
vertices based on dissimilarity measures correlated with the underlying
graph-distances. For example, internet hosts can be clustered by measured
latencies or traffic correlations and genes can be clustered according to
responses to varied experimental conditions. These clusters reveal the
structure of the underlying graph; e.g., internet routing or functional
pathways in biological systems. This tutorial talk will discuss theory,
methods, and applications of graph-learning based on clustering. Learning with
missing or incomplete data, which is the norm in practice, will be a key theme
in the discussion. The theory draws from ideas in statistical learning,
spectral and subspace clustering, and matrix completion. The main concepts
will be illustrated with examples from communication and biological network
inference problems.
MSC Code: