Breadth first search graph partitions and concept lattices

James Abello, Alex J. Pogel, Lance Miller

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We apply the graph decomposition method known as rooted level aware breadth first search to partition graph-connected formal contexts and examine some of the consequences for the corresponding concept lattices. In graph-theoretic terms, this lattice can be viewed as the lattice of maximal bicliques of the bipartite graph obtained by symmetrizing the object-attribute pairs of the input formal context. We find that a rooted breadth-first search decomposition of a graph-connected formal context leads to a closely related partition of the concept lattice, and we provide some details of this relationship. The main result is used to describe how the concept lattice can be unfolded, according to the information gathered during the breadth first search. We discuss potential uses of the results in data mining applications that employ concept lattices, specifically those involving association rules.

Original languageAmerican English
Pages (from-to)934-954
Number of pages21
JournalJournal of Universal Computer Science
Volume10
Issue number8
StatePublished - 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Bipartite Graph
  • Breadth First Search
  • Formal Concept Analysis

Fingerprint

Dive into the research topics of 'Breadth first search graph partitions and concept lattices'. Together they form a unique fingerprint.

Cite this