## 4 Concept Stability Calculation Based on Maximal Non-Generator
### Extracting Maximal Non-Generator  
Summarize the preceding part of this section, we have known that the stability of \((A,B)\) can be calculated by linking it to maximal non-generator. Now, how to obtain all maximal non-generators of \((A,B)\) is becoming important. The brute force method of traversing all subsets of \(A\) and checking whether Definition 3 is satisfied undoubtedly wastes computing resources. Interestingly, we have found the equivalence between maximal non-generator of \(A\) and the lower neighbor concept of \((A,B)\). This equivalence makes it sufficient to calculate the concept stability by only exploring its lower neighbor concepts, which greatly improves scalability and reduces computational complexity. The equivalence theorem is given below:  
**Theorem 2**. : _Given a formal context \(K=(G,M,I)\) and a concept \((A,B)\) of \(K\). The maximal non-generators of \(A\) is equivalent to the lower neighbor concepts of \((A,B)\)._  
Proof. : In order to prove the equivalence of lower neighbor concept and maximal non-generator, we need to prove from two directions: (1) Suppose \(X\) is a maximal non-generator of \(A\), then it can form a lower neighbor concept \((X,f(X))\) of \((A,B)\). (2) If \((X,Y)\) is a lower neighbor concept of \((A,B)\), then \(X\) is a maximal non-generator of \(A\). (1) Since \(X\) is a maximal non-generator of \(A\), then \(X\subset A\Leftrightarrow f(A)\subset f(X)\Leftrightarrow g(f(X))\subset A\). In addition, \(X\subseteq g(f(X))\), thus we can get \(X\subseteq g(f(X))\subset A\). However, \(X\) is a subset of \(g(f(X))\) could never hold, otherwise \(X\) could not be maximal. Thus, \(X=g(f(X))\), it means that there exists a lower neighbor concept (X, f(X)) of (A, B). (2) Since \((X,Y)\) is a lower neighbor concept of \((A,B)\), then \(B\subset Y,X\subset A,f(X)=Y\). So \(X\) is a non-generator of \(A\). Suppose \(X\) is not maximal, there exists a maximal non-generator \(\vec{X}\supset X\) of \(A\). From (1), there should exist a concept \((\vec{X},f(\vec{X}))\). This conclusion contradicts the initial conditions. Thus, \(X\) is a maximal non-generator of \(A\). Based on the proved the equivalence of lower neighbor concept and maximal non-generator, we can directly obtain the maximal non-generator form the existing concept lattice. For example, as shown in Figure 3, calculating the maximal non-generators of \(\{(1,2,3),(a,b)\}\) only needs to directly explore its lower neighbor concepts \(\{(1,2),(a,b,e)\}\) and \(\{(3),(a,b,c)\}\). Next, on the basis of Theorem 1, the core theorem is proposed as follows. It uses the inclusion-exclusion principle and the lower neighbor concept of \((A,B)\) that represents maximal non-generator of \(A\) to calculate concept stability. The core theorem is as follows:  
**Theorem 3**. : _Let \(K=(G,M,I)\) be a formal context and a formal concept \((A,B)\) of \(K\). If all neighbor concepts of \((A,B)\) are \(\{(A_{1},B_{1}),(A_{2},B_{2})\ldots(A_{n},B_{n})\}\), then_  
\[\sigma\left(A,B\right)=1-\left(\sum_{i=1}^{n}2^{|A_{i}|}-\sum_{1\leq i<j\leq n }2^{|A_{i}\cap A_{j}|}\ +\cdots+(-1)^{n-1}\,2^{|A_{1}\bigcap A_{2}\cap\cdots\cap A_{n}|}\right) \left(2^{|A|}\right)^{-1} \tag{5}\]  
Figure 3: Explored lower neighbor concepts for computing the stability of \(\{(1,2,3),(a,b)\}\). **Proof. ** According to the Theorem 2, all lower neighbor concepts of \((A,B)\) are its maximal non-generators. Then, Equation (5) can be naturally derived from Theorem 1. \(\qed\)  
**Corollary 3**: _Let \(K=(G,M,I)\) be a formal context and a formal concept \((A,B)\) of \(K\). If the lower neighbor concept of \((A,B)\) is the bottom concept, the stability of \((A,B)\) is equal to \(\frac{2^{|A|}-1}{2^{|A|}}\)._  
**Proof. ** The extent of the bottom concept is an empty set. So the maximal non-generator is an empty set means only one empty set in the powerset of \(A\) is a non-generator. Thus, the stability of \((A,B)\) is equal to \(\frac{2^{|A|}-1}{2^{|A|}}\).