Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Boolean Matrix Factorization Meets Consecutive Ones Property

MPG-Autoren
/persons/resource/persons45046

Miettinen,  Pauli
Databases and Information Systems, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

arXiv:1901.05797.pdf
(Preprint), 227KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Tatti, N., & Miettinen, P. (2019). Boolean Matrix Factorization Meets Consecutive Ones Property. Retrieved from http://arxiv.org/abs/1901.05797.


Zitierlink: https://hdl.handle.net/21.11116/0000-0004-02F0-A
Zusammenfassung
Boolean matrix factorization is a natural and a popular technique for
summarizing binary matrices. In this paper, we study a problem of Boolean
matrix factorization where we additionally require that the factor matrices
have consecutive ones property (OBMF). A major application of this optimization
problem comes from graph visualization: standard techniques for visualizing
graphs are circular or linear layout, where nodes are ordered in circle or on a
line. A common problem with visualizing graphs is clutter due to too many
edges. The standard approach to deal with this is to bundle edges together and
represent them as ribbon. We also show that we can use OBMF for edge bundling
combined with circular or linear layout techniques.
We demonstrate that not only this problem is NP-hard but we cannot have a
polynomial-time algorithm that yields a multiplicative approximation guarantee
(unless P = NP). On the positive side, we develop a greedy algorithm where at
each step we look for the best 1-rank factorization. Since even obtaining
1-rank factorization is NP-hard, we propose an iterative algorithm where we fix
one side and and find the other, reverse the roles, and repeat. We show that
this step can be done in linear time using pq-trees. We also extend the problem
to cyclic ones property and symmetric factorizations. Our experiments show that
our algorithms find high-quality factorizations and scale well.