English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Metropolis Algorithms for Representative Subgraph Sampling

Hübler, C., Kriegel, H.-P., Borgwardt, K., & Ghahramani, Z. (2008). Metropolis Algorithms for Representative Subgraph Sampling. In F. Giannotti, D. Gunopulos, F. Turini, C. Zaniolo, N. Ramakrishnan, & X. Wu (Eds.), 2008 Eighth IEEE International Conference on Data Mining (pp. 283-292). Piscataway, NJ, USA: IEEE.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-C637-C Version Permalink: http://hdl.handle.net/21.11116/0000-0003-3792-A
Genre: Conference Paper

Files

show Files

Locators

show
hide
Description:
-

Creators

show
hide
 Creators:
Hübler, C, Author
Kriegel, H-P, Author
Borgwardt, K1, 2, Author              
Ghahramani, Z, Author
Affiliations:
1Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497794              
2Former Research Group Machine Learning and Computational Biology, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_2528696              

Content

show
hide
Free keywords: -
 Abstract: While data mining in chemoinformatics studied graph data with dozens of nodes, systems biology and the Internet are now generating graph data with thousands and millions of nodes. Hence data mining faces the algorithmic challenge of coping with this significant increase in graph size: Classic algorithms for data analysis are often too expensive and too slow on large graphs. While one strategy to overcome this problem is to design novel efficient algorithms, the other is to 'reduce' the size of the large graph by sampling. This is the scope of this paper: We will present novel Metropolis algorithms for sampling a 'representative' small subgraph from the original large graph, with 'representative' describing the requirement that the sample shall preserve crucial graph properties of the original graph. In our experiments, we improve over the pioneering work of Leskovec and Faloutsos (KDD 2006), by producing representative subgraph samples that are both smaller and of higher quality than those produced by other methods from the literature.

Details

show
hide
Language(s):
 Dates: 2008-12
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1109/ICDM.2008.124
BibTex Citekey: HublerKBG2008
 Degree: -

Event

show
hide
Title: Eighth IEEE International Conference on Data Mining (ICDM 2008)
Place of Event: Pisa, Italy
Start-/End Date: 2008-12-15 - 2008-12-19

Legal Case

show

Project information

show

Source 1

show
hide
Title: 2008 Eighth IEEE International Conference on Data Mining
Source Genre: Proceedings
 Creator(s):
Giannotti, F, Editor
Gunopulos, D, Editor
Turini, F, Editor
Zaniolo, C, Editor
Ramakrishnan, N, Editor
Wu, X, Editor
Affiliations:
-
Publ. Info: Piscataway, NJ, USA : IEEE
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 283 - 292 Identifier: ISBN: 978-0-7695-3502-9