@inproceedings{6850,
  title = {Multi-agent random walks for local clustering},
  journal = {Proceedings of the IEEE International Conference on Data Mining (ICDM 2010)},
  abstract = {We consider the problem of local graph clustering
  where the aim is to discover the local cluster corresponding
  to a point of interest. The most popular algorithms to solve
  this problem start a random walk at the point of interest and
  let it run until some stopping criterion is met. The vertices
  visited are then considered the local cluster. We suggest a more
  powerful alternative, the multi-agent random walk. It consists
  of several “agents” connected by a fixed rope of length l. All
  agents move independently like a standard random walk on
  the graph, but they are constrained to have distance at most l
  from each other. The main insight is that for several agents it is
  harder to simultaneously travel over the bottleneck of a graph
  than for just one agent. Hence, the multi-agent random walk
  has less tendency to mistakenly merge two different clusters
  than the original random walk. In our paper we analyze
  the multi-agent random walk theoretically and compare it
  experimentally to the major local graph clustering algorithms
  from the literature. We find that our multi-agent random walk
  consistently outperforms these algorithms.},
  pages = {18-27},
  editors = {Webb, G. I., B. Liu, C. Zhang, D. Gunopulos, X. Wu},
  publisher = {IEEE},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Piscataway, NJ, USA},
  month = dec,
  year = {2010},
  slug = {6850},
  author = {Alamgir, M. and von Luxburg, U.},
  month_numeric = {12}
}