基于顶点依赖连接的下界枚举极大τ−isolated团

定义：

j-core:

j-core 是图论中的一个概念，用于表示图中某个连通度较高的顶点子集。给定一个图$G=(V,E)$，其顶点集$V$的$j-core$是这样一个顶点子集，其中每个顶点在该子集内的度数至少为 j。核心思想是通过移除不满足最低度数要求的顶点，保留满足要求的顶点子集。

常规j-core：

如果顶点集$X⊆V$中的每个顶点$v$满足$degX(v)≥j$，则称$X$是$j-core$。

特点：

可变j-core：

可变 j-core 允许每个顶点$v$的最低度数要求不同，即每个顶点的要求不是一个常数$j$，而是一个函数$j(v)$，为每个顶点赋予一个独立的最低度数要求。这个扩展使得算法可以根据每个顶点的特性灵活调整连通性要求。

特点：

τ隔离因子：

物理意义：越大越孤立

在下界策略中的运用：
具体下界策略：

极大孤立团（Maximal Isolated Cliques）：

定义：

完全连通：该顶点集是一个团（即顶点集中的每两个顶点之间都有边相连）。
τ-孤立性：该顶点集满足一定的孤立性要求，即每个顶点v在该团中的连通度至少为$τ×deg(v)$，其中$τ$是一个范围在$0<τ≤0$的隔离因子。

枚举图中所有的最大孤立团MIC

核心思想是通过深度优先搜索（DFS）并结合剪枝策略来有效地生成满足$τ$-隔离性的最大团。

问题定义

给定一个无向图$G=(V,E)$，其中$V$是顶点集，$E$是边集，目标是枚举所有满足以下条件的最大$τ$-孤立团：

团（clique）：该顶点集中的任意两个顶点都有边相连。
$τ$-隔离性：对于顶点集$X⊆V$中的任意顶点$v$，在集合$X$中的度数（即与其他顶点的连边数）满足$degX(v)≥j_τ(v)=τ×deg(v)$

主要概念

τ隔离因子：用于衡量顶点集合的孤立性，定义为$ 0<τ≤1$。越接近 1，要求的孤立性越强。
可变 j-core：用于定义每个顶点在团内的最低连通性要求，具体为$j_τ(v)=τ×deg(v)$，即顶点$v$在子集$X$中的度数应至少为其总度数的 τ 倍。
$corejτ$ 用于扩展过程中确保$τ$-隔离性; $corejK$ 用于伪候选剪枝过程中检测无效顶点
Cand :候选顶点集，它是是扩展当前团的初步候选集，包含所有可能用于扩展的顶点，即与$X$中所有顶点直接相连的顶点。是直接基于图结构计算出来的，在每一步扩展过程中，算法会使用 Cand 作为初始候选顶点集，再进一步通过$τ-core$操作筛选出满足$τ-$隔离性的顶点，生成 Ext。
$$NewCand = Cand ∩ Γ(v)$$
Ext :候选扩展顶点集，它是 Cand 经过筛选后的集合，仅保留满足$τ$-隔离性要求的顶点，用于确保扩展团$X$的候选顶点满足$τ$-隔离性。包含当前团$X$以继续扩展的所有顶点，即可能用于扩展当前团并继续构造 τ-孤立团的顶点。通过 corejτ(Xv ∪ Cand) 计算得出的最大 $τ$-隔离性顶点集。
$$Ext = corejτ(X’ ∪ Cand)$$
K候选集（K-candidate set）：是从 Ext 中提取的，表示那些在当前步骤中有可能继续扩展的顶点，结合了团结构的进一步筛选。$$ K ← Ext - X $$ 对于某个团$X$，K候选集是指可以用来扩展$X$ 的顶点集。扩展时需要判断这些顶点是否能满足$τ$-隔离性。K候选集与 Ext 的区别在于，K候选集是针对当前具体扩展步骤进一步筛选的可行扩展顶点集。
NL集：是 K候选集中的进一步筛选结果，用于避免重复枚举顶点。NL集 仅包含那些在排序上位于当前团最后一个顶点$tail(X)$之后的顶点，确保扩展是有序的。NL集用于防止重复扩展同一个团。$$NL(X)={v∈K(X)∣tail(X)≺v}$$

算法步骤

主函数

从空集开始，递归调用 Expand 函数扩展团，每次选择新的候选顶点，并检查扩展是否生成了一个满足$τ$-隔离性的最大孤立团。

procedure Main(G, τ):
[Input] G = (V, Γ): 无向图
τ: 隔离因子 (0 < τ ≤ 1)
[Output] 枚举所有最大τ-孤立团
begin
    Sort V in degree descending order;  // 根据顶点度数对顶点集排序，降序排列
    Expand(∅, V, V);  // 从空集开始扩展，初始候选集为全部顶点
end

扩展函数(dfs)

对于每个当前团，找到可以扩展的顶点，计算其扩展后的$τ$-core，并继续扩展直到无法继续扩展为止。

procedure Expand(X, Ext, Cand):
[Input] X: 当前团
Ext: 候选扩展顶点集
Cand: 候选顶点集
begin
  K ← Ext \ X;  // 计算K候选集（所有可以用来扩展的顶点）
  NL ← {v ∈ K | tail(X) ≺ v};  // 计算NL集，只扩展那些在顶点排序中位于团𝑋最后一个顶点之后的候选顶点
  // Fixpoint 剪枝
  //K = ∅ => X = Ext(X) => 扩展后的团与原团𝑋相同，说明已经找到了一个极大τ-孤立团
  if K = ∅ then  // 如果没有候选顶点，则当前团为最大孤立团
    Output X;  // 输出X作为fixpoint solution
    return;
  // NL 集剪枝：避免重复扩展同一个团，确保每次扩展都是按照一定顺序进行的
  if NL = ∅ then  // 如果没有可以扩展当前团的顶点
    if X is jτ-cored then  // 检查当前团是否满足jτ-core条件: 每个顶点在团𝑋中的度数必须达到其全局度数的𝜏倍
      if SolWithFalseCand(X, K) == true then  // 如果存在伪候选顶点
        Output X;  // 输出X为最大孤立团
      endif
    endif
    return;
  endif
  
  for each v ∈ NL do  // 遍历每个可以扩展的候选顶点
    Xv ← X ∪ {v} // // 将顶点 v 加入当前团，形成新的团 Xv
    NewCand ← Cand ∩ Γ(v);  // 更新初始候选集, 只保留与新团相连的顶点
    NewExt ← corejτ(Xv ∪ NewCand);  // 计算扩展集的corejτ，确保满足 τ-隔离性
    
    if Xv ⊆ NewExt then  // 如果扩展后的团Xv满足 τ-隔离性
      Expand(Xv, NewExt, NewCand);  // 递归扩展
    endif
  endfor
end

伪候选顶点检测（SolWithFalseCand）

当扩展团时，候选集$K$中有可能存在一些伪候选顶点，它们虽然可以扩展团，但不会生成满足$τ$-隔离性的团。此步骤用于检测并排除这些伪候选顶点，提前终止那些无法继续有效扩展的候选路径，减少无效扩展。

伪候选剪枝基于顶点的度数要求：对于每个候选顶点$x∈K(X)$，计算其在当前候选集中的最低度数要求
$$
jK(x) = \max ( 0, \tau \cdot \deg(x) - |X| )
$$如果某些候选顶点无法满足这个度数要求，它们被视为伪候选顶点。
伪候选顶点无法满足$τ$-隔离性要求，因此其加入只会破坏团的结构。
corejK(Q) 用来从$Q$中移除不满足最低度数要求$jK(x)$的顶点。如果某个最大团$Q$的$corejK(Q)$ 不为空，意味着存在有效的扩展，团$X$还可以继续扩展，因此$X$不是最大$τ$-孤立团

procedure SolWithFalseCand(X, K):
[Input] X: 当前团
K: 候选顶点集
[Output] 检查候选集𝐾中是否存在伪候选顶点
begin
  // 定义了每个候选顶点𝑥的最低度数要求
  Let jK be a function defined as
  jK(x) = max{0, τ · degG(x) − |X|} for each x ∈ K;  // 为K候选集中的顶点定义jK函数
  
  for each Q presented by MaxCliqueEnum(G[K]) do  // 遍历K候选集中的所有团Q
    // 伪候选剪枝：通过检测伪候选顶点，提前终止那些无法继续有效扩展的候选路径，减少无效扩展。
    if corejK(Q) != ∅ then  // 如果存在一个K候选集的core不为空
      return false;  // X不是最大孤立团(如果找到有效扩展，说明不是伪候选，继续扩展。)
    endif
  endfor
  return true;  // X是最大孤立团，并且含有伪候选顶点(当前团𝑋已经没有任何有效的候选顶点可以用于扩展，剩余的候选顶点（伪候选顶点）也无法生成符合条件的新团)
end

corejτ：扩展过程中，移除不满足τ-core条件的顶点

输入：D = $X’\cup NewCand$
度数计算：$\forall u\in X’\cup NewCand$, 计算$deg_{X’\cup NewCand} (u)$
检查$\tau$-core条件：$\forall u\in X’\cup NewCand$
1
2
if deg_D(u) < τ * deg(u)
D ← D \ u
反复迭代：直到没有顶点被移除
返回NewExt