English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Multi-agent random walks for local clustering on graphs

Alamgir, M., & von Luxburg, U. (2010). Multi-agent random walks for local clustering on graphs. In G. Webb, B. Liu, C. Zhang, D. Gunopulos, & X. Wu (Eds.), IEEE International Conference on Data Mining (ICDM 2010) (pp. 18-27). Piscataway, NJ, USA: IEEE.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/21.11116/0000-0002-7E39-2 Version Permalink: https://hdl.handle.net/21.11116/0000-0002-7E3A-1
Genre: Conference Paper

Files

show Files

Locators

show
hide
Locator:
https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5693955 (Publisher version)
Description:
-
OA-Status:

Creators

show
hide
 Creators:
Alamgir, M1, 2, Author           
von Luxburg, U1, 2, Author           
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

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: 2010-12
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1109/ICDM.2010.87
 Degree: -

Event

show
hide
Title: IEEE International Conference on Data Mining (ICDM 2010)
Place of Event: Sydney, Australia
Start-/End Date: 2010-12-13 - 2010-12-17

Legal Case

show

Project information

show

Source 1

show
hide
Title: IEEE International Conference on Data Mining (ICDM 2010)
Source Genre: Proceedings
 Creator(s):
Webb, GI, Editor
Liu, B, Editor
Zhang, C, Editor
Gunopulos, D, Editor
Wu, X, Editor
Affiliations:
-
Publ. Info: Piscataway, NJ, USA : IEEE
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 18 - 27 Identifier: ISBN: 978-1-4244-9131-5