Breadth First Search Graph Partitions and Concept Lattices

James Abello (DIMACS, Rutgers University, USA)

Alex J. Pogel (New Mexico State University, USA)

Lance Miller (University of Connecticut, USA)

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.

Keywords: Bipartite Graph, Breadth First Search, formal concept analysis

Categories: G.2.2, G.2.3