Bron–Kerbosch 算法

朴素的BK算法伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
R := {}
P := node set of G
X := {}

BronKerbosch(R, P, X):
if P and X are both empty:
report R as a maximal clique
for each vertex v in P:
BronKerbosch(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
P := P \ {v}
X := X ⋃ {v}

其中 R{R} 为已确定的极大团顶点的集合; P{P} 为未处理顶点集,其初始状态是所有结点; X{X} 为已搜过的并且属于某个极大团的顶点集合,用于判重。

  1. 对于每一个在 P{P} 中的点 vv ,我们把 vv 加入 R{R}P{P} 中的点与 R{R} 中所有的点都是连接的,这样加入 vv,保证 R{R} 依然是一个团),对在 P{P} 中且与 vv 相连的这部分集合中寻找下一个可能加入 R{R} 的点。
  2. 回溯时我们把 vvP{P} 中移出,加入 X{X} 代表当前状态下对包含 vv 的极大团已经计算完毕了。
  3. R{R} 集合为极大团的时候,必须要满足 P\text{P}X{X} 都是空的。P{P} 存放的是还可能加入 R{R} 的点,P{P} 为空代表没有点还能再加入到 R{R} 当中,而 X{X} 存放的是已经完成极大团计数的点,而且 X{X} 中的点必然是与所有 R{R} 中的点都有边存在,也即 X{X} 中点必然可以与 R{R} 构成极大团。

pivot 优化

基本思想是选择一个pivot uu ,要与 RR 集合构成极大团,那么取的点一定是 PΓ(u)P \cap \Gamma(u) 中的一个点( Γ(u)\Gamma(u) 表示与 uu 相邻的点)。其伪代码如下:

1
2
3
4
5
6
7
8
BronKerbosch2(R, P, X):
if P and X are both empty:
report R as a maximal clique
choose a pivot vertex u in P ⋃ X
for each vertex v in P \ N(u):
BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
P := P \ {v}
X := X ⋃ {v}

degeneracy ordering 优化

如果图的结点存在一种序列,使得每个结点和它所有前驱形成的诱导子图中,该结点度不超过 kk ,则称该图为 kk - degenerate graph( kk - 退化图);可以找到最小的 kk 值,使得原图满足 kk - 退化图,此时对应的序列即为退化序(degeneracy ordering)。

简单来说,退化序是一种从节点集合中选择一个节点序列的方式,其中每个节点的度数都小于或等于它在序列中的位置。

使用退化序的BK算法的优化包括以下方面:

  1. 节点选择顺序:在BK算法的每一步中,需要选择一个候选节点来扩展当前的团。使用退化序可以确保首先选择度数最小的节点作为候选节点。由于退化序中度数较低的节点更有可能与其他节点组成团,这有助于减少搜索空间,提高算法效率。
  2. 分支限界:在BK算法中,当已经找到一个团后,可以使用分支限界法来减少搜索的深度。使用退化序,可以更容易地识别那些不可能再扩展为更大团的节点,从而在搜索树的早期阶段剪枝。
  3. 剪枝策略:基于退化序,可以开发更强大的剪枝策略。例如,可以考虑在搜索团的过程中,如果已知某节点的度数超过当前最大团的大小,那么可以立即停止对该节点的探索,因为它不可能在当前情况下产生更大的团。

二部图极大团

二部图上的极大团(biclique):

指一对(集合对)(X,Y) s.t XU,YV and  uX,vY,(u,v)E(X,Y)\ \text{s.t}\ X \subseteq U,Y\subseteq V\ \text{and }\ \forall u \in X, v\in Y,(u,v)\in E

PMBE

在Aman Abidi等人的论文中给出如下算法框架:

biclique.png

算法解释

EnumerateMaximalBiclique(U,V)\texttt{EnumerateMaximalBiclique(}U,V \texttt{)} 函数中采用的逆拓扑序确定枚举顺序,cand(X)cand(X) 表示搜索时 XX 的候选节点。

在枚举二分图极大团的算法中,其搜索空间是一颗set enumeration tree。

PMBE(B,Y,cand)\texttt{PMBE(}B,Y,cand \texttt{)} 函数中 XP(V)X\in \mathcal{P}(V) 。(PMBE是Pivot-based Maximal Biclique Enumeration的缩写)

Γ(X)\Gamma(X) 表示与集合 XX 内任意点均相邻的所有节点。

大致思想是固定 UU 侧节点,与另一侧求交,并且同时更新 UU 集合。

pivot

因为clique与biclique性质不同,所以在clique中选择pivot的方法是无效的,因此我们要修改针对clique的pivot选择方法。我们首先定义如下的包含关系:

Containment( \subset ) :

对于给定的二部图 G=(UV,E), let v1,v2VG=(U\cup V,E),\ let\ v_1,v_2 \in V ,那么 v1v_1v2v_2 包含     Γ(v1)Γ(v2)\iff \Gamma(v_1) \subset \Gamma(v_2)

包含关系具有如下性质:

给定 v1,v2cand(X)v_1,v_2 \in cand(X) ,如果 v1v2v_1\subset v_2 ,那么 sub(v1)sub(v_1) 包含 sub(v2)sub(v_2) 。其中 sub(X)sub(X) 指在搜索空间中以 XX 为根的子树。

证明:

因为 v1v2v_1 \subset v_2 ,所以 Γ(v1)Γ(v2)\Gamma(v_1) \subseteq \Gamma(v_2) ,进而有 Γ(Γ(v1))Γ(Γ(v2))\Gamma(\Gamma(v_1)) \subseteq \Gamma(\Gamma(v_2)) 。又因为 sub(v1)sub(v_1)sub(v2)sub(v_2)Γ(Γ(v1))\Gamma(\Gamma(v_1))

Γ(Γ(v2))\Gamma(\Gamma(v_2)) 的幂集。故 sub(v2)sub(v_2) 包含 sub(v1)sub(v_1)

于是,我们定义pivot:

Pivot:

给定一个顶点集 XX ,我们定义顶点 pcand(X)p\in cand(X) 为pivot当且仅当  vcand(X) s.t. Γ(v)Γ(p)\exist \ v \in cand(X) \ \text{s.t.}\ \Gamma(v) \subset \Gamma(p)

更进一步,我们有如下剪枝策略:

在搜索空间的任一递归层面上,选择pivot pcand(X)p \in cand(X) 并从 cand(X)cand(X) 剪枝所有被 pp 包含的顶点不丢失任何biclique。

但朴素做法较为低效,Aman Abidi等人提出了一种索引结构CDAG来进行高效的剪枝。

CDAG

CDAG有两个部分:有向无环图(DAG)和索引(R)。

Range index:

对于顶点 vcandv\in cand ,索引范围( Rv=[x,y], where x,yZR_v = [x,y],\ where\ x,y\in \Z^* )指遍历时分配给DAG中对应顶点的区间,x,yx,y 分别表示遍历的开始和结束。

CDAG:

一个CDAG,C=(Vˉ,Eˉ)C=(\bar{V},\bar{E}) 是一个无环图  s.t. vˉVˉ\ \text{s.t.}\ \forall \bar{v} \in \bar{V}vvvcandv\in candRvR_v 组成,并且 (vˉ,uˉ)Eˉ,uˉvˉ\forall(\bar{v},\bar{u})\in \bar{E},\bar{u}\subset \bar{v}

(这论文过于冗长了,看看下篇)

iMBEA

考虑二部图上基础的MBE算法,在图 G=(L,R,E)G=(L,R, E) 中,依次遍历 RR 中的子集 B2RB\in 2^R 并使得 AABB 中的common neighbours。那么,如果 AA \ne \emptyset(A,B)(A,B) 就是一个极大团。

iMBEA算法使用一种order去不重复地遍历 2R2^R ,其复杂度达到了 O(Rdmax(R)2R)\mathcal{O}(|R|d_{max}(R)2^{|R|})O(dmax2(R)R2B)\mathcal{O}(d_{max}^2(R)|R|^2\mathcal{B}) ,其中 dmaxd_{max} 表示 RR 中的最大度数的顶点, B\mathcal{B} 表示 GG 中实际的极大团数量。

pivot

给定两个顶点 u,uRu,u'\in R ,如果 uu' 的邻居是 uu 邻居的子集,那么包含 uu' 的极大团一定能通过增加 uu 点来扩张。称 uu 为pivot。 可以理解为两个顶点的neighbours存在交集。

算法框架

biclique2.png

ooMBEA

Lu Chen等人对于稀疏二部图上的情况进行了讨论,并提出了一种新的order方法。

order的重要性

通过order,我们可以把 GG 上的MBE问题转化为其子图上的MBE问题。其中,子图的定义如下:

有序顶点的搜索空间:

给定一个顶点序列 R=(v1,,vR)R = (v_1, \cdots,v_{|R|}) ,和 viRv_i\in Rviv_i 的搜索范围是包含 Rvi+N2(vi)R_{v_i}^+ \cap N_2(v_i)N(vi,G)N(v_i,G) 的子图。其中 Rvi+R_{v_i}^+RR 中的顶点 vi (ii)v_{i'}\ (i'\geq i)N2(v)N_2(v)vv 的2-hop neighbours, N(v,G)N_(v, G)GGvv 的neighbours。

新的order方法

kk unilateral core:

给定一个顶点 vRv\in R ,如果一个包含 vv 子图 HGH \subseteq G 对于任意 vR(H), N2(v,H)k\forall v'\in R(H), \ |N_2(v', H)|\geq k ,我们称 vv 是一个 kk unilateral core。最大的 kk 我们用 τ(v,G)\tau(v,G) 来表示。在 RR 中最大的 τ\tauς(R)\varsigma(R) 表示。对于 LL 顶点集的定义是类似的。

unilateral order:

对于一个排列 R=(v1,,vR)R = (v_1,\cdots,v_{|R|}) ,如果 1iR, vi\forall 1\leq i\leq |R|,\ v_i 有最少的two-hop neighbours在 H+H^+ 中 ,其中 H+H^+Rvi+=vjijRR_{v_i}^+={v_j|i\leq j \leq |R|}N(vi,G)N(v_i,G) 的诱导子图。LL 边order的定义是类似的。

另外,如果我们考虑一个辅助图 GG' ,其顶点包含 R(G)R(G) 中的所有顶点,边是 GG 中2-hop reachable的顶点。那么

Order optimised MBE (ooMBEA) 搜索框架

image.png

order算法

image.png

(没太看懂?看起来是基于辅助图的order策略)

PMUC

基于不确定图的更general的pivot策略。

不确定图:

我们用 G=(V,E,p)\mathcal{G}=(V,E,p) 来表示一个不确定图,其中 p:E(0,1]p:E \to (0,1] 是一个函数表示每条边出现的概率。

我们用 G=(V,EG)G=(V,E_G) 来表示 G\mathcal{G} 中可能的一种图,用 Pr(G)\Pr(G) 来表示 GG 出现的可能性,于是

Pr(G)=eEGpeeEEG(1pe)(1)\Pr(G) = \prod_{e\in E_G} p_e \prod_{e\in E \setminus E_G}(1-p_e) \tag1

我们定义一个 GG 上的团出现的可能性为 Pr(H,G)\Pr(H,\mathcal{G}) ,于是

Pr(H,G)=e{(u,v)u,vH,uv}pe(2)\Pr(H,\mathcal{G}) = \prod_{e\in\{(u,v)|u,v\in H, u \neq v \}} p_e \tag2

基于 (2)(2) 我们对于不确定图上的团由如下定义:

η\eta-clique:

给定一个不确定图 G\mathcal{G} 和一个概率 η[0,1]\eta\in [0,1] ,对于一个顶点集 HH 如果 Pr(H,G)η\Pr(H,\mathcal{G}) \geq \eta ,那么 HH 是一个 η\eta-clique。

maximal η\eta-clique:

有了团的定义,极大团定义与一般图上类似。

maximal (k,η)(k,\eta)-clique:

如果一个 HH 是maximal η\eta-clique,并且 Hk|H|\geq k ,那么 HH 是一个maximal (k,η)(k,\eta)-clique。

我们的目标是枚举 G\mathcal{G} 中所有的maximal (k,η)(k,\eta)-clique。

MUC

原始的MUC算法与一般图上的极大团算法相像。

image.png

其中 rvr_v 表示 RR 中与 vv 相连所有边可能性的乘积。 qq 返回的是 Pr(H,G)\Pr(H,\mathcal{G})

pivot principle

论文中给出了一种对于最大化 P\mathcal{P}-subgraph 的枚举问题的通用pivot策略。其中 P\mathcal{P}-subgraph是具有遗传性质( P\mathcal{P} )的子图。

我们考虑pivot的本质就是对于候选集 CC ,我们删除一个集合 PP 对于之后 P\mathcal{P}-subgraph (在代码中即为集合 RR)的拓展没有影响。我们称 PP 为periphery set。

image.png

M-pivot

基于我们的pivot策略,对于不确定图上的 (k,η)(k,\eta)-clique 枚举问题开发了M-pivot技术。

核心思想:如果我们在递归调用中能够检测到一个包含子集 RR 的极大 η\eta-clique,那么我们可以剪枝掉那些也包含在检测到的最大 η\eta-clique中的候选集 CC 的顶点。

因此在枚举时我们可以只枚举集合 PCP \subseteq C 当且 R{pv}PR \cup \{p_v\}\cup P 是一个包含 R{pv}R \cup \{p_v\} 极大 η\eta-clique 在 RCR \cup C 中,其中 pvCp_v\in C 称为pivot顶点。

Improvement:首先使用基本的M-pivot方法得到一个初始的边缘集合 PP 。然后,它会递归地处理在C但不在P中的顶点。如果在递归调用中找到一个比之前更大的 η\eta-clique,那么它就会替换之前的边缘集合,从而更好地剪枝并提高性能。

例如,考虑一个不确定的图 G\mathcal{G} 。算法首先选择一个顶点,如v1,并找到所有包含v1的最大 (k,η)(k,\eta)-clique。这会产生一个边缘集合,例如{v2, v3, v8}。然后,算法会继续处理在 CC 但不在这个边缘集合中的顶点,如v4,并再次查找所有包含v4的最大 (k,η)(k,\eta)-clique。根据这些新的结果,边缘集合可能会被更新。

PMUC

基于前述pivot策略的伪代码。

image.png