一种求解最小支配集问题的置信传播算法

刘子琳，王晓峰，2，芦 磊，程亚南

(1. 北方民族大学计算机科学与工程学院，宁夏 银川 750021；2. 北方民族大学图像图形智能处理国家民委重点实验室，宁夏 银川 750021)

1 引言

在运筹学中，最小支配集已经被证明是一个NP难问题[1]。最小支配集(Minimum Dominating Set，简称为MDS)是一种最重要的支配集问题，在社会网络[2]、城市交通网络[3]，以及物流网络中心的选址[4]等领域有着广泛的应用。最小支配集问题的目的是构造一个最小的节点集合，使得网络的任何节点要么在该集合中，要么与该集合中至少一个节点相邻。目前，求解最小支配集问题的算法主要分为精确算法[5]和启发式算法[6]，精确算法能够处理一些小规模问题，但处理大规模问题时的时间复杂度和空间复杂度较高；启发式算法能获得较好近似度结果，时间复杂度较低，但容易陷入局部最优解，其完备性和唯一性不能保证。

在无向图G(V，E)中，V表示图G中的所有节点，E表示所有节点之间的边。令集合S={v1，v2，…，vm}，其中vm⊆V，若S⊆V，S≠∅，对于∀x∈V-S，x都与S中至少一个节点有边相连，则称S是图G的支配集。所有支配集中节点数目最少的则称为图G的最小支配集。|S|为最小支配数，相关文献中也用γ(G)表示[7]。

在求解最小支配集的相关算法研究中，文献[5]描述了求解最小支配集的精确算法，错误率较小，但时间复杂度极大。文献[8]采用线性规划的内点法求解最大集合覆盖，极大地降低了计算复杂度。文献[9]比较了标准的贪婪算法、LP近似算法以及将贪婪算法和LP近似算法相结合而设计的混合算法的性能，得出了LP混合算法具有高效性。文献[10]将粗糙集理论中的属性序引入到图论中，研究顶点序下图的支配集问题。文献[11]通过对蚁群算法添加信息素校正策略，设计了求解最小连通支配集的蚁群优化算法。局部搜索算法也已经被提出来启发式地解决MDS问题[12-15]，到目前为止，最好的多项式算法只能保证得到的支配集的大小不超过最小值的lnN倍[16.17]。

线性规划(Linear Programming)是运筹学中研究、发展较成熟的一个重要分支，是一种用来辅助科研人员进行科学研究的数学方法。线性规划问题一般是指求线性目标函数在线性约束条件下的最大值或最小值的问题，构建线性规划方程来求问题最优解[18]。

近年来，信息传播算法(Message Propagation Algorithm，MP)发展迅速，信息传播算法基于统计物理学的“空腔”概念提出，是一种作用于因子图(Factor Graph)上的概率算法[19，20]。在组合优化问题方面，信息传播算法的应用已取得丰硕的成果，如MAX-SAT问题、Maximum-Weight Matching问题、Minimum Cost Network Flow问题、图的着色、最大独立集等[21]。文献[20]提出了三种信息传播算法求解可满足问题，分别为警示传播(Warning Propagation，WP) 算法、置信传播(Belief Propagation，BP) 算法和调查传播(Survey Propagation，SP)算法，SP算法是目前求解可满足问题最为有效的算法，能够稍高于线性时间求解难解SAT区域的具备107变量规模的实例，几乎能够有效求解接近相变点的可满足性实例。文献[22]指出，广义叶子移除过程可以精确地解决MDS问题，并用平均场方法求解了一个自旋玻璃模型来估计MDS的大小。文献[23]指出，BP算法可以解决用线性规划(Linear Programming，LP)公式来描述的组合优化问题，并且证明了其收敛性。文献[24]设计了大量组合优化问题的BP算法，这对我们设计求解最小支配集的置信传播算法很有参考意义。

基于上述研究，本文将MDS问题的无向图通过集合覆盖映射为因子图，基于因子图构建线性规划方程，设计出一种求解最小支配集问题的置信传播算法。实验结果表明：本算法可以近似解决最小支配集问题，且算法的性能优于其它算法。

2 基本知识

2.1 集合覆盖

给定一个全集U，集合S={S1，S2，…，Sn}，Si∈U且S1∪S2∪…∪Sn=U。集合覆盖问题要找到一个子集D={D1，D2，…Dk}，D∈S，使得D1∪D2∪…∪Dk=U，同时|D|最小。例如给定全集U={1，2，3，4，5}，S={{1，2，3}，{2，4}，{3，4}，{4，5}}，虽然S中所有元素的并集是U，但是可以找到S的一个最小子集D={{1，2，3}∪{4，5}}，使得{1，2，3}∪{4，5}=U，则集合D可以被称为一个集合覆盖。

文献[25]指出支配集可规约到集合覆盖问题，求解网络无向图的支配集时，可以先转化成求集合覆盖问题的解。转换的步骤为：遍历所有的节点，将当前遍历到的节点及其邻居节点放置到同一个子集合中，则最小支配集问题转化为找到一个所含顶点个数最少的子集T，使得|T∩Sj|≥1，其中Sj是当前节点及其邻居节点的集合。相应地，集合覆盖问题也可使用BP算法的思路去求解。

2.2 因子图

因子图(Factor Graph)用图模型来代表变量之间的关系，可以将一个复杂的网络结构模型化。因子图是一个具有变量节点和因子节点的二部图，可以将一个含有多个变量的全局函数因子分解，得到几个局部函数的乘积。因此在最小支配集问题上，网络节点的联合置信分布比较复杂的情况下，因子图结合信息传播算法可以将网络节点的联合置信分布进行边缘化，从而将复杂的实际问题简单化。

图1 因子图模型

给定一个赋值指派z={x1，x2，…xn}∈{0，1}n，如图1所示的因子图模型，变量节点X={x1，x2，x3，x4}，因子节点F={fa，fb，fc}，当且仅当函数节点fn与变量节点xn之间有对应关系时，两者有边相连。则图1中的因子图关系可以表示为Pr[Z=z]=fa(x1，x3)fb(x1，x2，x4)fc(x2，x4)。因此我们可用如下GM公式表示因子图：

(1)

3 因子图转换算法

根据网络支配集的特性，可以将无向网络图的各个节点映射成变量节点，各个节点及其邻居节点构成的子集合映射成函数节点，即可生成对应问题的因子图模型。相对应的，在集合覆盖问题中，一个集合对应一个因子节点，集合里面的变元即为因子节点的所有邻居节点。下面我们给出最小支配集问题对应的无向图与因子图之间的转换算法。

算法开始时随机生成无向图邻接矩阵，首先生成各节点及其邻居节点构成的集合，映射成函数节点，图中的各个顶点则映射成变量节点。最后获得变量节点和函数节点的对应关系，构造成因子图。具体算法过程如下：

算法1：因子图转换算法

输入：无向图

输出：因子图模型

1)生成无向图邻接矩阵；

2)生成各节点及其邻居节点构成的子集合；

3)无向图中的节点映射为因子图中的变量节点；

4)一个子集合为一个函数节点，并向集合里面的变元节点添加边。

具体转化结果如图2、图3所示。

图2 无向图G

图2是一个无向图G(V，E)，顶点集V={1，2，3，4，5，6}。最小支配集为{3，5}或{2，3}，最小连通支配集为{2，3}。转化成集合覆盖问题，则有6个集合，分别为：S1={1，2，5}，S2={2，1，3，5}，S3={3，2，5，6}，S4={4，3}，S5={5，1，2，6}，S6={6，3，5}。

图3 图2对应的因子图模型

如图3所示，将6个节点映射成为变量节点，6个集合S={S1，S2，S3，S4，S5，S6}代表每个节点及其邻居节点构成的集合，映射成函数节点。算法由Sn与n之间相互传递消息，改变两类节点的信息，直至收敛。

4 最小支配集的信念传播算法

4.1 置信迭代方程

BP算法的迭代方程为

(2)

(3)

其中Z是归一化函数。

4.2 最小支配集线性规划方程

最小支配集问题是一类经典的组合优化问题，该问题的LP方程

(4)

其中δ(a)是因子图中因子节点a的所有相邻变量节点，xi对应因子图中变量节点，xi=1表示选取该点选入最小支配集中，xi=0表示不选取，则对GM模型有如下定义

(5)

对于最小支配集问题的能量函数ψa定义如下

(6)

4.3 最小支配集的置信传播算法

算法2： BP-update算法

输入：MDS对应的因子图，最大迭代次数tmax；精度ε

0)初始化：对于因子图的每个边a→i，随机初始化消息μa→i(xi)∈[0，1]

1)从t=1到t=tmax：

(7)

因子图变量节点的概率即为无向图节点的取值概率，根据式(3)得到每个节点的取值概率，构建出节点的概率向量p=(p(1)，p(2)…p(n))。通过以下算法求出具体的最小支配集。定义一个最小支配集τ={x1，x2，…，xn}，如果xi=1，则在最小支配集集合中；如果xi=0，则不在最小支配集集合中。下面给出求解MDS的BP算法，记为BP-MDS算法。

算法3： BP-MDS算法

输入：节点的取值概率向量p；节点集合[nodes]

输出：最小支配集τ

for i in [nodes]：

if pi(1)>pi(0)：

xi=1

elif pi(1)

xi=0

else：

xi=none

if τ is not [dominating set]：

for i in [nodes]：

if len([xi+neighbor(xi)])<1：

j=random[xi+neighbor(xi)]

xj=1

for i in [nodes]：

if xi==0：

continue

else：

xi=0

if τ is not [dominating set]：

xi=1

5 数值实验及分析

本文实验以普通PC的64位Windows10操作系统为平台，基于Python3.7进行算法测试。

图4 不同节点规模的收敛速度

图4所示为BP-MDS算法在不同节点规模下的收敛速度。随机选取三组节点规模的无向图，其中节点规模n={50，100，200}，不同规模分别随机生成100组实例进行实验。横坐标是迭代次数，纵坐标是收敛概率。由图可见，随着节点规模增加，迭代次数增大，收敛速度变慢，意味着算法的效率逐渐降低。但后期始终可以收敛，说明收敛速度并没有影响算法的寻优质量，很好地验证了BP-MDS算法的可行性。

图5 三种算法的平均最优解

图5是KCenters算法、贪婪算法与BP-MDS算法在不同节点规模下得到的平均最小支配集大小。对n个节点生成的随机无向图求最小支配集，对三种算法在50组实例中取得的解求平均值进行比较。可以看到小规模实例中(n<=20)，三种算法的求解质量相近。但随着节点规模增加，BP-MDS算法的求解质量明显优于KCenters算法和贪婪算法。由此可见，随着n增大，BP-MDS算法求解性能优于另外两种算法。

图6 BP-MDS算法收敛性

图6所示是BP-MDS算法在不同规模下的收敛性。随着规模n的增大，算法求得的解空间也较大，大大增加了运行时间和迭代次数，当迭代次数达到最大值，算法强制退出。虽然随着问题规模的增大BP算法效率有一定降低，但是经过表1可得，BP算法的效率仍然优于其他算法。

表1是BP-MDS算法与KCenters算法、遗传算法在不同规模下求得平均最优解的时间比较。其中n是节点规模，AVG是平均最优解，Time是求得最优解的平均时间。可以看到在小规模实例下，虽然BP-MDS算法的求解效率略低于KCenters算法，求得解的质量却始终优于KCenters算法。随着规模增大，BP-MDS算法在时间和求解质量上都要优于另外两种算法。

表1 三种算法的平均时间

6 总结

本文设计了求解无向图的最小支配集问题的置信传播算法，将把最小支配集映射成因子图，构建基于因子图的线性规划方程，代入BP迭代方程中，不断迭代直至收敛得到实验结果，同时这种算法也为集合覆盖问题的求解提供了思路。实验结果表明，置信传播算法求解的时间复杂度较低，效率较高，总体来说其性能优于传统的启发式算法和分布式算法。但缺陷是随着问题规模的增大，可能产生不收敛的现象。接下来的工作是尽量解决大规模不收敛的情况，设计求解最小支配集的调查传播算法、用信息传播算法求解支配集及其变种问题、将线性规划模型推广到更多的组合优化问题等等。