English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  How the result of graph clustering methods depends on the construction of the graph

Maier, M., von Luxburg, U., & Hein, M. (2013). How the result of graph clustering methods depends on the construction of the graph. ESAIM: Probability and Statistics, 17, 370-418. doi:10.1051/ps/2012001.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-B85C-9 Version Permalink: http://hdl.handle.net/21.11116/0000-0002-878C-8
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Maier, M1, Author              
von Luxburg, U1, Author              
Hein, M, Author              
Affiliations:
1Dept. Empirical Inference, Max Planck Institute for Intelligent Systems, Max Planck Society, DE, ou_1497647              

Content

show
hide
Free keywords: -
 Abstract: We study the scenario of graph-based clustering algorithms such as spectral clustering. Given a set of data points, one rst has to construct a graph on the data points and then apply a graph clustering algorithm to nd a suitable partition of the graph. Our main question is if and how the construction of the graph (choice of the graph, choice of parameters, choice of weights) in uences the outcome of the nal clustering result. To this end we study the convergence of cluster quality measures such as the normalized cut or the Cheeger cut on various kinds of random geometric graphs as the sample size tends to innity. It turns out that the limit values of the same objective function are systematically dierent on dierent types of graphs. This implies that clustering results systematically depend on the graph and can be very dierent for dierent types of graph. We provide examples to illustrate the implications on spectral clustering.

Details

show
hide
Language(s):
 Dates: 2013-05
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1051/ps/2012001
BibTex Citekey: MaiervH2012
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: ESAIM: Probability and Statistics
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 17 Sequence Number: - Start / End Page: 370 - 418 Identifier: -