社交网络通常用图来表示，对社交网络的研究能够转化为对图中相关问题的研究．如社交网络中近期出现的正影响支配集问题[1]、连通正影响支配集问题[2]、*-支配集问题和*-连通支配集问题[3]、正影响目标支配集问题[4]等．采用无权图表示社交网络时，任意一条边表示两个节点之间存在某种确定的关系．在一些特殊的社交网络中，任意两个节点之间的关系并不是确定的，或者节点之间的关系有强弱，这些社交网络将用带权图表示．特别地，当任意两个节点之间的边权重取值范围为[0,1]时，该权重表示节点之间能够相互传播信息或影响的概率[5]，目前已应用于社交网络中的信息传播领域，如信息传播模型的设计[6]、影响力最大化问题[7]、信息源定位问题[8]、传播趋势和范围预测[9]等问题．针对边权重取值范围为[0,1]的无向带权图，本研究提出概率支配集(PDS)概念，是传统支配集的一种扩展形式．概率支配集可应用于以下场景：将社交网络表示为边权重取值范围为[0,1]的无向带权图，每个节点能够以一定的概率影响其邻居节点或向其邻居节点传播信息．从图中找出一定数量的节点作为支配点，令图中支配点以外的节点被传播信息或被影响的概率大于等于阈值α，由这些支配点组成的集合称为PDS．本研究首先给出PDS的形式化描述，并证明最小PDS问题是NP难问题，然后基于次模函数提出一个贪心近似算法用于求解最小PDS问题．1 问题描述1.1　问题定义给定一个无向带权图G=(V,E,P)，其中：V为节点集；E为边集；P:E→[0,1]为边的权函数．在图G中，节点的个数n=|V|，边的个数m=|E|．N(v)表示节点v的邻居节点集合．给定一个支配点组成的集合D，ND(v)表示N(v)与集合D的交集，D⊆V，ND(v)=N(v)⋂D．将节点之间相互支配看作是独立事件，v被支配的概率定义为节点v至少被ND(v)中一个节点支配的概率，记做tD(v)，计算公式为tD(v)=0    (ND(v)=∅);1-∏u∈ND(v)(1-pu,v)    (ND(v)≠∅), (1)式中pu,v为节点v和u之间的边权重值．引理1 tD(v)是关于D的单调递增函数．证明 对于(u,v)∈E，满足0≤pu,v≤1，由此可以推出0≤1-pu,v≤1．由式(1)可看出：当D中的节点数增加时，ND(v)的元素增加，∏u∈ND(v)(1-pu,v)随着ND(v)中元素的增加而减少，tD(v)是关于D的单调递增函数．给定阈值α，对于任意节点集合D⊆V，使得∀v∈V，v∈D或tD(v)≥α，称D为一个概率支配．最小PDS问题即从节点集合V中找出最少数量的节点构成集合D，使得∀v∈V，v∈D或tD(v)≥α．若α的取值过大，则最小PDS问题可能无解．对于v∈V，v被支配的最大概率用q(v)表示，有q(v)=1-∏u∈N(v)(1-pu,v)．设定的α不能超过所有节点的最大被支配概率中的最小值．令μ=minv∈Vq(v)，当α的取值区间为(0,μ]时，最小PDS问题有解．1.2　问题的计算复杂性引理2 求解最小PDS问题是NP难的．证明 由于最小支配集问题是NP难问题，只须证明可将最小支配集问题归约到最小PDS问题即可．任意给定一个无向图G1=(V,E)，构造一个无向带权图G=(V,E,P)，其中P为恒等映射E→{1}，即对任意边(u,v)∈E，有pu,v=1．该构造显然能在关于n=|V|的多项式时间内完成，易看出：当阈值α=1时，G的最小PDS即为图G1的最小支配集问题．即最小支配集问题的任一实例可多项式归约为最小PDS问题的一个实例求解．2 贪心近似算法2.1　算法描述约定：∀v∈D，tD(v)=α；∀v∈V-D，v须要被支配的概率和已被支配的概率之间的差值用gD(v)表示，即gD(v)=max(0,α-tD(v))．本研究基于次模函数提出一个贪心近似算法，用于求解最小PDS问题，并且分析算法的近似比．根据PDS的定义，对于v∈V，须满足v∈D或tD(v)≥α．根据上述约定可知：图中任意节点v被支配的概率由0上升至α后，v被支配的概率不再增加．所有节点被支配的概率变化过程如势函数f(D)所示，即f(D)=nα-∑v∈V-DgD(v)．(2)贪心算法的思想是依次从非支配点集合中选择节点作为支配点，令所有节点被支配的概率增加最多．基于式(2)对贪心算法进行形式化描述，即当∃v∈V，v∉D且tD(v)α时，依次从V-D选择支配点u，使得f(D∪{u})-f(D)达到最大值．引理3给出势函数f(D)的性质．引理3 a. f(D)是拟阵函数；b. 当D为PDS时，f(D)=nα；c. 若f(D)nα，则图G中∃u∈V-D，使得f(D∪{u})-f(D)0．证明 a. 显然f(∅)=0．基于引理1可知gD(v)关于D是非增的，可以推出f(D)是关于D的非减函数．只须证明f(D)遵循边际效用递减规律[10-11]，即对于A⊆B⊆V，x∉B，始终满足条件f(A∪{x})-f(A)≥f(B∪{x})-f(B)．令A'= A∪{x}，B'=B∪{x}，由式(2)可推出：f(A')-f(A)=gA(x)+∑v∈N(x)(gA(v)-gA'(v))；f(B')-f(B)=gB(x)+∑v∈N(x)(gB(v)-gB'(v))．显然gA(x)≥gB(x)，只须比较gA(v)-gA'(v)和gB(v)-gB'(v)之间的大小关系．若gA'(v)0，gB'(v)0，则    gA(v)-gA'(v)=(1-tA(v))px,v≥(1-tB(v))px,v=gB(v)-gB'(v);若gA'(v)0，gB'(v)=0，则    gA(v)-gA'(v)=(1-tA(v))px,v≥(1-tB(v))px,v≥α-tB(v)=gB(v)-gB'(v);若gA'(v)=0，则    gA(v)-gA'(v)=α-tA(v)≥α-tB(v)=gB(v)-gB'(v).综上所述，f(A')-f(A)≥f(B')-f(B)是成立的．b. 若D为PDS，则∀v∈V-D都满足gD(v)=0，f(D)=nα；若D不为PDS，则∃v∈V-D，gD(v)0，f(D)nα．综上所述，当D为PDS时，f(D)=nα．c. 若f(D)nα，则∃v∈V-D，gD(v)0，此时若选择节点u∈N(v)-D作为支配点，则由引理1可知节点v被支配的概率将增大，由此可以推出f(D∪{u})f(D)．基于引理3，给出求解最小PDS问题的贪心算法(greedy algorithm for the minimum PDS problem，GAMP)的伪代码如下．输入 G=(V,E,P)，α输出 DD←∅While f(D)nα doChoose u∈V-D to maximize f(D∪{u})Set D←D∪{u}Output D引理3证明了GAMP对应的势函数f(D)是单调非减的拟阵函数，那么基于文献[12-13]的次模集合覆盖相关理论证明，GAMP是一个近似算法．给出两个现有的定理．定理1 若贪心算法对应的势函数F是一个整数型的拟阵函数，则贪心算法的近似比为H(β)，其中：H为调和级数；β为势函数的最大增量．定理2 若贪心算法对应的势函数F是一个实数型的拟阵函数，则关于算法的近似比有以下结论：a. 贪心算法的近似比为1+ln(β/η)，其中η为势函数的最小增量；b. 当η≥1，且F*≥O时，贪心算法的近似比为1+ln(F*/O)，其中：F*为势函数F的最大值；O为问题最优解的大小．在定理2中，因为F*/O≤β，所以当F满足η≥1，且F*≥O时，采用定理2b中的结论能够得到更好的近似比．基于定理1和定理2，定理3将证明GAMP是贪心近似算法．定理3 GAMP是贪心近似算法，近似比为1+ln((α+γ)/(α-λ))，其中：γ为图中任意节点最大边权重之和，即γ=argmaxv∈V∑u∈N(v)pu,v；λ为图中任意节点满足须要被支配的概率前的最大概率值．证明 引理3证明了GAMP对应的f是拟阵函数．注意到η≤1，显然f是实数型函数．基于定理2a可知，GAMP的近似比为1+ln(β/η)．f是实数型的拟阵函数，对于A⊆B，x∉B，f始终满足条件f(A∪{x})-f(A)≥f(B∪{x})-f(B)，由式(2)可计算    β=f({x})-f(∅)=g∅(x)+∑v∈N(x)(g∅(v)-g{x}(v))=α+∑v∈N(x)px,v=α+γ.对于v∈V，gD(v)0，当选择节点u作为支配点时，D'=D∪{u}，gD'(v)=0，节点v被支配的概率的增量最小，为α-tD(v)．有η=α-max{tD(v)|tD(v)α,v∈V}=α-λ．2.2　复杂度分析给定G=(V,E,P)，|V|=n，每个节点最多有n-1个邻居节点．贪心算法在执行过程中，判断非支配点是否被选为支配点的依据是当非支配点被选为支配点时，f的增量大小．f的增量大小根据非支配点的邻居节点当前的概率值计算．计算所有非支配点被选为支配点时f的增量，时间复杂度为O(n2)．在每一轮支配点的选择过程中，对所有非支配点根据其被选为支配点时f的增量大小进行排序，最小的时间复杂度为O(nlogn)，选择令f的增量最大对应的非支配点作为支配点．GAMP最多须挑选n个节点作为支配点，综上所述，贪心算法的时间复杂度为O(n3)．3 实验分析3.1　数据集数据集来自斯坦福大学收集的网络数据(http：//snap.stanford.edu/data/#socnets)，包含了若干个真实的社交网络实例．这些真实的网络实例被广泛地应用于验证各种算法[14-17]．这些网络均是不包含孤立点的无向无权图，在测试GAMP的求解质量之前，随机地为每条边赋予区间为[0,1]的权重值，并记录每个数据集中阈值α的取值范围(0,μ]．表1对这些网络进行具体描述．10.13245/j.hust.210213.T001表1实验所使用的社交网络图名称节点数/104边数/104平均度E-FBG-ATG-COG-GOG-NSG-POG-PFG-TVM-FBM-DEM-ENM-ESM-FRM-PTM-RUF-DSF-LS0.403 91.386 61.411 30.705 72.791 70.590 81.156 50.389 22.247 00.949 80.712 60.464 80.654 90.191 20.438 52.828 10.762 48.823 48.685 85.231 08.945 520.625 94.172 96.711 41.726 217.100 215.313 83.532 45.938 211.266 63.129 93.730 49.275 22.780 643.6912.527.4125.3514.7714.1211.608.8715.2232.249.9125.5534.4032.7317.016.557.293.2　GAMP的求解质量实验讨论的是算法所求的PDS中节点的个数，节点个数越少，表明算法所求的PDS质量越高．本研究采用算法所求的PDS节点个数|D|与图中总节点个数n的比值|D|/n来反映解的质量．对于同一个社交网络图，通过在区间(0,μ]下设置不同的α得到贪心解，实验结果如表2所示．10.13245/j.hust.210213.T002表2GAMP所求的PDS节点个数与总节点数的比值数据集α0.50.60.7E-FBG-ATG-COG-GOG-NSG-POG-PFG-TVM-FBM-DEM-ENM-ESM-FRM-PTM-RUF-DSF-LS4.1813.1821.7311.2814.6314.0519.9721.0716.358.7417.3910.118.118.3712.2219.4323.024.8313.4421.8011.5214.8914.3020.0421.3316.528.8417.5710.158.118.6312.2519.5723.055.8413.7621.9812.1715.2114.3020.1421.4816.749.0517.6410.208.448.7312.2919.7023.08%由表2可见：对于同一个社交网络图，当设定的α越大，每个节点须要被支配的概率越大，算法所求的PDS节点数也会更多．在22个真实社交网络图上，GAMP平均所求PDS的节点个数为总节点个数的14%～15%左右．本研究针对一种边的权重范围是[0,1]的无向带权图，提出了概率支配集的概念，在典型的社交网络图数据上分析了算法的实际效果．