de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Thesis

Community Analysis Using Local Random Walks

MPS-Authors
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;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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


Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-97AE-6
Abstract
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.