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. |
| Links: | |
| 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 |
| BibTeX Type: | Conference Paper (inproceedings) |
| Address: | Piscataway, NJ, USA |
| DOI: | 10.1109/ICDM.2010.87 |
| Event Name: | IEEE International Conference on Data Mining (ICDM 2010) |
| Event Place: | Sydney, Australia |
| Digital: | 0 |
| Electronic Archiving: | grant_archive |
| Language: | en |
| Organization: | Max-Planck-Gesellschaft |
| School: | Biologische Kybernetik |
BibTeX
@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},
author = {Alamgir, M. and von Luxburg, U.},
doi = {10.1109/ICDM.2010.87},
month_numeric = {12}
}