Banded structure in binary matrices

ABSTRACT

A 0--1 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 in this paper 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 ordering of rows and columns have natural interpretations.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: F. Alizadeh, R. M. Karp, L. A. Newberg, and D. K. Weisser. Physical mapping of chromosomes: A combinatorial problem in molecular biology. Algorithmica, 13(1/2):52--76, 1995.
• 3: Jonathan E. Atkins , Erik G. Boman , Bruce Hendrickson, A Spectral Algorithm for Seriation and the Consecutive Ones Problem, SIAM Journal on Computing, v.28 n.1, p.297-310, Feb. 1999 [doi>10.1137/S0097539795285771]
• 4: Cevdet Aykanat , Ali Pinar , Ümit V. Çatalyürek, Permuting Sparse Rectangular Matrices into Block-Diagonal Form, SIAM Journal on Scientific Computing, v.25 n.6, p.1860-1879, 2004 [doi>10.1137/S1064827502401953]
• 5: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 6: Arindam Banerjee , Chase Krumpelman , Joydeep Ghosh , Sugato Basu , Raymond J. Mooney, Model-based overlapping clustering, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081932]
• 7: Kellogg Speed Booth, Pq-tree algorithms., University of California, Berkeley, 1975
• 8: Pablo Burzyn , Flavia Bonomo , Guillermo Durán, NP-completeness results for edge modification problems, Discrete Applied Mathematics, v.154 n.13, p.1824-1844, 15 August 2006 [doi>10.1016/j.dam.2006.03.031]
• 9: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 10: E. Cuthill , J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th national conference, p.157-172, August 26-28, 1969 [doi>10.1145/800195.805928]
• 11: M. Fortelius. Neogene of the old world database of fossil mammals (NOW). http://www.helsinki.fi/science/now/, 2008.
• 12: K. K. Puolam¨aki, M. Fortelius, and H. Mannila. Seriation in paleontological data using Markov chain Monte Carlo methods. PLoS Comput Biol, 2, 2006.
• 13: I.-J. Lin and D. B. West. Interval digraphs that are indifference digraphs. In Graph theory, Combinatorics, and Algorithms, pages 751--765, 1992.
• 14: Heikki Mannila , Evimaria Terzi, Nestedness and segmented nestedness, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281245]
• 15: Ross M. McConnell, A certifying algorithm for the consecutive-ones property, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 16: S. Myllykangas, J. Himberg, T. Böhling, B. Nagy, J. Hollm´en, and S. Knuutila. Dna copy number amplification profiling of human neoplasms. Oncogene, 25:7324--7332, 2006.
• 17: C. H. Papadimitriou. The NP-completeness of the bandwidth minimization problem. Computing, 16:263--270, 1976.
• 18: F. S. Roberts. Indifference graphs. In Proof Techniques in Graph Theory, pages 139--146, 1969.
• 19: Richard Rosen, Matrix bandwidth minimization, Proceedings of the 1968 23rd ACM national conference, p.585-595, August 27-29, 1968 [doi>10.1145/800186.810622]
• 20: M. Sen , B. K. Sanyal, Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders, SIAM Journal on Discrete Mathematics, v.7 n.2, p.157-165, May 1994 [doi>10.1137/S0895480190177145]
• 21: A. Tucker. A structure theorem for the consecutive 1's property. Journal of Combinatorial Theory, Series B, 12(2):153--162, 1972.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Experimentation, Theory

Keywords:
0-1 data, banded matrices, consecutive ones property