Spanning Concept Trees: Algorithms and Interaction

The Concept Tree is a means of browsing the concept lattice of a formal context using readily-available tools for the interactive visualisation of trees. While respecting the lattice order, the directed Concept Tree includes arcs between concepts which are not mutual covers, and hence is not a spanning tree of the lattice digraph. Such arcs misrepresent the structure of the digraph. This paper surveys and augments options for constructing a Spanning Concept Tree, including: as an auxiliary data structure of existing Formal Concept Analysis algorithms; transitive reduction of the partial order amongst previously-enumerated concepts to produce the lattice digraph, from which a spanning tree is then derived; a novel algorithm which exploits the Reverse Lectic Order (RLO) of intents to construct a spanning tree from the set of formal concepts; and a novel algorithm which identifies and remediates only those arcs in the Concept Tree which are not arcs in the lattice digraph. Both novel algorithms exploit the property that a post-order traversal of the Concept Tree returns the concepts in RLO. They produce Spanning Concept Trees in which the parent of each concept is its first cover in the RLO, and whose children, like those in the Concept Tree, are in RLO. However, some concepts in the Spanning Concept Tree may depart from their canonical positions in the Concept Tree. The implications of this departure for interactive exploration – vice algorithmic traversal – of the Spanning Concept Tree are also explored.