Banded structure in binary matrices

Abstract : A binary matrix has a banded structure if both rows and columns can be permuted so that the non-zero entries exhibit a staircase pattern of overlapping rows. The concept of banded matrices has its origins in numerical analysis, where entries can be viewed as descriptions between the problem variables; the bandedness corresponds to variables that are coupled over short distances. Banded data occurs also in other applications, for example in the physical mapping problem of the human genome, in paleontological data, in network data and in the discovery of overlapping communities without cycles. We study the banded structure of binary matrices, give a formal definition of the concept and discuss its theoretical properties. We consider the algorithmic problems of computing how far a matrix is from being banded, and of finding a good submatrix of the original data that exhibits approximate bandedness. Finally, we show by experiments on real data from ecology and other applications the usefulness of the concept. Our results reveal that bands exist in real datasets and that the final obtained orderings of rows and columns have natural interpretations.
Type de document :
Article dans une revue
Knowledge and Information Systems (KAIS), Springer, 2011, 28 (1), pp.197-226. 〈10.1007/s10115-010-0319-7〉
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00658836
Contributeur : Gemma C Garriga <>
Soumis le : mardi 17 avril 2012 - 18:32:20
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mercredi 18 juillet 2012 - 02:20:31

Fichier

bands_revised-v2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Gemma Garriga, Esa Junttila, Heikki Mannila. Banded structure in binary matrices. Knowledge and Information Systems (KAIS), Springer, 2011, 28 (1), pp.197-226. 〈10.1007/s10115-010-0319-7〉. 〈hal-00658836〉

Partager

Métriques

Consultations de la notice

385

Téléchargements de fichiers

340