定义1^{[1, 2]} 称(U, A, I)为一个形式背景, 其中:

$ U=\left\{x_{1}, x_{2}, \cdots, x_{n}\right\}$

为对象集, 每个x_i(i≤ n)表示一个对象;

$ A=\left\{a_{1}, a_{2}, \cdots, a_{m}\right\}$

为属性集, 每个a_j(j≤ m)表示一个属性; I为U和A之间的二元关系, I⊆U× A.若(x, a)∈ I, 则表示对象x具有属性a, 记为xIa; 若(x, a)∉I, 则表示对象x不具有属性a.

设(U, A, I)为一个形式背景, 在对象子集X⊆U和属性子集B⊆A上分别定义概念诱导算子* 如下:

$ \begin{array}{l} X^{* }=\{a \mid a \in A, \forall x \in X, (x, a) \in I\}, \\ B^{* }=\{x \mid x \in U, \forall a \in B, (x, a) \in I\}, \end{array}$

其中, X^* 表示集合X中所有对象共同具有的属性集合, B^* 表示共同具有集合B中所有属性的对象集合.

设(U, A, I)为一个形式背景, X⊆U, B⊆A.如果二元组(X, B)满足X^* =B, X=B^* , 则称(X, B)为一个形式概念, 简称概念, 其中, X表示概念的外延, B表示概念的内涵.记L(U, A, I)为形式背景(U, A, I)中所有概念的集合.

定义2^[19] 设(U, A, I)为一个形式背景, X⊆U, B⊆A.如果二元组(X, B)满足X^* =B, X=B^* 且X=B, 则称(X, B)为一个等势概念, 其中, X表示等势概念的外延, B表示等势概念的内涵.记EL(U, A, I)为形式背景(U, A, I)中所有等势概念的集合.

定义3^{[1, 2]} 设(U, A, I)为一个形式背景, H⊆U, N⊆A.记

$ I_{H \times N}=I \cap(H \times N) \text {, }$

称(H, N, I_{H× N})为(U, A, I)的子背景.

在子背景(H, N, I_{H× N})中, ∀ Y⊆H, C⊆N, 将概念诱导算子* 记为Y^{* N}, C^{* H}.事实上, 由* 算子的定义可知

Y^{* N}=Y^* ∩ N, C^{* H}=C^* ∩ H.

图通常表示为一个二元对G=(V, E), 其中, V表示图G中顶点的集合, E表示图G中边的集合.对于图G的两个顶点v_i∈ V, v_j∈ V, 若v_i、v_j之间存在一条边, 则表示为< v_i, v_j> ∈ E.对于图G的任意非空顶点子集V₁⊂V, 称以V₁为顶点集, 以G中两个端点都在V₁中、边为其边集的图为V₁的导出子图, 记为G[V₁].

定义4^[22] 设G=(V, E)为一个图, 称图G为连通的当且仅当对于图G的任意两个顶点v_i∈ V, v_j∈ V, 从顶点v_i出发, 经过若干个中间顶点, 能到达顶点v_j.特别地, 若对于任意的x_i∈ V, x_j∈ V, 都有< x_i, x_j> ∈ E, 则称图G为完全连通图.

网络是由节点和连接这些节点的线组成的系统, 这些节点表示顶点, 线表示边, 通常表示为图G=(V, E).对于一个简单无向图G, 定义修正邻接矩阵M=(m_ij)如下^[20]:

$ m_{i j}=\left\{\begin{array}{ll} 1, & \left\langle v_{i}, v_{j}\right\rangle \in E, i \neq j \text { 或 } v_{i}=v_{j} \\ 0, & \text { 其它 } \end{array}\right.$

结合形式背景(U, A, I)和以对象集U为顶点集的图G=(U, E)的修正邻接矩阵, 所得的表格称为网络形式背景(也称为带对象结构信息形式背景).在网络形式背景中不仅包含对象与对象之间的信息, 同时也包含对象与属性之间的信息, 其详细定义

如下所示.

定义5^[17] 称四元组(U, A, M, I)为一个网络形式背景, 其中

U={x₁, x₂, …, x_n}

为对象集,

A= {a₁, a₂, …, a_m}

为属性集, M=(m_ij)为对象集U上的结构矩阵(即对象集对应的修正邻接矩阵); I为U和A之间的二元关系, 若(x, a)∈ I, 则表示对象x具有属性a, 记为xIa; 若(x, a)∉I, 则表示对象x不具有属性a.

定义6^[17] 设(U, A, M, I)为一个网络形式背景, X⊆U, X≠ Ø .若由集合X在结构矩阵M中诱导的子图G[X]是连通的, 则称X是连通的, 此时也称X为对象集U的连通子集.

在定义6中, 若X的导出子图G[X]是完全连通的, 则称X为U的完全连通子集.进一步地, 若不存在对象集U的完全连通子集Y, 使得X⊂Y, 此时称X为对象集U的极大完全连通子集.特别地, 单点集和二元连通子集都是U的完全连通子集.

定义7^[17] 设(U, A, M, I)为一个网络形式背景, X⊆U, B⊆A(X≠ Ø 且B≠ Ø ).

1)若X^* =B, X=B^* 且X是连通的, 则称(X, B)为全局网络形式概念.记N(U, A, M, I)为(U, A, M, I)的所有全局网络形式概念的集合.

2)若X^* =B, X为连通的且不存在x∈ B^* -X使得X∪ {x}连通, 则称(X, B)为局部网络形式概念.记N_L(U, A, M, I)为(U, A, M, I)的所有局部网络形式概念的集合.

由定义7可知, 若(X, B)为(U, A, M, I)的全局网络形式概念, 则(X, B)一定为(U, A, I)的概念, 也一定为(U, A, M, I)的局部网络形式概念, 即

N(U, A, M, I)⊆L(U, A, I), N(U, A, M, I)⊆NL₍U, A, M, I).

例1 图1为一个学术网络图, 每个顶点表示一个对象, 顶点旁边为该对象具有的属性信息, 边表示学者之间存在学术交流关系.

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 学术网络图Fig.1 Academic network graph

表1为图1对应的网络形式背景(U, A, M, I), 对象集

U={x₁, x₂, x₃, x₄, x₅, x₆},

表1

Table 1

表1(Table 1)

表1 网络形式背景(U, A, M, I) Table 1 Network formal context(U, A, M, I) x1 x2 x3 x4 x5 x6 a1 a2 a3 a4 a5 x1 × × × × × × × x2 × × × × × × × x3 × × × × × × x4 × × × × × x5 × × × × × × × × × x6 × × × × × × × × ×

表1 网络形式背景(U, A, M, I) Table 1 Network formal context(U, A, M, I)

属性集

A={a₁, a₂, a₃, a₄, a₅}.

在表1中, 形式背景(U, A, I)概念的集合为:

$ \begin{aligned} L(U, A, I)= & \left\{(\emptyset, A), \left(x_{1}, a_{2} a_{3} a_{5}\right), \left(x_{4} x_{5} x_{6}, a_{1} a_{4} a_{5}\right), \right. \\ & \left(x_{6}, a_{1} a_{2} a_{4} a_{5}\right), \left(x_{1} x_{3}, a_{2} a_{3}\right), \\ & \left(x_{1} x_{5}, a_{3} a_{5}\right), \left(x_{1} x_{6}, a_{2} a_{5}\right), \\ & \left(x_{2} x_{6}, a_{1} a_{2} a_{4}\right), \left(x_{1} x_{2} x_{3} x_{6}, a_{2}\right), \\ & \left(x_{2} x_{4} x_{5} x_{6}, a_{1} a_{4}\right), \left(x_{5}, a_{1} a_{3} a_{4} a_{5}\right), \\ & \left.\left(x_{1} x_{3} x_{5}, a_{3}\right), \left(x_{1} x_{4} x_{5} x_{6}, a_{5}\right), (U, \emptyset)\right\} . \end{aligned}$

全局网络形式概念的集合为:

$ \begin{aligned} N(U, A, M, I)= & \left\{\left(x_{6}, a_{1} a_{2} a_{4} a_{5}\right), \left(x_{2} x_{4} x_{5} x_{6}, a_{1} a_{4}\right), \right. \\ & \left(x_{1}, a_{2} a_{3} a_{5}\right), \left(x_{5}, a_{1} a_{3} a_{4} a_{5}\right), \\ & \left(x_{1} x_{3}, a_{2} a_{3}\right), \left(x_{2} x_{6}, a_{1} a_{2} a_{4}\right), \\ & \left(x_{1} x_{5}, a_{3} a_{5}\right), \left(x_{1} x_{6}, a_{2} a_{5}\right), \\ & \left.\left(x_{1} x_{3} x_{5}, a_{3}\right), \left(x_{1} x_{2} x_{3} x_{6}, a_{2}\right)\right\} . \end{aligned}$

局部网络形式概念的集合为:

$ \begin{array}{l} N_{L}(U, A, M, I)=N(U, A, M, I) \cup \\ \quad\left\{\left(x_{5} x_{6}, a_{1} a_{4} a_{5}\right), \left(x_{4}, a_{1} a_{4} a_{5}\right), \left(x_{1} x_{5} x_{6}, a_{5}\right)\right\} . \end{array}$

根据全局网络形式概念的定义可知, 要获取该类网络形式概念, 在(U, A, I)的概念已知的条件下, 只需判定(U, A, I)中概念外延是否为连通集即可.而由引理1可知, 由(U, U, R)的等势概念可直接获取所有的完全连通子集.因此, 基于(U, U, R)中概念, 可得如下定理.

定理3 设(U, A, R, I)为一个网络形式背景, L(U, U, R)为(U, U, R)的概念集合.对于任意的(X, B)∈ L(U, A, I)(X≠ Ø 且B≠ Ø ), 下列结论成立:

1)若存在(Y, C)∈ L(U, U, R), 有Y=C且X⊆Y, 则(X, B)为全局网络形式概念;

2)若存在(Y, C)∈ L(U, U, R), 有Y∩ C≠ Ø , 且X=Y或X=C, 则(X, B)为全局网络形式概念.

证明 先证1).若存在(Y, C)∈ L(U, U, R), 使得Y=C, 则Y为U的极大完全连通子集.又因为X⊆Y, 由引理1可得, X为U的完全连通子集, 故(X, B)∈ L(U, A, I)为全局网络形式概念.

再证2).因为(Y, C)∈ L(U, U, R), 故可知∀ x∈ Y, ∀ y∈ C, 都有(x, y)∈ R.而由Y∩ C≠ Ø 可知, 一定存在z∈ Y∩ C, 即z∈ Y且z∈ C.因为z∈ C, 所以由概念的定义可知, ∀ x_i∈ Y, x_j∈ Y, 有(x_i, z)∈ R且(x_j, z)∈ R; 而z∈ Y, 所以x_i可经过z到达x_j, 进而由x_i、x_j的任意性可知, Y为U的连通子集, 同理可得, C为U的连通子集.因此可证, 当X=Y或X=C时, (X, B)∈ L(U, A, I)为全局网络形式概念.

定理3说明可从形式背景(U, U, R)中的概念得到一部分全局网络形式概念.为了进一步借助(U, U, R)中的等势概念给出获取所有全局网络形式概念的方法, 下面给出由(U, U, R)的等势概念获取其子背景(X, X, R_X)(X⊆U, R_X=R∩ (X× X))等势概念的方法.此前, 对于特定集合{(X, X)|X⊆U}, 本文规定其中任意两个元素之间的偏序关系为

(X₁, X₁)≤ (X₂, X₂) ⇔ X₁⊆X₂.

引理2 设(U, A, R, I)为一个网络形式背景, EL(U, U, R)为(U, U, R)的等势概念集合.对∀ X⊆U, 记

B={(X∩ X_i, X∩ B_i)|(X_i, B_i)∈ EL(U, U, R)},

则有

EL(X, X, R_X)=max B,

其中max B为偏序集(B, ≤ )的所有极大元的集合.

证明 第一步证明EL(X, X, R_X)⊆max B.对∀ (Y, C)∈ EL(X, X, R_X), 首先证明(Y, C)∈ B.由(Y, C)∈ EL(X, X, R_X)可知, Y=C且Y⊆X为X的极大完全连通子集.进一步有Y为U的完全连通子集, 故存在U的一个极大完全连通子集X_i, 满足Y⊆X_i且

(X_i, B_i)∈ EL(U, U, R),

因此Y⊆X∩ X_i且X∩ X_i⊆X_i为X的完全连通子集.又因为Y为X的极大完全连通子集, 因此

Y=X∩ X_i,

进而有

C=X∩ B_i,

即∀ (Y, C)∈ EL(X, X, R_X), 存在(X_i, B_i)∈ EL(U, U, R), 使得

(Y, C)=(X∩ X_i, X∩ B_i)∈ B.

其次证明(Y, C)∈ max B.假设存在

(X∩ X_j, X∩ B_j)∈ B,

有

(Y, C)≤ (X∩ X_j, X∩ B_j),

即Y⊆X∩ X_j, 又因为Y为X的极大完全连通子集, 所以

Y=X∩ X_j,

因此(Y, C)∈ max B.故EL(X, X, R_X)⊆max B.

第二步证明max B⊆EL(X, X, R_X), 即证

∀ (X∩ X_i, X∩ B_i)∈ max B,

有(X∩ X_i, X∩ B_i)∈ L(X, X, R_X)且

X∩ X_i=X∩ B_i.

对于任意的(X∩ X_i, X∩ B_i)∈ max B, 由B的定义可知(X_i, B_i)∈ EL(U, U, R), 所以(X_i, B_i)∈ L(U, U, R), X_i=B_i且X_i× B_i⊆R.因为

(X∩ X_i)⊆X_i, (X∩ B_i)⊆B_i,

所以

(X∩ X_i)× (X∩ B_i)⊆R.

又因为

(X∩ X_i)⊆X, (X∩ B_i)⊆X,

故

(X∩ X_i)× (X∩ B_i)⊆X× X,

于是有

(X∩ X_i)× (X∩ B_i)⊆R∩ (X× X)=R_X,

从而根据概念诱导算子'的性质可知

(X∩ X_i)⊆ (X⋂Bi)'X.

假设

(X∩ X_i)⊂ (X⋂Bi)'X,

即存在x∈ (X⋂Bi)'X且x∉X∩ X_i.由引理1可知X∩ B_i为X的完全连通子集.又x∈ (X⋂Bi)'X, 由性质1可得(X∩ B_i)∪ {x}为X的完全连通子集.进一步可知(X∩ B_i)∪ {x}为U的完全连通子集, 所以一定存在(X_j, B_j)∈ EL(U, U, R), 使得

(X∩ B_i)∪ {x}⊆B_j .

又因为

(X∩ B_i)∪ {x}⊆X,

所以

(X∩ B_i)∪ {x}⊆X∩ B_j,

进而有

X∩ B_i⊂(X∩ B_i)∪ {x}⊆X∩ B_j,

即存在一个(X∩ X_j, X∩ B_j)∈ B, 使得

X∩ B_i⊂X∩ B_j,

与

(X∩ X_i, X∩ B_i)∈ max B

矛盾.因此,

X∩ X_i= (X⋂Bi)'X.

同理可得

(X⋂Xi)'X=X∩ B_i,

所以

(X∩ X_i, X∩ B_i)∈ L(X, X, R_X).

又因为X_i=B_i, 所以

X∩ X_i=X∩ B_i.

综上可得

(X∩ X_i, X∩ B_i)∈ EL(X, X, R_X),

进而有

max B⊆EL(X, X, R_X).

例3 针对表1的网络形式背景, 取对象子集

X={x₁, x₂, x₃, x₅},

根据定义3, 可得X在形式背景(U, U, R)中对应的子背景(X, X, R_X), 具体如表2所示.

表2

Table 2

表2(Table 2)

表2 子背景(X, X, RX) Table 2 A subcontext (X, X, RX) x1 x2 x3 x5 x1 × × × x2 × × x3 × × × x5 × × × ×

表2 子背景(X, X, RX) Table 2 A subcontext (X, X, RX)

一方面, 由定义2, 根据概念诱导算子可得

EL(X, X, R_X)={(x₂x₅, x₂x₅), (x₁x₃x₅, x₁x₃x₅)}.

另一方面, 根据引理2 与例2可得

B={(x₂x₅, x₂x₅), (x₂, x₂), (x₁x₃x₅, x₁x₃x₅)},

进而有

max B={(x₂x₅, x₂x₅), (x₁x₃x₅, x₁x₃x₅)}.

于是可得

EL(X, X, R_X)=max B.

借鉴定理1的思路, 结合引理2, 可得由子背景的等势概念获取全局网络概念的方法.

定理4 设(U, A, R, I)为一个网络形式背景, EL(X, X, R_X)为子背景(X, X, R_X)的等势概念的集合.对任意的(X, B)∈ L(U, A, I)(X≠ Ø 且B≠ Ø ), 记M₀, M₁, …, MX-1为X的一个子集族序列, 其中

M₀={ Yi0|( Yi0, Ci0)∈ EL(X, X, R_X)},

M₁=

{ Yi1=∪ { Yj0| Yi0∩ Yj0≠ Ø , ∀ Yj0∈ M₀}|∀ Yi0∈ M₀},

︙

MX-1={ YiX-1=∪ { YjX-2| YiX-2∩ YjX-2≠ Ø ,

∀ YjX-2∈ MX-2}|∀ YiX-2∈ MX-2}.

则如下结论成立:

1)若存在0≤ k≤ |X|-1, 有|M_k|=1, 则(X, B)为全局网络形式概念;

2)若存在0≤ k≤ |X|-1, 有M_k-1=M_k且|M_k|≥ 2, 则(X, B)不是全局网络形式概念.

证明 由M_k的构造方法及连通图的分解性易知, M_k(0≤ k≤ |X|-1)中的元素都是X的连通子集, 对于任意的X⊆U(X≠ Ø ), X要么为U的连通子集, 要么为U的非连通子集.由M₀的有限性可知, 一定存在一个0≤ k≤ X-1, 使得 Mk=1, 或者M_k=M_k+1且 Mk+1≥ 2.

先证1).当 Mk=1时, 显然有M_k={X}.因此可知X是连通的, 进而可证(X, B)为全局网络形式概念.

2)当M_k=M_k+1且 Mk+1≥ 2时, 由M_k(0≤ k≤ X-1)的定义可知

M_k=M_k+1=…= MX-1,

且

Mk= Mk+1= Mk+2=…= MX-1≥ 2.

不失一般性, 设

M_k={Y₁, Y₂, …, Y_t}, t≥ 2,

则显然有

⋃i=1tY_i=X.

由M_k=M_k+1可知, ∀ Y_i∈ M_k, Y_j∈ M_k, Y_i≠ Y_j, 都有

Y_i∩ Y_j=Ø .

进一步地, 假设存在y_i∈ Y_i, y_j∈ X-Y_i, 使得(y_i, y_j)∈ R_X, 则{y_i, y_j}为X的完全连通子集, 进而存在Y_k∈ M_k, 使得{y_i, y_j}⊆Y_k.若Y_i=Y_k, 则y_j∈ Y_i, 这样存在矛盾.若Y_i≠ Y_k, 则Y_i∩ Y_k≠ Ø , 这样也存在矛盾.因此, ∀ y_i∈ Y_i, y_j∈ X-Y_i, 都有(y_i, y_j)∉R_X.由y_i、y_j的任意性可知, y_i不能经过若干顶点到达y_j, 所以X是不连通的, 进而可证(X, B)不是全局网络形式概念.

基于定理3和定理4, 下面给出从网络形式背景(U, A, R, I)出发获取全局网络形式概念的步骤.

1)计算L(U, A, I)和L(U, U, R).

2)对于任意的(X, B)∈ L(U, A, I)(X≠ Ø 且B≠ Ø ), 利用定理3判断其是否为全局网络形式概念, 并将由此得到的全局网络形式概念的集合记为N₁(U, A, R, I).

3)∀ (X, B)∈ L(U, A, I)-N₁(U, A, R, I)(X≠ Ø 且B≠ Ø ), 首先根据引理2获取子背景(X, X, R_X)的等势概念, 其次计算X的子集族序列

{M_k 0≤k≤X-1},

最后根据定理4判断(X, B)是否为全局网络形式概念.

在3)中, 集合连通性的判定算法如下所示.

算法2 对象子集X的连通性判别

输入 EL(U, U, R), 线索集X

输出 True or False

初始化 M₀=Ø

根据引理2计算EL(X, X, R_X)

M₀=EL_X(X, X, R_X)

If |M₀|=1

返回True

Break

Else

k=1∶ |X|-1, M_k=Ø

For Yik-1in M_k-1

A_i=Ø

For Yjk-1in M_k-1

If Yik-1∩ Yjk-1≠ Ø

A_i← A_i∪ Yjk-1

M_k← M_k∪ {A_i}

End if

End for

End for

End if

If |M_k|=1

返回True

Break

End if

If M_k-1=M_k(k≥ 1)且 |M_k|≥ 2

返回False

Break

End if

算法2的时间复杂度为O(|X|m+|X|m²), 空间复杂度为O(|X|m), 其中m=|EL(U, U, R)|.

例4 继续以表1的网络形式背景为例进行分析, 基于等势概念的获取全局网络形式概念的详细过程如下.

1)由例1和例2可得表1的L(U, A, I)和L(U, U, R).

2)根据定理3中1)可得

(x₁, a₂a₃a₅)∈ N(U, A, R, I), (x5_, a1_a3_a4_a5₎∈ N(U, A, R, I), (x6, _a1a₂a₄a₅)_∈ N(U, A, R, I), (x1x3_, a₂a3₎∈ _N(U, A, R, I), (x1x5, _a3_a5)_∈ N₍U, A, R, I), (x1x6, a₂a₅)∈ _N(_U, A, R, I), (x2x6, a1_a2_a4)_∈ N₍U_, A, R, I), (x1x3x5, a₃)_∈ N₍U, _A, R, I).

对于

(x₂x₄x₅x₆, a₁a₄)∈ L(U, A, I),

因为存在

(x₂x₄x₅x₆, x₂)∈ L(U, U, R),

且

{x₂, x₄, x₅, x₆}∩ {x₂}≠ Ø ,

所以根据定理3中2)可知

(x₂x₄x₅x₆, a₁a₄)∈ N(U, A, R, I).

于是, 可得

$ \begin{aligned} N_{1}(U, A, R, I)= & \left\{\left(x_{1}, a_{2} a_{3} a_{5}\right), \left(x_{5}, a_{1} a_{3} a_{4} a_{5}\right), \right. \\ & \left(x_{1} x_{3}, a_{2} a_{3}\right), \left(x_{6}, a_{1} a_{2} a_{4} a_{5}\right), \\ & \left(x_{1} x_{5}, a_{3} a_{5}\right), \left(x_{1} x_{6}, a_{2} a_{5}\right), \\ & \left(x_{2} x_{6}, a_{1} a_{2} a_{4}\right), \left(x_{1} x_{3} x_{5}, a_{3}\right), \\ & \left.\left(x_{2} x_{4} x_{5} x_{6}, a_{1} a_{4}\right)\right\} . \end{aligned} $

3)由1)、2)可得

$ \begin{array}{l} L(U, A, I)-N_{1}(U, A, R, I)-\{(U, \emptyset), (\emptyset, A)\}= \\ \quad\left\{\left(x_{1} x_{2} x_{3} x_{6}, a_{2}\right), \left(x_{4} x_{5} x_{6}, a_{1} a_{4} a_{5}\right), \left(x_{1} x_{4} x_{5} x_{6}, a_{5}\right)\right\} . \end{array} $

对于概念(x₁x₂x₃x₆, a₂), 令

X₁={x₁, x₂, x₃, x₆}.

由例2和引理2知

EL(X₁, X₁, RX1)={(x₂x₆, x₂x₆), (x₁x₃x₆, x₁x₃x₆)},

进而可得

M₀={{x₂, x₆}, {x₁, x₃, x₆}}.

根据定理4可得

M₁={{x₁, x₂, x₃, x₆}},

此时 M1=1, 所以

(x₁x₂x₃x₆, a₂)∈ N(U, A, R, I).

类似于上述过程, 对于概念(x₄x₅x₆, a₁a₄a₅), 令

X₂={x₄, x₅, x₆}.

首先, 由例2和引理2可知

EL(X₂, X₂, RX2)={(x₄, x₄), (x₅x₆, x₅x₆)},

于是

M₀={{x₄}, {x₅, x₆}}.

又根据定理4可得

M₁={{x₄}, {x₅, x₆}},

此时M₀=M₁, M1≥ 2, 所以

(x₄x₅x₆, a₁a₄a₅)∉N(U, A, R, I).

同理, 对于概念(x₁x₄x₅x₆, a₅), 可得

(x₁x₄x₅x₆, a₅)∉N(U, A, R, I).

综上所述, 网络形式背景(U, A, R, I)的全局网络形式概念如下:

$ \begin{array}{l} \left(x_{1}, a_{2} a_{3} a_{5}\right), \left(x_{5}, a_{1} a_{3} a_{4} a_{5}\right), \left(x_{6}, a_{1} a_{2} a_{4} a_{5}\right), \\ \left(x_{1} x_{3}, a_{2} a_{3}\right), \left(x_{1} x_{5}, a_{3} a_{5}\right), \left(x_{1} x_{6}, a_{2} a_{5}\right), \\ \left(x_{2} x_{6}, a_{1} a_{2} a_{4}\right), \left(x_{1} x_{3} x_{5}, a_{3}\right), \left(x_{1} x_{2} x_{3} x_{6}, a_{2}\right), \\ \left(x_{2} x_{4} x_{5} x_{6}, a_{1} a_{4}\right) . \end{array} $

该结论与例1一致.

根据局部网络形式概念的定义, 基于性质2, 给出局部网络形式概念的一个等价描述.

定理5 设(U, A, R, I)为一个网络形式背景, X⊆U(X≠ Ø )为对象集U的连通子集.若X^* ≠ Ø 且

$ \left(X^{* * }-X\right) \cap\left(\cup_{x_{i} \in X} x_{i}^{\prime}-X\right)=\emptyset, $

则(X, X^* )为局部网络形式概念.

证明 由

$ \left(X^{* * }-X\right) \cap\left(\cup_{x_{i} \in X} x_{i}^{\prime}-X\right)=\emptyset $

可知, ∀ x∈ X^{* *} -X, 都有

$ x \notin\left(\cup_{x_{i} \in X} x_{i}^{\prime}-X\right), $

所以∀ x_i∈ X, 都有x∉x'_i-X, 即(x, x_i)∉R, 因此x与X中的任意一个对象之间都不存在边, 故X∪ {x}是不连通的.于是, 根据定义7中2)可得, (X, X^* )为局部网络形式概念.

由于全局网络形式概念一定是局部网络形式概念, 并且由局部网络形式概念的定义可知, 获取局部网络形式概念的关键还是在于集合连通性的判别, 于是在定理5的基础上, 给出局部网络形式概念的获取方法.

定理6 设(U, A, R, I)为一个网络形式背景, L(U, U, R)为(U, U, R)的概念集合.对于任意的X⊆U(X≠ Ø 且X^* ≠ Ø ), 下列结论成立:

1)若存在(Y, C)∈ L(U, U, R), 有

Y=C, X⊆Y

且

$ \left(X^{* * }-X\right) \cap\left(\cup_{x_{i} \in X} x_{i}^{\prime}-X\right)=\emptyset \text {, } $

则(X, X^* )为局部网络形式概念;

2)若存在(Y, C)∈ L(U, U, R), 有Y∩ C≠ Ø , X=Y或X=C, 且

$ \left(X^{* * }-X\right) \cap\left(\cup_{x_{i} \in X} x_{i}^{\prime}-X\right)=\emptyset, $

则(X, X^* )为局部网络形式概念.

证明 由定理3和定理5易证.

定理7 设(U, A, R, I)为一个网络形式背景, EL(X, X, R_X)为子背景(X, X, R_X)的等势概念的集合.对∀ X⊆U(X≠ Ø 且X^* ≠ Ø ), 记M₀, M₁, …, MX-1为X的一个子集族序列, 其中

$ \begin{array}{l} M _{0}=\left\{Y_{i}^{0} \mid\left(Y_{i}^{0}, C_{i}^{0}\right) \in E L\left(X, X, R_{X}\right)\right\}, \\ M _{1}=\left\{Y_{i}^{1}=\cup\left\{Y_{j}^{0} \mid Y_{i}^{0} \cap Y_{j}^{0} \neq \emptyset, \forall Y_{j}^{0} \in M _{0}\right\} \mid\right. \\ \left.\quad \forall Y_{i}^{0} \in M _{0}\right\}, \\ \vdots \\ \stackrel{}M_{|X|-1}=\left\{Y_{i}^{|X|-1}=\cup\left\{Y_{j}^{|X|-2} \mid Y_{i}^{|X|-2} \cap Y_{j}^{|X|-2} \neq \emptyset, \right.\right. \\ \left.\left.\quad \forall Y_{j}^{|X|-2} \in M _{|X|-2}\right\} \mid \forall Y_{i}^{|X|-2} \in m_{|X|-2}\right\}, \end{array} $

若存在0≤ k≤ X-1, 有 Mk=1, 且

$ \left(X^{* * }-X\right) \cap\left(\cup_{x_{i} \in X} x_{i}^{\prime}-X\right)=\emptyset, $

则(X, X^* )为局部网络形式概念.

证明 由定理4和定理5易证.

基于定理6和定理7, 下面给出从网络形式背景(U, A, R, I)出发获取局部网络形式概念的步骤.

1)计算L(U, U, R).

2)对于任意的X⊆U(X≠ Ø 且X^* ≠ Ø ), 利用定理6判断(X, X^* )是否为局部网络形式概念, 并将由此得到的局部网络形式概念的集合记为 NL1(U, A, R, I).

3)对于其余对象子集X⊆U(X≠ Ø 且X^* ≠ Ø ), 首先根据引理2获取子背景(X, X, R_X)的等势概念, 其次计算X的子集族序列

{M_k|0≤ k≤ |X|-1},

最后根据定理7判断(X, X^* )是否为局部网络形式概念.

例5 以表1的网络形式背景为例, 基于等势概念的局部网络形式概念获取过程具体如下.

由定义7可知N(U, A, R, I)⊆N_L(U, A, R, I), 所以由例4可知

$ \begin{array}{l} \left(x_{1}, a_{2} a_{3} a_{5}\right) \in N_{L}(U, A, R, I), \\ \left(x_{5}, a_{1} a_{3} a_{4} a_{5}\right) \in N_{L}(U, A, R, I), \\ \left(x_{6}, a_{1} a_{2} a_{4} a_{5}\right) \in N_{L}(U, A, R, I), \\ \left(x_{1} x_{3}, a_{2} a_{3}\right) \in N_{L}(U, A, R, I), \\ \left(x_{1} x_{5}, a_{3} a_{5}\right) \in N_{L}(U, A, R, I), \\ \left(x_{1} x_{6}, a_{2} a_{5}\right) \in N_{L}(U, A, R, I), \\ \left(x_{2} x_{6}, a_{1} a_{2} a_{4}\right) \in N_{L}(U, A, R, I), \\ \left(x_{1} x_{3} x_{5}, a_{3}\right) \in N_{L}(U, A, R, I), \\ \left(x_{1} x_{2} x_{3} x_{6}, a_{2}\right) \in N_{L}(U, A, R, I), \\ \left(x_{2} x_{4} x_{5} x_{6}, a_{1} a_{4}\right) \in N_{L}(U, A, R, I) . \end{array} $

下面考虑其它对象子集.

对于集合X₁={x₃, x₆}, 由例2可知

(x₁x₃x₅x₆, x₁x₃x₅x₆)∈ EL(U, U, R),

于是由引理1可得X₁是连通的, 进一步有

X1*={a₂}, X1* *={x₁, x₂, x₃, x₆},

所以

X1* *-X₁={x₁, x₂}.

又因为

∪x∈X1x'-X₁={x₁, x₂, x₃, x₅, x₆}-{x₃, x₆}= {x1_, x2_, x5_},

由此可得

$ \left(X_{1}^{* * }-X_{1}\right) \cap\left(\cup_{x \in X_{1}} x^{\prime}-X_{1}\right)=\left\{x_{1}, x_{2}\right\} \neq \varnothing, $

所以根据定理5可得

(x₃x₆, a₂)∉N_L(U, A, R, I).

对于集合X₂={x₁, x₅, x₆}, 由例2可知

(x₁x₃x₅x₆, x₁x₃x₅x₆)∈ EL(U, U, R),

于是由引理1可得, X₂是连通的, 进一步有

$ \begin{array}{l} X_{2}^{* }=\left\{a_{5}\right\}, \\ X_{2}^{* * }=\left\{x_{1}, x_{4}, x_{5}, x_{6}\right\}, \end{array} $

所以

X2* *-X₂={x₄}.

又因为

$ \begin{aligned} \cup_{x_{i} \in X} x_{i}^{\prime}-X= & \left\{x_{1}, x_{2}, x_{3}, x_{5}, x_{6}\right\}-\left\{x_{1}, x_{5}, x_{6}\right\}= \\ & \left\{x_{2}, x_{3}\right\}, \end{aligned} $

由此可得

$ \left(X_{2}^{* * }-X_{2}\right) \cap\left(\cup_{x \in X_{2}} x^{\prime}-X_{2}\right)=\emptyset, $

所以根据定理5可得

(x₁x₅x₆, a₅)∈ N_L(U, A, R, I).

同理可得

(x₄, a₁a₄a₅)∈ N_L(U, A, R, I), (x5_x6_, a1_a4_a5₎∈ NL₍U, A, R, I).

综上所述, 网络形式背景(U, A, R, I)的局部网络形式概念如下:

$ \begin{array}{l} \left(x_{1}, a_{2} a_{3} a_{5}\right), \left(x_{5}, a_{1} a_{3} a_{4} a_{5}\right), \left(x_{6}, a_{1} a_{2} a_{4} a_{5}\right), \\ \left(x_{1} x_{3}, a_{2} a_{3}\right), \left(x_{1} x_{5}, a_{3} a_{5}\right), \left(x_{1} x_{6}, a_{2} a_{5}\right), \\ \left(x_{2} x_{6}, a_{1} a_{2} a_{4}\right), \left(x_{1} x_{3} x_{5}, a_{3}\right), \left(x_{1} x_{2} x_{3} x_{6}, a_{2}\right), \\ \left(x_{2} x_{4} x_{5} x_{6}, a_{1} a_{4}\right), \left(x_{1} x_{5} x_{6}, a_{5}\right), \left(x_{4}, a_{1} a_{4} a_{5}\right), \\ \left(x_{5} x_{6}, a_{1} a_{4} a_{5}\right) . \end{array} $

该结论与例1一致.