# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Multi-agent random walks for local clustering

##### External Ressource

No external resources are shared

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Alamgir, M., & von Luxburg, U. (2010). Multi-agent random walks for local clustering.
In *IEEE International Conference on Data Mining (ICDM 2010)* (pp. 18-27). Piscataway, NJ,
USA: IEEE.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0013-BD34-8

##### 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.