JUCS - Journal of Universal Computer Science 10(8): 934-954, doi: 10.3217/jucs-010-08-0934
Breadth First Search Graph Partitions and Concept Lattices
expand article infoJames Abello, Alex J. Pogel§, Lance Miller|
‡ DIMACS, Rutgers University, United States of America§ New Mexico State University, United States of America| University of Connecticut, United States of America
Open Access
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.
formal concept analysis, Bipartite Graph, Breadth First Search