Monday, October 24, 2011 - 1:30pm - 2:30pm
Aarti Singh (Carnegie-Mellon University)
Despite the empirical success of spectral clustering, its performance under noise and incomplete data is not well understood. This talk will provide a precise characterization of the misclustering rate of spectral clustering for large graphs. Using minimax theory, we establish information theoretic lower bounds on the amount of noise any clustering algorithm can tolerate and demonstrate that spectral clustering is near-optimal. The gap relative to the optimal performance is the statistical price that needs to be paid for computational efficiency.
Monday, October 24, 2011 - 9:00am - 10:00am
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
Monday, September 26, 2011 - 9:15am - 10:00am
Bin Yu (University of California, Berkeley)
In recent years network analysis have become the focus of much
research in many fields including biology, communication studies,
economics, information science, organizational studies,
and social psychology. Communities or clusters of highly connected actors
form an essential feature in the structure of several empirical networks.
Spectral clustering is a popular and computationally feasible method to
discover these communities.

The Stochastic Block Model is a social network model with well defined
Monday, September 26, 2011 - 3:00pm - 4:00pm
Robert Nowak (University of Wisconsin, Madison)
Clustering and ranking is often based on pairwise similarities (metric data) or comparisons (ordinal data). Most methods assume that the entire collection of all possible pairwise similarities or comparisons are known, but in high-dimensional settings there may be missing data and/or the costs of collecting this information may be prohibitive. The existence of clusters or other intrinsic low-dimensional structure can induce redundancy in these data, and therefore it may be possible to robustly cluster or rank based on a small subset of the data.
Friday, May 30, 2008 - 9:55am - 10:45am
The cluster of receptors and associated proteins at the 'front
end' of the E. coli chemotaxis pathway is a paradigm for
membrane complexes in cells. Like focal adhesions and synapses,
it acts as a solid-state computational device that amplifies,
integrates, and parses chemical signals from the environment
and relays the output to the rest of the cell. Ten years ago we
proposed a structure for this receptor cluster and suggested
how it might provide a basis for the very high sensitivity of


Subscribe to RSS - Clustering