This paper is a preliminary attempt to study how modular and bimodular decomposition, used in graph theory, can be used on contexts and concept lattices in formal concept analysis (FCA). In a graph, a module is a set of vertices defined in term of behaviour with respect to the outside of the module: All vertices in the module act with no distinction and can be replaced by a unique vertex, which is a representation of the module. This definition may be applied to concepts of lattices, with slighty modifications (using order relation instead of adjacency). One can note that modular decomposition is not well suited for bipartite graphs. For example, every bipartite graph corresponding to a clarified context is trivially prime (not decomposable w.r.t modules). In [4], authors have introduced a decomposition dedicaced to bipartite graph, called the bimodular decomposition. In this paper, we show how modular decomposition of lattices and bimodular decomposition of contexts interact. These results may be used to improve readability of a Hasse diagram.
Concept lattices are well suited to deal with knowledge representation and
classification, but when the number of concepts grows, it is not very convenient
to visualize the Hasse diagram. To avoid this problem, some approaches keep
only part of the concepts (Iceberg lattice [
There is a lot of works in graph theory about decomposition of a graph. A
classical and well studied decomposition is the modular decomposition (see for
example [
Modular decomposition of graphs may be adapted to lattices with only little changes: In a graph, this is the adjacency relation which is fundamental, but it is the order relation for lattices.
Moreover, concept lattices are usually computed from a context, which can be considerated as a bipartite graph. So, there are two structures which can be decomposed: the concept lattice and the bipartite graph.
Unfortunately, bipartite graphs are not good candidates for modular
decomposition: except for twin vertices (vertices with the same neighbourghood) or
connected components, there are no modules (except trivial one’s) in such graphs.
To improve the decomposition of bipartite graph, the notion of bimodule is
introduced in [
Goal of this paper is to study how bimodules of a bipartite graph interact with modules of the concept lattice of this context, and to see how it can be used to help the visualisation of information contained in lattices.
The next section is dedicaced to definitions. Section 2.2 introduces modules of a graph and transposes the definition to lattice (modules of a lattice). Section 3 is about bimodules of a bipartite graph (context) and the links that exist with the corresponding concept lattice. After some discussion in section 4, we conclude the paper in section 5. 2 2.1
In this paper, all discrete structures are finites and all graphs are simples (no loops neither multi-edges). Since this paper is about usages of graph theory results, a formal context will be considerated as a bipartite graph B = (O; A; I) with O (objects) and A (attributes) being two stable sets of vertices, and I (incidence relation between objects and attributes) the set of edges of B.
For a vertex v, v′ denotes the neighbourghood of v (vertices adjacents to v). For a subset V of vertices, V ′ denotes the common neighbourhood (vertices which are adjacent to every vertices of V ). With this notation, the classical definition of galois connections follows immediately.
De nition 1 (Galois connections). For a set X ⊂ O, Y ⊆ A we de ne X′ = {y ∈ O | xIy for all x ∈ X},
Y ′ = {x ∈ A | xIy for all y ∈ Y }.
A clarified context is a context such that x′ = y′ implie x = y for any vertices of O ∪ A. A clarified context is reduced if no vertex v is such that v′ = V ′ with V ⊆ O ∪ A, v ̸∈ V .
A complete lattice L = (P; ≤; ∨; ∧) is a poset such that for all X ⊆ P , there exist a supremum and an infimum in P . j ∈ P is ∨-irreducible element if x∨y = j implies x = j or y = j. m ∈ P is a ∧-irreducible element if x ∧ y = m implies x = m or y = m. j covers a unique element j∗ (j∗ ≺ j), m is covered by a unique element m∗ (m ≺ m∗). We denote J the set of ∨-irreducible elements and M the set of ∧-irreducible elements.
For a formal context C = (O; A; I) a formal concept is a pair (X; Y ), X ⊆ O, X ⊆ A and X′ = Y and Y ′ = X. X is called the extent of the concept and Y is called the intent. The set of formal concepts ordered by inclusion on the intents is the concept lattice of C.
For every finite lattice L = (P; ≤; ∨; ∧) there is, up to isomorphism, a unique reduced context C = (J; M; ≤). In the following of this paper, we will consider only reduced contexts, i.e. contexts such that O = J , the set of ∨-irreducible elements and A = M the set of ∧-irreducible elements of L. 2.2
We denote a graph G with G = (V; E). V is the set of vertices and E a set of edges. Let X ⊂ V and s ∈ V \X. Then s distinguishes X if s′ ∩ X ̸= ∅ and s′ ∩ X ̸= X. That is, s is adjacent with some vertices of X and not adjacent with some others vertices of X. So, if no vertex distinguishes a set X, then for the outside of X and relation of adjacency, every vertex is similar and X can be viewed as a unique vertex.
vertices that no vertex distinguishes.
The graph which is obtained by the replacement of a module by a single vertex is called a quotient graph. It is a simplification of the original one (see Fig. 1). As no vertex distinguishes X (elements in dashed line), there exist only two possibilities for a vertex v not in X: either v is adjacent to every vertex of X (then there exists an edge between v and the representant of X) or v is adjacent with no vertex of X (then, there is no edge between v and the representant of X).
For a graph G = (V; E), the set V and singletons x ∈ V are trivial modules. A graph without non trivial module is called a prime graph (for the modular decomposition). Two modules A and B overlap if no one is a subset of the other and A ∩ B ̸= ∅. A module which does not overlap another module is a strong module.
Modules and strong modules are central in several decomposition processes
and their properties have been well studied. In the first definitions, modules
where defined with respect to the adjacency relation, but decompositions have
been generalized (for example in [
For a lattice, it is more natural to consider the order relation than an adjacency relation, so a natural definition follows immediately: (a)
(b) De nition 3. For a lattice L = (P; ≤; ∨; ∧), a lattice module is a set of elements X ⊆ P such that, for every y ∈ P \X, one of the three following statements is true: { ∀x ∈ X, x < y; { or ∀x ∈ X, x > y; { or ∀x ∈ X, x||y.
It is clear with this definition that a module in a lattice L is equivalent to a module (with respect to adjacency) in the graph obtained by transitive closure of the Hasse Diagram of L.
f
g a b c
h d
e (a) ⊤ ⊥
M1
M2 (b)
Let X ⊆ P be a subset of elements of a lattice L, with A = min(X) and B = max(X) the sets of minimal (resp. maximal) elements of X. X is a convex set iff for all y ∈ P such that a < y < b, a ∈ A, b ∈ B, then y ∈ X. If A and B are reduced to singletons, X is an interval. [A; B] denotes the convex set defined by the two sets A and B.
Lemma 1. Modules in lattices are convex sets.
Proof. Suppose it is not, then there exists y ∈ P \X with a < y < b and so, y distinguishes a and b. It follows that X is not a module.
From now, since lattices modules are convex sets, we will use the notation X = [A; B] to speak of a module X.
1. if |A| > 1 then A ⊆ J , 2. if |B| > 1 then B ⊆ M .
Proof. Suppose |A| > 1, and let A = a1; a2; : : : ; an.
Suppose ai ̸∈ J , then, since ai||aj there exists at least one ∨-irreducible element j such that j < ai and j ̸< aj , which is a contradiction with the fact that [A; B] is a module.
Dually proof applies for elements of B.
Note that when |A| = 1 (dually for B) the maximal element of the module is not necessary an irreducible one (See Fig. 3).
M6 M5 M4
1. if |A| > 2, ∧ A = ai ∧ aj for all ai; aj ∈ A. 2. if |B| > 2, ∨ B = bi ∨ bj for all bi; bj ∈ B.
Proof. Clearly, suppose |A| > 2 and there exist ai; aj ; ak ∈ A such that x1 = ai ∧ aj ̸= aj ∧ ak = x2. w.l.o.g suppose x1 ̸< x2. Then x1 < aj and x1 ̸< ak. It follows that x1 distinguishes [A; B].
As a preliminary remark, we recall that all considered contexts are reduced, and so, clarified. The clarification of a context is the fact to keep only one object o for all objects oi such that o′i = o′j (dually for attribute). It is clear that the set {o1; : : : ; on} is a module in the bipartite graph and this process is equivalent to replace twin vertices by a representant.
Modules are not well situed for bipartite graphs. Twin vertices and connected components are the only modules for these graphs which are poorly decomposable. In goal to improve the decomposition, Fouquet and all have introduced bimodule, an analog of module for bipartite graphs.
De nition 4 (Bimodule). Let C = (O; A; I) be a bipartite graph, and (X; Y ) ⊂ (O; A), then (X; Y ) is a bimodule if no x ∈ O\X distinguishes A and no y ∈ A\Y distinguishes O.
Example of bimodule is given in Fig. 4: b and c are not distinguished with respect to vertices 4 (none of them are adjacent) or 3 (each of them is adjacent). Similarly, 1 and 2 are not distinguished by a (each of them is adjacent) and d (none of them is adjacent).
1 2 3
4 a b c
d
Proof. By definition of a lattice module, no elements inside the modules are distinguished by elements outside. It follows directly that no ∨-irreducible element outside the module distinguishes ∧-irreducible elements inside, and conversely.
Now, we want to know how a bimodule on the context may be interpretated in the concept lattice. First, we define a set in the lattice L from a bimodule X.
From a bimodule X = (J1; M1) ⊆ (J; M ), we build a subset C of concepts in L such that: { attributes concepts of X are in C, { objects concepts of X are in C, { C = [A; B] is a convex set, with A being maximal elements of C and B being minimal elements of C.
As previously seen, a lattice module corresponds to a context bimodule but, with the previous construction, the converse may be false: There exist bimodules of a context such that [A; B] does not correspond to a module in the lattice. As an example, Fig. 5 shows the lattice for the bipartite graph in Fig. 4. The set [A; B] is bounded by a dashed line.
Nevertheless, we can observe that, even if [A; B] is not a module, there exists a possibility of simplification, replacing a set of elements by two vertices and an edge.
(abcd, ∅) (ac, 2) (ab, 1)
(bcd, 3)
Proposition 2. Let [A; B] be a convex set built from a non trivial bimodule X. If [A; B] is not a module, then 1. | |[A; B] ∩ M | − |[A; B] ∩ J | | ≤ 1 2. if |[A; B] ∩ M | = |[A; B] ∩ J |, then A ⊆ J and B ⊆ M 3. if |max([A; B] ∩ J )| > 1, a+ = ∨ ai, ai ∈ max([A; B] ∩ J ) is such that ai ≺ a+ 4. if |min([A; B] ∩ M )| > 1, b− = ∧ bi, bi ∈ min([A; B] ∩ M ) is such that b− ≺ bi Proof. First, we show that | |[A; B] ∩ M | − |[A; B] ∩ J | | ≤ 1:
Suppose that [A; B] is not a module of the concept lattice, then there exists an element x ̸∈ [A; B] which distinguishes [A; B]. Without lost of generality, we can consider that x ∈ J and there exist y ∈ [A; B] such that x < y. We denote P1 the set of elements of [A; B] which are greater than x and P2 = [A; B]\P1. Since x is a ∨-irreducible element, it does not distinguish any ∧-irreducible elements in [A; B]. It follows that all ∧-irreducible elements in [A; B] are in P1 and none of them in P2 (or conversely).
In a finite lattice, every element e is ∧-dense, i.e. equal to the infimum of ∧-irreducible elements greater than e.
All ∨-irreducible elements in P2 cannot be distinguished by ∧-irreducible elements outside [A; B]. One unique ∨-irreducible element jmax of P2 may be defined by jmax = ∧ mi; : : : ; mj , with mi; : : : ; mj ̸∈ P1. All other ∨-irreducible elements in P2 are distinguished by ∧-irreducible elements in P1 (and only by these elements). So P2 ∩ J = X ∪ {jmax} (jmax may not exist).
Suppose |X| < |[A; B] ∩ M |, then there exist m1; m2 ∈ [A; B] ∩ M , j1 ∈ X such that j1 < m1, j1 < m2, m1||m2. It follows that j1 < m1 ∧ m2, which is impossible since j1 ∈ P2 and elements in P2 are not comparable to x.
Similarly, suppose |X| > |[A; B] ∩ M |, At least one ∨-irreducible element j of X is smaller than two ∧-irreducible elements m1 and m2 of P1, with m1||m2. This is impossible, so |X| = |[A; B] ∩ M | and | |[A; B] ∩ M | − |[A; B] ∩ J | | ≤ 1.
A ⊆ J and B ⊆ M follow directly of the fact that, by construction A and B contain irreducible elements and for each ∧-irreducible element m ∈ [A; B], there exists a ∨-irreducible element j ∈ [A; B] such that j < m.
It remains to prove that, when max([A; B]∩J ) contains at least two elements, a+ = ∨ ai, ai ∈ max([A; B]∩J ) is such that ai ≺ a+ (and dually for b−). Suppose it is not the case, then exist at least two elements x1 and x2 smaller than a+ and such that x1 and x2 distinguish elements in A. It follows that one can find a ∧-irreducible element which distinguishes ∨-irreducible elements in A and that is a contradiction.
It follows from this proposition that even if a set [A; B] is not a module, it can be collapsed into two vertices j and m such that j < m (but maybe not j ≺ m). j is a representant for the set [A; B] ∩ J and m a representant for the set [A; B] ∩ M . Moreover, j ≺ a+ and b+ ≺ m. 4 4.1
It is known that the family of modules of a graph (and so, of a lattice) and the family of bimodules of a bipartite graph are closed by intersection. Since the whole graph is a (trivial) module, it defines a lattice. So, for any set S of vertices, it is possible to use a closure operator to compute the smallest module which contains S. Algorithm 1 adds all vertices which distinguish respectively X and Y and the same process is repeated until no more vertex can be added.
Usually, bimodules decomposition does not produce all possible modules, but an inclusion tree such that all possible bimodules can be deduced from this tree. The root represents the whole graph and the leaves are vertices (trivial Input: (O; A; I) a bipartite graph, (X; Y ) ⊂ (O; A) Output: (Xc; Yc), smallest bimodule containing (X; Y ) begin continue ← true; (Xc; Yc) ← (X; Y ); while continue do continue ← f alse; forall the x ∈ J\Xc do if x distinguishes Yc then
Xc ← Xc ∪ x; continue ← true; end end forall the y ∈ M \Yc do if y distinguishes Xc then
Yc ← Yc ∪ y;
continue ← true;
end
end
end
return (Xc; Yc)
end
Algorithm 1: Computation of the smallest bimodule which contains (X; Y )
bimodules). It follows that the size of the tree is O(n), with n = |O| + |A|. In
[
In Fig. 6, an example of bimodule is shown on the “Living Beings and Water”
concept lattice [
First, we have seen that modules defined on a lattice have natural links with bimodules of the bipartite graph (context) of this lattice. Modules of a lattice can be used the same way as modules of a graph are used: to produce a quotient lattice, which is a simplification of the original one. Recursive definition of modules allows to consider several details levels in the lattice.
All results in modular decomposition may be transposed immediatly to concept lattice and associated context to improve the readibility of the lattice. 4 i 4 i 3 2 1 12 c c (b) (c) b b e
7
e
7
d
8
d
8
6
f
6
f
5
5
Fig. 6. (a) “Living Beings and Water ” Context [
Second, investigation of bimodules properties shows that a bimodule may not correspond to a module of the lattice. Nevertheless, it remains possible to use it to produce a simplification of the original lattice. In such a case, the bimodule is collapsed in two elements a and b which represent ∨-irreducible elements and ∧-irreducible elements of the bimodule.
This last case is a particular case of another decomposition proposed for
inheritance hierarchies [