Title: Detecting bicliques in GF[q]
Authors: Ramon, Jan ×
Miettinen, Pauli #
Vreeken, Jilles #
Issue Date: Sep-2013
Publisher: Springer
Series Title: Lecture Notes in Computer Science vol:8188 pages:509-524
Conference: European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD) location:Prague, Czech republic date:23-27 September 2013
Abstract: We consider the problem of finding planted bicliques in random matrices over $\GF[q]$. That is, our input matrix is a $\GF[q]$-sum of an unknown biclique (rank-1 matrix) and a random matrix. We study different models for the random graphs and characterize the conditions when the planted biclique can be recovered. We also empirically show that a simple heuristic can reliably recover the planted bicliques when our theory predicts that they are recoverable.

Existing methods can detect bicliques of $O(\sqrt{N})$, while it is \NP-hard to find the largest such clique. Real graphs, however, are typically extremely sparse and seldom contain such large bicliques. Further, the noise can destroy parts of the planted biclique. We investigate the practical problem of how small a biclique can be and how much noise there can be such that we can still approximately correctly identify the biclique. Our derivations show that with high probability planted bicliques of size logarithmic in the network size can be detected in data following the Erd\H{o}s-R\'{e}nyi model and two bipartite variants of the Barab\'{a}si-Albert model.
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
paper.pdfdraft Published 512KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.