GI LogoGI Logo
  • Login
Digital Library
    • All of DSpace

      • Communities & Collections
      • Titles
      • Authors
      • By Issue Date
      • Subjects
    • This Collection

      • Titles
      • Authors
      • By Issue Date
      • Subjects
Digital Library Gesellschaft für Informatik e.V.
GI-DL
    • English
    • Deutsch
  • English 
    • English
    • Deutsch
View Item 
  •   DSpace Home
  • Lecture Notes in Informatics
  • Proceedings
  • INFORMATIK - Jahrestagung der Gesellschaft für Informatik e.V.
  • P294 - INFORMATIK 2019 - 50 Jahre Gesellschaft für Informatik – Informatik für Gesellschaft
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
  •   DSpace Home
  • Lecture Notes in Informatics
  • Proceedings
  • INFORMATIK - Jahrestagung der Gesellschaft für Informatik e.V.
  • P294 - INFORMATIK 2019 - 50 Jahre Gesellschaft für Informatik – Informatik für Gesellschaft
  • View Item

Finding Tiny Clusters in Bipartite Graphs

Author:
Neumann, Stefan [DBLP]
Abstract
We study the problem of finding clusters in random bipartite graphs. Applications of this problem include online shops in which one wants to find customers who purchase similar products and groups of products which are frequently bought together. We present a simple two-step algorithm which provably finds tiny clusters of size O(n" ), where n is the number of vertices in the graph and " > 0; previous algorithms were only able to identify medium-sized clusters consisting of at least (pn) vertices. We practically evaluate the algorithm on synthetic and on real-world data; the experiments show that the algorithm can find extremely small clusters even when the graphs are very sparse and the data contains a lot of noise.
  • Citation
  • BibTeX
Neumann, S., (2019). Finding Tiny Clusters in Bipartite Graphs. In: David, K., Geihs, K., Lange, M. & Stumme, G. (Hrsg.), INFORMATIK 2019: 50 Jahre Gesellschaft für Informatik – Informatik für Gesellschaft. Bonn: Gesellschaft für Informatik e.V.. (S. 253-254). DOI: 10.18420/inf2019_30
@inproceedings{mci/Neumann2019,
author = {Neumann, Stefan},
title = {Finding Tiny Clusters in Bipartite Graphs},
booktitle = {INFORMATIK 2019: 50 Jahre Gesellschaft für Informatik – Informatik für Gesellschaft},
year = {2019},
editor = {David, Klaus AND Geihs, Kurt AND Lange, Martin AND Stumme, Gerd} ,
pages = { 253-254 } ,
doi = { 10.18420/inf2019_30 },
publisher = {Gesellschaft für Informatik e.V.},
address = {Bonn}
}
DateienGroesseFormatAnzeige
paper3_07.pdf81.18Kb PDF View/Open

Sollte hier kein Volltext (PDF) verlinkt sein, dann kann es sein, dass dieser aus verschiedenen Gruenden (z.B. Lizenzen oder Copyright) nur in einer anderen Digital Library verfuegbar ist. Versuchen Sie in diesem Fall einen Zugriff ueber die verlinkte DOI: 10.18420/inf2019_30

Haben Sie fehlerhafte Angaben entdeckt? Sagen Sie uns Bescheid: Send Feedback

More Info

DOI: 10.18420/inf2019_30
ISBN: 978-3-88579-688-6
ISSN: 1617-5468
xmlui.MetaDataDisplay.field.date: 2019
Language: en (en)
Content Type: Text/Conference Paper

Keywords

  • Biclustering
  • Bipartite Graphs
  • Random Graphs
  • Stochastic Block Models
Collections
  • P294 - INFORMATIK 2019 - 50 Jahre Gesellschaft für Informatik – Informatik für Gesellschaft [85]

Show full item record


About uns | FAQ | Help | Imprint | Datenschutz

Gesellschaft für Informatik e.V. (GI), Kontakt: Geschäftsstelle der GI
Diese Digital Library basiert auf DSpace.

 

 


About uns | FAQ | Help | Imprint | Datenschutz

Gesellschaft für Informatik e.V. (GI), Kontakt: Geschäftsstelle der GI
Diese Digital Library basiert auf DSpace.