hide
Free keywords:
-
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.
