Dresden 2009 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

SYCS: Symposium Data Analysis in Complex Systems

SYCS 1: Data Analysis in Complex Systems: From Data to Models

SYCS 1.4: Hauptvortrag

Freitag, 27. März 2009, 12:00–12:30, BAR SCHÖ

Clustering and multiscale structure of graphs — •Boaz Nadler — Weizmann Institute of Science, Rehovot, Israel

Clustering of data and graph partitioning are fundamental problems in many scientific fields. Both problems are related since many clustering algorithms can be formulated as solutions to graph partitioning problems.

In this talk we focus on two issues. The first is a probabilistic interpretation of eigenvalue/eigenvector based methods, such as spectral clustering and normalized cut. We show the connection of these methods to the properties of random walks on graphs, thus explaining both their successes, but also highlighting their fundamental limitations, specifically in the presence of structures at different scales.

The second issue is the study of the multiscale structure of data and graphs. Motivated by the properties of random walks on graphs, we present a multiscale algorithm and a diffusion based coherence score to reveal the structure of graphs and detect salient clusters at different scales.