Multi-agent random walks for local clustering

Alamgir, M; von Luxburg, U; Webb,; I., G.; Liu, B.; Zhang, C.; Gunopulos, D.; Wu, X.

doi:10.1109/ICDM.2010.87

Local TagsRelease HistoryDetailsSummary

Multi-agent random walks for local clustering

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.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-BD34-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-BD35-6

Genre: Conference Paper

Files

show Files

Locators

show

Creators

show

hide

Creators:
Alamgir, M¹, Author
von Luxburg, U¹, Author
Webb, Editor
I., G., Editor
Liu, B., Editor
Zhang, C., Editor
Gunopulos, D., Editor
Wu, X., Editor

Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795

Content

show

hide

Free keywords: -

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.

Details

show

hide

Language(s):

Dates: Date issued: 2010-12

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: -

Identifiers: URI: http://datamining.it.uts.edu.au/icdm10/
DOI: 10.1109/ICDM.2010.87
BibTex Citekey: 6850

Degree: -

Event

show

hide

Title: IEEE International Conference on Data Mining (ICDM 2010)

Place of Event: Sydney, Australia

Start-/End Date: -

Legal Case

show

Project information

show

Source 1

show

hide

Title: IEEE International Conference on Data Mining (ICDM 2010)

Source Genre: Proceedings

Creator(s):

Affiliations:

Publ. Info: Piscataway, NJ, USA : IEEE

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 18 - 27 Identifier: -