de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Hochschulschrift

Community Analysis Using Local Random Walks

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons136381

Kolev,  Pavel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45576

Sun,  He
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Kolev, P. (2013). Community Analysis Using Local Random Walks. Master Thesis, Universität des Saarlandes, Saarbrücken.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0024-97AE-6
Zusammenfassung
The problem of graph clustering is a central optimization problem with various applications in numerous fields including computational biology, machine learning, computer vision, data mining, social network analysis, VLSI design and many more. Essentially, clustering refers to grouping objects with similar properties in the same cluster. Designing an appropriate similarity measure is currently a state of the art process and it is highly depended on the underlying application. Generally speaking, the problem of graph clustering asks to find subsets of vertices that are well-connected inside and sparsely connected outside. Motivated by large-scale graph clustering, we investigate local algorithms, based on random walks, that find a set of vertices near a given starting vertex with good worst case approximation guarantees. The running time of these algorithms is nearly linear in the size of the output set and is independent of the size of the whole graph. This feature makes them perfect subroutines in the design of efficient parallel algorithms for graph clustering.