Finding Tiny Clusters in Bipartite Graphs
| dc.contributor.author | Neumann, Stefan | |
| dc.contributor.editor | David, Klaus | |
| dc.contributor.editor | Geihs, Kurt | |
| dc.contributor.editor | Lange, Martin | |
| dc.contributor.editor | Stumme, Gerd | |
| dc.date.accessioned | 2019-08-27T12:55:22Z | |
| dc.date.available | 2019-08-27T12:55:22Z | |
| dc.date.issued | 2019 | |
| dc.description.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. | en |
| dc.identifier.doi | 10.18420/inf2019_30 | |
| dc.identifier.isbn | 978-3-88579-688-6 | |
| dc.identifier.pissn | 1617-5468 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/24978 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik e.V. | |
| dc.relation.ispartof | INFORMATIK 2019: 50 Jahre Gesellschaft für Informatik – Informatik für Gesellschaft | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-294 | |
| dc.subject | Biclustering | |
| dc.subject | Bipartite Graphs | |
| dc.subject | Random Graphs | |
| dc.subject | Stochastic Block Models | |
| dc.title | Finding Tiny Clusters in Bipartite Graphs | en |
| dc.type | Text/Conference Paper | |
| gi.citation.endPage | 254 | |
| gi.citation.publisherPlace | Bonn | |
| gi.citation.startPage | 253 | |
| gi.conference.date | 23.-26. September 2019 | |
| gi.conference.location | Kassel | |
| gi.conference.sessiontitle | Data Science |
Dateien
Originalbündel
1 - 1 von 1