论文部分内容阅读
摘要：很多领域产生的大量数据都可以很自然地用不确定图模型表示和描述，如蛋白质交互网络、社交网络、无线传感器网络等。本文研究不确定图上最可靠的最小生成树问题，该问题具有广泛的应用价值和研究意义。精确地求解算法需要枚举所有可能的最小生成树并找出其中出现次数最多的那个。因此，枚举开销随着边数增多呈指数增长，当图规模较大时并不可行。为此本文提出了一个时间复杂度为O（d |V|2）的启发式贪心算法，其中d为最大的顶点度数，|V|为顶点数。实验结果表明，该算法具有较好的效率和较高扩展性。
关键词：不确定图：最可靠最小生成树：贪心算法
0引言
近年来，很多领域产生的大量数据可以利用图模型表示。由于测量数据的工具不精确、数据本身性质等多方面原因导致图数据普遍存在不确定性，如蛋白质交互网络（PPI）、社交网络、无线传感器网络等，将不确定性融入到图中得到不确定图。
确定图上的最小生成树问题具有十分重要的实际意义。在连通图G=（v.E）中，E中每条边有对应的权值，图G的一棵生成树是连接V中所有顶点的一棵树，生成树中所有边的权值总和称为生成树的代价，使这个代价最小的生成树称为图G的最小生成树（Minimum Spanning Tree.MST）。很多实际应用问题可以通过求解最小生成树得到很好的解决。例如，道路规划问题，可将各个城镇作为图的顶点，城镇之间的道路作为边，每条道路的修建代价作为边上的权值，在该图上求最小生成树可以得到修建代价最少的修路方案。如，在无线传感器网络中，由于传感器节点间的通信链路存在一定的干扰，每条链路存在一定的失效风险，因此其拓扑结构可以很自然地建模为不确定图。顶点表示各传感器节点，边表示可能存在的通信链路，边的权值由距离决定，边的存在概率表示该链路正常工作的可能性大小。在该图上求解最可靠的最小生成树非常重要，其上的边集即链路集合是最稳定可靠的连通路径，利用该生成树可以优化路由选路过程，用最少的代价完成全部节点间通信的同时，保证了网络通信的可靠性与稳定性。
不确定图是边带有概率的特殊加权图，边的概率表示该边存在的可能性大小。因此不确定图有多种可能的存在形式，每一个存在形式称为蕴含子图，蕴含子图是一个以一定概率确定存在的加权图，由此可知每个连通的蕴含子图上都有至少一棵最小生成树，这些最小生成树构成了不确定图的最小生成树集合。
本文研究不确定图上最可靠的最小生成树问
1问题定义
本节介绍一种不确定图模型，并形式化描述不确定图上的最可靠的最小生成树问题。
1.1不确定图模型
不确定图是一个四元组G=（v.e.p.W），其中V是顶点集，E为边集，P是边的存在概率函数，即E到（0.1]的映射，P（e）表示边e存在的概率，W为权重函数，定义了每条边的权值大小。由于边的不确定性导致不确定图具有多种存在形式，每种确定的存在形式称之为蕴含子图，也称为可能世界。所有的蕴含子图构成不确定图所蕴含的确定图集合，记为Imp（G）。对于g∈Imp（G），称之为G蕴含g.记作C→g.假定所有边相互独立，蕴含概率P（G→g）等于所有g中的边的存在概率与不在g中的边不存在概率之积，如公式（1）所示。
下面通过一个简单的例子来说明蕴含子图及其存在概率的含义。
例1如图1（a）所示，图G是包含3个顶点和3条边的不确定图，每条边存在与否决定了图G共有23=8个蕴含子图，每个子图的存在概率由公式（1）计算得到。以图1（b）中的子图g2为例，P（C→g2）=0.4×（1-0.9）×（1-0.7）=0.012.其它子图的存在概率计算与之类似，结果如图1（b）所示。
1.2 最可靠的最小生成树
下面通过例2求图1（a）中不确定图G上的MSTmax来说明公式（3）的含义。
MSTmax是最小生成树集合中存在概率最大的那棵，即MST3，MSTmax={Ac，BC}，P（MSTmax）=P（MST3）=0.378，利用|MST|表示最小生成树的代价，则|MSTmax|=|MST3|=7。
由MSTmax的定義可知，一种直观的求解算法是枚举所有蕴含子图g.并在g上求最小生成树得到一个最小生成树集合，求集合中存在概率最大的最小生成树，然而该算法在实践上并不可行，图G共有2|E|，个蕴含子图，枚举代价随边数增多呈指数增长，当图规模较大时，算法效率十分不理想。因此本文提出一种启发式的贪心算法近似求解MSTmax，时间复杂度为0（d2|V|2），相对于枚举法性能大大提高，实验结果表明该算法在通常情况下能够得到MSTmax。
2贪心算法求最可靠最小生成树
启发式贪心策略近似求解不确定图上最可靠的最小生成树，在2.1节给出算法的详细描述，而后在
2.2节分析贪心算法的运行时间。
2.1 算法描述
给定连通不确定图G=（v.e.p.W），求解其上MSTmax的算法思想与Prim算法求解确定图上最小生成树类似，维持一棵树a.树A从任意根顶点r开始形成，并逐渐生成，直至树A覆盖了V中的所有顶点，每一次，一条连接树A与GA=（v.A）中某孤立顶点的概率最大的轻边被加入到树A中，其中轻边是指权值最小的边，下面给出概率最大轻边的定义。 定义1概率最大的轻边（Light Edge withMaximum Probability.LEMP），将所有连接树A与森林GA=（v.A）中某孤立顶点的边加入队列S中，按公式（4）计算其加入到树A中的概率，其中概率值最大的边即为LEMP。
将队列S中的边按权值非降序排列，pi表示位于排序队列中第i条边的存在概率，l≤i≤|S|，则第i条边作为概率最大的轻边（LEMP）加入到树A中的概率P;为：
其中，ni表示队列中所有与第i条边权值相等，但位置排在其前面的边的个数，O≤n;≤i-1。下面举例说明公式（4）。
例3假设G中所有与A中顶点直接相连但不在A中的边有{e1，e2，e3}，将其加人队列s.按照权值升序排列，假设w12=w3，则这3条边加入到树A中的概率依次为：P1，（1-P1）·P2，（1-P1）·P3。
直观地讲，e1具有最小权重值w1，故其作为轻边加入树A的概率就是其自身的存在概率p1;对于e2，由于其的权值w2大于e1的权值w1，，所以只有在e1不存在的情况下，e2才能作为轻边加入到A中，概率为e1不存在的概率乘以e2存在的概率，即（1-p1）·p2;对于e3，由于e3的权值w3和e2的权值w2，相等，则其加入到A的概率与e2存在与否无关，概率等于e1不存在的概率乘以e3存在的概率，即（1-p1） ·p3。
下面给出具体的算法描述，见算法1。实现时，采用插入排序法排序队列s.因为每次添加新边之前，S中已有的边是按权值升序排列的，只需要将新加入的边插入到已经排好序的队列中即可，这样减少了全部边重新排序的时间开销。
算法1最可靠的最小生成树算法，
输入：不确定图G=（v.e.p.W）。
输出：最可靠的最小生成树MST_max的边集A
（1）MST_V={r};A=φ;S=φ
（2）将所有与r相连的边添加到队列S中
（3）WHILE|MST_V|
关键词：不确定图：最可靠最小生成树：贪心算法
0引言
近年来，很多领域产生的大量数据可以利用图模型表示。由于测量数据的工具不精确、数据本身性质等多方面原因导致图数据普遍存在不确定性，如蛋白质交互网络（PPI）、社交网络、无线传感器网络等，将不确定性融入到图中得到不确定图。
确定图上的最小生成树问题具有十分重要的实际意义。在连通图G=（v.E）中，E中每条边有对应的权值，图G的一棵生成树是连接V中所有顶点的一棵树，生成树中所有边的权值总和称为生成树的代价，使这个代价最小的生成树称为图G的最小生成树（Minimum Spanning Tree.MST）。很多实际应用问题可以通过求解最小生成树得到很好的解决。例如，道路规划问题，可将各个城镇作为图的顶点，城镇之间的道路作为边，每条道路的修建代价作为边上的权值，在该图上求最小生成树可以得到修建代价最少的修路方案。如，在无线传感器网络中，由于传感器节点间的通信链路存在一定的干扰，每条链路存在一定的失效风险，因此其拓扑结构可以很自然地建模为不确定图。顶点表示各传感器节点，边表示可能存在的通信链路，边的权值由距离决定，边的存在概率表示该链路正常工作的可能性大小。在该图上求解最可靠的最小生成树非常重要，其上的边集即链路集合是最稳定可靠的连通路径，利用该生成树可以优化路由选路过程，用最少的代价完成全部节点间通信的同时，保证了网络通信的可靠性与稳定性。
不确定图是边带有概率的特殊加权图，边的概率表示该边存在的可能性大小。因此不确定图有多种可能的存在形式，每一个存在形式称为蕴含子图，蕴含子图是一个以一定概率确定存在的加权图，由此可知每个连通的蕴含子图上都有至少一棵最小生成树，这些最小生成树构成了不确定图的最小生成树集合。
本文研究不确定图上最可靠的最小生成树问
1问题定义
本节介绍一种不确定图模型，并形式化描述不确定图上的最可靠的最小生成树问题。
1.1不确定图模型
不确定图是一个四元组G=（v.e.p.W），其中V是顶点集，E为边集，P是边的存在概率函数，即E到（0.1]的映射，P（e）表示边e存在的概率，W为权重函数，定义了每条边的权值大小。由于边的不确定性导致不确定图具有多种存在形式，每种确定的存在形式称之为蕴含子图，也称为可能世界。所有的蕴含子图构成不确定图所蕴含的确定图集合，记为Imp（G）。对于g∈Imp（G），称之为G蕴含g.记作C→g.假定所有边相互独立，蕴含概率P（G→g）等于所有g中的边的存在概率与不在g中的边不存在概率之积，如公式（1）所示。
下面通过一个简单的例子来说明蕴含子图及其存在概率的含义。
例1如图1（a）所示，图G是包含3个顶点和3条边的不确定图，每条边存在与否决定了图G共有23=8个蕴含子图，每个子图的存在概率由公式（1）计算得到。以图1（b）中的子图g2为例，P（C→g2）=0.4×（1-0.9）×（1-0.7）=0.012.其它子图的存在概率计算与之类似，结果如图1（b）所示。
1.2 最可靠的最小生成树
下面通过例2求图1（a）中不确定图G上的MSTmax来说明公式（3）的含义。
MSTmax是最小生成树集合中存在概率最大的那棵，即MST3，MSTmax={Ac，BC}，P（MSTmax）=P（MST3）=0.378，利用|MST|表示最小生成树的代价，则|MSTmax|=|MST3|=7。
由MSTmax的定義可知，一种直观的求解算法是枚举所有蕴含子图g.并在g上求最小生成树得到一个最小生成树集合，求集合中存在概率最大的最小生成树，然而该算法在实践上并不可行，图G共有2|E|，个蕴含子图，枚举代价随边数增多呈指数增长，当图规模较大时，算法效率十分不理想。因此本文提出一种启发式的贪心算法近似求解MSTmax，时间复杂度为0（d2|V|2），相对于枚举法性能大大提高，实验结果表明该算法在通常情况下能够得到MSTmax。
2贪心算法求最可靠最小生成树
启发式贪心策略近似求解不确定图上最可靠的最小生成树，在2.1节给出算法的详细描述，而后在
2.2节分析贪心算法的运行时间。
2.1 算法描述
给定连通不确定图G=（v.e.p.W），求解其上MSTmax的算法思想与Prim算法求解确定图上最小生成树类似，维持一棵树a.树A从任意根顶点r开始形成，并逐渐生成，直至树A覆盖了V中的所有顶点，每一次，一条连接树A与GA=（v.A）中某孤立顶点的概率最大的轻边被加入到树A中，其中轻边是指权值最小的边，下面给出概率最大轻边的定义。 定义1概率最大的轻边（Light Edge withMaximum Probability.LEMP），将所有连接树A与森林GA=（v.A）中某孤立顶点的边加入队列S中，按公式（4）计算其加入到树A中的概率，其中概率值最大的边即为LEMP。
将队列S中的边按权值非降序排列，pi表示位于排序队列中第i条边的存在概率，l≤i≤|S|，则第i条边作为概率最大的轻边（LEMP）加入到树A中的概率P;为：
其中，ni表示队列中所有与第i条边权值相等，但位置排在其前面的边的个数，O≤n;≤i-1。下面举例说明公式（4）。
例3假设G中所有与A中顶点直接相连但不在A中的边有{e1，e2，e3}，将其加人队列s.按照权值升序排列，假设w12=w3，则这3条边加入到树A中的概率依次为：P1，（1-P1）·P2，（1-P1）·P3。
直观地讲，e1具有最小权重值w1，故其作为轻边加入树A的概率就是其自身的存在概率p1;对于e2，由于其的权值w2大于e1的权值w1，，所以只有在e1不存在的情况下，e2才能作为轻边加入到A中，概率为e1不存在的概率乘以e2存在的概率，即（1-p1）·p2;对于e3，由于e3的权值w3和e2的权值w2，相等，则其加入到A的概率与e2存在与否无关，概率等于e1不存在的概率乘以e3存在的概率，即（1-p1） ·p3。
下面给出具体的算法描述，见算法1。实现时，采用插入排序法排序队列s.因为每次添加新边之前，S中已有的边是按权值升序排列的，只需要将新加入的边插入到已经排好序的队列中即可，这样减少了全部边重新排序的时间开销。
算法1最可靠的最小生成树算法，
输入：不确定图G=（v.e.p.W）。
输出：最可靠的最小生成树MST_max的边集A
（1）MST_V={r};A=φ;S=φ
（2）将所有与r相连的边添加到队列S中
（3）WHILE|MST_V|