Header logo is

Multi-agent random walks for local clustering


Conference Paper


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.

Author(s): Alamgir, M. and von Luxburg, U.
Journal: Proceedings of the IEEE International Conference on Data Mining (ICDM 2010)
Pages: 18-27
Year: 2010
Month: December
Day: 0
Editors: Webb, G. I., B. Liu, C. Zhang, D. Gunopulos, X. Wu
Publisher: IEEE

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

DOI: 10.1109/ICDM.2010.87
Event Name: IEEE International Conference on Data Mining (ICDM 2010)
Event Place: Sydney, Australia

Address: Piscataway, NJ, USA
Digital: 0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF


  title = {Multi-agent random walks for local clustering},
  author = {Alamgir, M. and von Luxburg, U.},
  journal = {Proceedings of the IEEE International Conference on Data Mining (ICDM 2010)},
  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},
  month_numeric = {12}