一般圖中的最小概要表示集問題*

鐘 昊,陳衛(wèi)東

(華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣東 廣州 510631)

1 引言

給定一個對象集合，任意2個對象之間的相似度越大，表明其中一個對象越能夠在一定程度上表示另一個對象。通常根據(jù)對象之間的相似度從對象集合中選擇一些對象，令這些對象能夠概要表示整個對象集合。比如，從知識圖譜的摘要模式集中找出一些摘要模式來概要表示整個知識圖譜[1]，從文本的句子集合中找出一些句子來概要表示整個文本[2 - 4]。

在一般圖中，通?；趫D的拓?fù)浣Y(jié)構(gòu)來刻畫任意2個節(jié)點(diǎn)之間的相似度。例如，任意2個節(jié)點(diǎn)共同位于圖中越多數(shù)量的增廣路徑上，節(jié)點(diǎn)的相似度越高[5]；任意2個節(jié)點(diǎn)之間的連邊權(quán)重占這2個節(jié)點(diǎn)的所有連邊權(quán)重的比值越大，節(jié)點(diǎn)的相似度越高[6]；任意2個節(jié)點(diǎn)的共同鄰居節(jié)點(diǎn)數(shù)越多，節(jié)點(diǎn)的相似度越高[7]。基于節(jié)點(diǎn)的相似度計(jì)算方法，從圖中選擇一些節(jié)點(diǎn)來概要表示一個圖，被選擇的節(jié)點(diǎn)稱為代表點(diǎn)。由代表點(diǎn)構(gòu)成的集合滿足一些特定條件時，稱該集合為概要表示集SRS(Summary Representing Sets)。 本文定義了表示集的2種形式，具體描述為：任意一個由代表點(diǎn)構(gòu)成的集合被稱為概要表示集，當(dāng)且僅當(dāng)：

(1)圖中任意節(jié)點(diǎn)要么屬于代表點(diǎn)，要么與該集合中某個代表點(diǎn)的相似度大于或等于給定閾值η∈(0,1)。

(2)圖中任意節(jié)點(diǎn)要么屬于代表點(diǎn)，要么與該集合中所有代表點(diǎn)的相似度之和大于或等于給定的閾值μ∈(0,+∞)。

從圖中尋找最少節(jié)點(diǎn)數(shù)的概要表示集稱為最小概要表示集問題，本文對最小SRS問題進(jìn)行了研究，針對2種形式的最小SRS問題分別進(jìn)行了形式化的描述，證明任一形式的最小SRS問題都是NP難問題。針對2種形式的最小SRS問題，分別基于次模函數(shù)提出一個貪心近似算法進(jìn)行求解。

2 問題描述

2.1 問題定義

給定一個無向圖G=(V,E)，其中,V表示節(jié)點(diǎn)集，E表示邊集。圖G上的一個集合函數(shù)s:2V×V→[0,1]是任意2個節(jié)點(diǎn)的相似度函數(shù)。在圖G中，節(jié)點(diǎn)的個數(shù)n=|V|，邊的條數(shù)m=|E|。給定一個代表點(diǎn)組成的集合D，任意節(jié)點(diǎn)v∈V和子集D中任意代表點(diǎn)的最大相似度為maxu∈Ds(v,u)，和子集D中所有代表點(diǎn)的相似度之和為∑u∈Ds(v,u)。 顯然對于任意節(jié)點(diǎn)v∈V,maxu∈Ds(v,u)和∑u∈Ds(v,u)關(guān)于集合D都是非減的。 下面對最小SRS問題的2種形式進(jìn)行描述。

(1)給定閾值η∈(0,1)，當(dāng)任意節(jié)點(diǎn)集合D?V能夠使得?v∈V滿足v∈D或maxu∈Ds(v,u)≥η，那么稱集合D為第1種形式的SRS。 第1種形式的最小SRS問題可描述為：從節(jié)點(diǎn)集合V中找出最少數(shù)量的節(jié)點(diǎn)構(gòu)成集合D，使得?v∈V滿足v∈D或maxu∈Ds(v,u)≥η。

給定閾值μ∈(0,+∞)，當(dāng)任意節(jié)點(diǎn)集合D?V能夠使得?v∈V滿足v∈D或∑u∈Ds(v,u)≥μ，那么稱集合D為第2種形式的SRS。 第2種形式的最小SRS問題可描述為：從節(jié)點(diǎn)集合V中找出最少數(shù)量的節(jié)點(diǎn)構(gòu)成集合D，使得?v∈V滿足v∈D或∑u∈Ds(v,u)≥μ。

值得一提的是，對于第1種形式的最小SRS問題，當(dāng)給定的閾值η過大時，對于任意節(jié)點(diǎn)v∈V，若其滿足不等式maxu∈(V-{v})s(v,u)<η，表示節(jié)點(diǎn)v只能被選為代表點(diǎn)。那么設(shè)置閾值η過大時可能存在所有節(jié)點(diǎn)都只能被選為代表點(diǎn)的情況。為了避免出現(xiàn)上述情況，通常設(shè)定閾值η∈(0,minv∈Vmaxu∈(V-{v})s(v,u)]。對于第2種形式的最小SRS問題，當(dāng)給定的閾值μ過大時，對于任意節(jié)點(diǎn)v∈V，若其滿足不等式∑u∈(V-{v})s(v,u)<μ，表示節(jié)點(diǎn)v只能被選為代表點(diǎn)。那么設(shè)置閾值μ過大時可能存在所有節(jié)點(diǎn)都只能被選為代表點(diǎn)的情況。同理，為了避免出現(xiàn)上述情況，通常設(shè)定閾值μ∈(0,minv∈V∑u∈(V-{v})s(v,u)]。

2.2 問題的計(jì)算復(fù)雜性

定理1求解最小SRS問題是NP難的。

證明由于最小支配集問題是NP難問題，下面只需證明可將最小支配集問題歸約到最小SRS問題。

首先，給出最小支配集問題到第1種形式的最小SRS問題的歸約證明。給定任意無向圖G=(V,E),設(shè)定閾值η=0.5，構(gòu)造一個節(jié)點(diǎn)相似度函數(shù)s:2V×V→[0,1]如式(1)所示：

(1)

這個構(gòu)造顯然能在O(n2)的多項(xiàng)式時間內(nèi)完成，且D?V是圖G的一個支配集當(dāng)且僅當(dāng)D是圖G在該相似度函數(shù)s下的一個第1種形式的SRS。即，最小支配集問題的任一實(shí)例可多項(xiàng)式歸約為第1種形式的最小SRS問題的實(shí)例求解。

其次，給出最小支配集問題到第2種形式的最小SRS問題的歸約證明。注意，在上述歸約中，如果設(shè)定閾值μ=0.5，則D?V是圖G的一個支配集圖當(dāng)且僅當(dāng)D是圖G在該相似度函數(shù)s下的一個第2種形式的SRS。即，最小支配集問題的任一實(shí)例可多項(xiàng)式歸約為第2種形式的最小SRS問題的實(shí)例求解。

證畢。

3 貪心近似算法

在介紹求解最小SRS問題的貪心近似算法之前，先回顧一下組合優(yōu)化中NP難的最小基數(shù)次模覆蓋問題及其貪心近似算法。給定一個有限簇集合U和一個集合函數(shù)f:2U→R+，對于任意子集S?U，元素i∈(U-S)在S上的邊際效益用Δif(S)表示，定義如式(2)所示:

Δif(S)=f(S∪{i})-f(S)

(2)

函數(shù)f是次模函數(shù)，是指對于任意A?B?U和任意i∈(U-B)，函數(shù)f滿足式(3):

Δif(A)≥Δif(B)

(3)

設(shè)函數(shù)f是正規(guī)化的(f(?)=0)、單調(diào)的(任意A?B?U滿足f(B)≥f(A))和次模的，最小基數(shù)次模覆蓋問題可描述為：找出基數(shù)最小的子集S?U使得f(S)=f(U)，形式化表示如式(4)所示:

minS?U{|S|:f(S)=f(U)}

(4)

最小基數(shù)次模覆蓋問題及其近似求解算法已經(jīng)被廣泛地應(yīng)用于圖的許多問題中，比如，圖的最小支配集問題及其若干變體[8 - 10]、圖的最小分辨集問題[11,12]和圖的最小邊度量維數(shù)問題等[13]。求解最小基數(shù)次模覆蓋問題的一個經(jīng)典算法：初始化設(shè)置一個集合S為空集，依次從U-S中選擇使Δif(S)最大的元素i加入到集合S中，直至f(S)=f(U)。求解最小基數(shù)次模覆蓋問題的貪心算法GAMCSC(Greedy Algorithm for the Minimum Cardinality Submodular Cover problem)的偽代碼如算法1所示：

算法1GAMCSC算法

輸入:有限簇集合U和集合函數(shù)f:2U→R+。

輸出:最小基數(shù)次模覆蓋問題的一個解S。

S←?;

Whilef(S)

Chooseu∈(U-S) to maximizef(S∪{u});

SetS←S∪{u};

OutputD;

算法GAMCSC已經(jīng)被證明是近似算法[14,15]。給出2個已有的定理。

定理A若算法GAMCSC對應(yīng)的勢函數(shù)f是一個整數(shù)型函數(shù)，那么算法的近似比為H(α)≤(1+lnα)，其中,H為調(diào)和級數(shù),α=maxu∈UΔuf(?)為勢函數(shù)f的最大邊際效益。

定理B若算法GAMCSC對應(yīng)的勢函數(shù)f是一個實(shí)數(shù)型函數(shù)，那么算法的近似比為：(1)1+ln(α/β)，其中β為勢函數(shù)f的最小邊際效益;(2)1+ln(f(U)/opt)，當(dāng)β≥1，其中opt為最小基數(shù)次模覆蓋問題的最優(yōu)解基數(shù)。

上述定理將用于證明本文提出的求解最小概要表示集問題的貪心算法的近似比。

3.1 算法描述和近似比證明

在介紹求解第1種形式的最小SRS問題的貪心近似算法前，本文首先定義一個函數(shù)t:2V→R+并對于任意子集D?V進(jìn)行以下約定：

(1)對于?v∈D，令tD(v)=0;

(2)對于?v∈(V-D)，令tD(v)=max(0,η-maxu∈Ds(v,u))。

在這種約定下，對于?v∈V，其tD(v)關(guān)于D是非增的，表示?v∈V被選為代表點(diǎn)或滿足maxu∈Ds(v,u)≥η時都有tD(v)=0。緊接著，對于任意子集D?V，本文考慮一個勢函數(shù)f1:2V→R+如式(5)所示:

(5)

引理1勢函數(shù)f1(D)的一些性質(zhì)：

(1)f1(D)是正規(guī)化的、單調(diào)非減的次模函數(shù)。

(2)當(dāng)D是一個第1種形式的SRS時，f1(D)=nη。

(3)若f1(D)0。

證明(1)顯然f1(?)=0。由tD(v)=max(0,η-maxu∈Ds(v,u))可知tD(v)關(guān)于D是非增的，那么f1(D)關(guān)于D是非減的。要證明f1(D)是次模函數(shù)，只需證明對于任意A?B?V和任意x∈(V-B)，勢函數(shù)f1滿足Δxf1(A)≥Δxf1(B)，由式(5)可計(jì)算式(6)和式(7)：

(6)

(7)

顯然tA(x)≥tB(x)以及(V-A)?(V-B)，則只需證明(tA(v)-tA∪{x}(v))≥(tB(v)-tB∪{x}(v))如下：

若tA∪{x}(v)>0且tB∪{x}(v)>0，則式(8)成立：

tA(v)-tA∪{x}(v)=

max(0,s(x,v)-maxu∈As(u,v))≥

max(0,s(x,v)-maxu∈Bs(u,v))=

tB(v)-tB∪{x}(v)

(8)

若tA∪{x}(v)>0且tB∪{x}(v)=0，則式(9)成立：

tA(v)-tA∪{x}(v)=

max(0,s(x,v)-maxu∈As(u,v))≥

max(0,s(x,v)-maxu∈Bs(u,v))≥

max(0,η-maxu∈Bs(u,v))=

tB(v)-tB∪{x}(v)

(9)

若tA∪{x}(v)=0，則式(10)成立：

tA(v)-tA∪{x}(v)=

max(0,η-maxu∈As(u,v))≥

max(0,η-maxu∈Bs(u,v))=

tB(v)-tB∪{x}(v)

(10)

綜上所述，Δxf1(A)≥Δxf1(B)是成立的。

(2)若D是一個第1種形式的SRS，那么?v∈(V-D)都滿足tD(v)=0，即f1(D)=nη。若D不是一個第1種形式的SRS，那么存在v∈(V-D)滿足tD(v)>0，即f1(D)

(3)若f1(D)0，此時若從V-D中選擇節(jié)點(diǎn)u加入到集合D中，且節(jié)點(diǎn)u滿足s(u,v)>maxw∈Ds(w,v)，那么tD∪{u}(v)f1(D)。

證畢。

對于任意子集D?V，引理1證明了勢函數(shù)f1(D)是一個正規(guī)化的、非減的次模函數(shù)，且勢函數(shù)f1(D)還是一個實(shí)數(shù)型函數(shù)，那么采用算法GAMCSC的貪心思想求解第1種形式的最小SRS問題，即算法GAMCSC的輸入為集合函數(shù)f1:2V→R+。本文將基于定理B證明算法GAMCSC是求解第1種形式的最小SRS問題的一個近似算法。

定理2當(dāng)算法GAMCSC中的輸入為集合函數(shù)f1:2V→R+時，算法GAMCSC是求解第1種形式的最小SRS問題的一個近似算法，近似比為(1+ln((η+θ)/?))，其中θ表示任意節(jié)點(diǎn)和其他節(jié)點(diǎn)的最大相似度之和，即θ=maxu∈V∑v∈(V-{u})s(u,v),?表示任意節(jié)點(diǎn)v∈V在滿足tD(v)>0的前提下最小的tD(v)值，即?=minv∈V,D?V{tD(v)|tD(v)>0}。

證明引理1證明了勢函數(shù)f1(D)是一個正規(guī)化的、非減的次模函數(shù)，且勢函數(shù)f1(D)還是一個實(shí)數(shù)型函數(shù)。算法GAMCSC的輸入為集合函數(shù)f1:2V→R+，基于定理B可知，算法 GAMCSC的近似比為1+ln(α/β)，其中α和β分別為勢函數(shù)f1的最大邊際效益和最小邊際效益。

根據(jù)勢函數(shù)f1的次模性，即邊際效益遞減規(guī)律，可計(jì)算α=maxu∈VΔuf1(φ)≤(η+θ)，其中θ表示任意節(jié)點(diǎn)和其他節(jié)點(diǎn)的最大相似度之和，即θ=maxu∈V∑v∈(V-{u})s(u,v)。而β≥?，其中對于任意子集D?V,?表示任意節(jié)點(diǎn)v∈V在滿足tD(v)>0的前提下最小的tD(v)值，即?=minv∈V,D?V{tD(v)|tD(v)>0}。綜上所述，算法GAMCSC是求解第1種形式的最小SRS問題的一個近似算法,近似比為(1+ln((η+θ)/?))。

證畢。

在介紹求解第2種形式的最小SRS問題的貪心近似算法前，本文首先定義一個函數(shù)p:2V→R+并對于任意子集D?V進(jìn)行以下約定：

(1)對于?v∈D，令pD(v)=0;

(2)對于?v∈(V-D)，令pD(v)=max(0,μ-∑u∈Ds(v,u))。

在這種約定下，對于?v∈V，其pD(v)關(guān)于D是非增的，表示?v∈V被選為代表點(diǎn)或滿足∑u∈Ds(v,u)≥μ時都有pD(v)=0。接下來，對于任意子集D?V，本文考慮一個勢函數(shù)f2:2V→R+如式(11)所示:

(11)

引理2勢函數(shù)f2(D)的一些性質(zhì)：

(1)f2(D)是正規(guī)化的、單調(diào)非減的次模函數(shù)。

(2)當(dāng)D是一個第2種形式的SRS時，f2(D)=nμ。

(3)若f2(D)0。

證明(1)顯然f2(?)=0。由pD(v)=max(0,μ-∑u∈Ds(v,u))可知pD(v)關(guān)于D是非增的，那么f2(D)關(guān)于D是非減的。要證明f2(D)是次模函數(shù)，只需證明對于任意A?B?V和任意x∈(V-B)，勢函數(shù)f2滿足Δxf2(A)≥Δxf2(B)，由式(11)可計(jì)算式(12)和式(13)：

(12)

(13)

顯然pA(x)≥pB(x)以及(V-A)?(V-B)，則只需證明(pA(v)-pA∪{x}(v))≥(pB(v)-pB∪{x}(v))如下：

若pA∪{x}(v)>0且pB∪{x}(v)>0，則式(14)成立：

pA(v)-pA∪{x}(v)=s(x,v)=

pB(v)-pB∪{x}(v)

(14)

若pA∪{x}(v)>0且pB∪{x}(v)=0，則式(15)成立：

pA(v)-pA∪{x}(v)=s(x,v)≥

max(0,μ-∑u∈Bs(u,v))=pB(v)-pB∪{x}(v)

(15)

若pA∪{x}(v)=0，則式(16)成立：

pA(v)-pA∪{x}(v)=max(0,μ-∑u∈As(u,v))≥

max(0,μ-∑u∈Bs(u,v))=pB(v)-pB∪{x}(v)

(16)

綜上所述，Δxf2(A)≥Δxf2(B)是成立的。

(2)若D是一個第2種形式的SRS，那么?v∈(V-D)都滿足pD(v)=0，即f2(D)=nμ。若D不是一個第2種形式的SRS，那么存在v∈(V-D)滿足pD(v)>0，即f2(D)

(3)若f2(D)0，此時若從V-D中選擇節(jié)點(diǎn)u加入到集合D中，那么∑w∈(D∪{u})s(w,v)>∑w∈Ds(w,v)，即pD∪{u}(v)f2(D)。

證畢。

對于任意子集D?V，引理2證明了勢函數(shù)f2(D)是一個正規(guī)化的、非減的次模函數(shù)，并且勢函數(shù)f2(D)還是一個實(shí)數(shù)型函數(shù)，那么采用算法GAMCSC的貪心思想求解第2種形式的最小SRS問題，即算法GAMCSC的輸入為集合函數(shù)f2:2V→R+。本文將基于定理B證明算法GAMCSC是求解第2種形式的最小SRS問題的一個近似算法。

定理3當(dāng)算法GAMCSC中的輸入為集合函數(shù)f2:2V→R+時，算法GAMCSC是求解第2種形式的最小SRS問題的一個近似算法,近似比為(1+ln((μ+θ)/ρ))，其中θ表示任意節(jié)點(diǎn)和其他節(jié)點(diǎn)的最大相似度之和，即θ=maxu∈V∑v∈(V-{u})s(u,v),ρ表示任意節(jié)點(diǎn)v∈V在滿足pD(v)>0的前提下最小的pD(v)值，即ρ=minv∈V,D?V{pD(v)|pD(v)>0}。

證明引理2證明了勢函數(shù)f2(D)是一個正規(guī)化的、非減的次模函數(shù)，且勢函數(shù)f2(D) 還是一個實(shí)數(shù)型函數(shù)。算法GAMCSC的輸入為集合函數(shù)f2:2V→R+，基于定理B可知，算法 GAMCSC的近似比為1+ln(α/β)，其中α和β分別為勢函數(shù)f2的最大邊際效益和最小邊際效益。

根據(jù)勢函數(shù)f2的次模性，即邊際效益遞減規(guī)律，可計(jì)算α=maxu∈VΔuf2(?)≤(μ+θ)，其中θ表示任意節(jié)點(diǎn)和其他節(jié)點(diǎn)的最大相似度之和，即θ=maxu∈V∑v∈(V-{u})s(u,v)。而β≥?，其中對于任意子集D?V,ρ表示任意節(jié)點(diǎn)v∈V在滿足pD(v)>0的前提下最小的pD(v)值，即ρ=minv∈V,D?V{pD(v)|pD(v)>0}。 綜上所述，算法GAMCSC是求解第2種形式的最小SRS問題的一個近似算法，近似比為(1+ln((μ+θ)/ρ))。

證畢。

3.2 算法復(fù)雜度

給定一個無向帶權(quán)圖G=(V,E),|V|=n。 假設(shè)任意2個節(jié)點(diǎn)的相似度已知的前提下，計(jì)算任一節(jié)點(diǎn)與其他節(jié)點(diǎn)的相似度之和的時間復(fù)雜度為O(n)，那么計(jì)算所有未被選為代表點(diǎn)的節(jié)點(diǎn)與其他節(jié)點(diǎn)的相似度之和的時間復(fù)雜度為O(n2)。 在每一輪代表點(diǎn)的選擇過程中，根據(jù)被選為代表點(diǎn)時節(jié)點(diǎn)勢函數(shù)的增量大小排序所有非代表點(diǎn)，最小的時間復(fù)雜度為O(nlogn)，選擇令勢函數(shù)f的增量最大對應(yīng)的非代表點(diǎn)作為代表點(diǎn)。貪心算法GAMCSC最多需要挑選n個節(jié)點(diǎn)作為代表點(diǎn)，綜上所述，貪心算法GAMCSC的時間復(fù)雜度為O(n3)。

4 結(jié)束語

本文基于節(jié)點(diǎn)相似度提出了概要表示集的概念，并分為2種形式進(jìn)行討論。本文證明了求解任一形式的最小概要表示集問題都是NP難問題，這表明不太可能存在多項(xiàng)式時間內(nèi)求解該問題的精確算法。本文基于次模函數(shù)提出了2個時間復(fù)雜度為O(n3)的貪心近似算法，用于求解2種形式的最小概要表示集問題。