鐘 昊,陳衛(wèi)東

(華南師范大學計算機學院，廣東 廣州 510631)

1 引言

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

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

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

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

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

2 問題描述

2.1 問題定義

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

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

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

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

2.2 問題的計算復雜性

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

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

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

(1)

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

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

證畢。

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ù)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)被廣泛地應用于圖的許多問題中，比如，圖的最小支配集問題及其若干變體[8 - 10]、圖的最小分辨集問題[11,12]和圖的最小邊度量維數(shù)問題等[13]。求解最小基數(shù)次模覆蓋問題的一個經(jīng)典算法：初始化設置一個集合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對應的勢函數(shù)f是一個整數(shù)型函數(shù)，那么算法的近似比為H(α)≤(1+lnα)，其中,H為調(diào)和級數(shù),α=maxu∈UΔuf(?)為勢函數(shù)f的最大邊際效益。

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

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

3.1 算法描述和近似比證明

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

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

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

在這種約定下，對于?v∈V，其tD(v)關于D是非增的，表示?v∈V被選為代表點或滿足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是一個第1種形式的SRS時，f1(D)=nη。

(3)若f1(D)0。

證明(1)顯然f1(?)=0。由tD(v)=max(0,η-maxu∈Ds(v,u))可知tD(v)關于D是非增的，那么f1(D)關于D是非減的。要證明f1(D)是次模函數(shù)，只需證明對于任意A?B?V和任意x∈(V-B)，勢函數(shù)f1滿足Δxf1(A)≥Δxf1(B)，由式(5)可計算式(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é)點u加入到集合D中，且節(jié)點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ù)，那么采用算法GAMCSC的貪心思想求解第1種形式的最小SRS問題，即算法GAMCSC的輸入為集合函數(shù)f1:2V→R+。本文將基于定理B證明算法GAMCSC是求解第1種形式的最小SRS問題的一個近似算法。

定理2當算法GAMCSC中的輸入為集合函數(shù)f1:2V→R+時，算法GAMCSC是求解第1種形式的最小SRS問題的一個近似算法，近似比為(1+ln((η+θ)/?))，其中θ表示任意節(jié)點和其他節(jié)點的最大相似度之和，即θ=maxu∈V∑v∈(V-{u})s(u,v),?表示任意節(jié)點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ù)。算法GAMCSC的輸入為集合函數(shù)f1:2V→R+，基于定理B可知，算法 GAMCSC的近似比為1+ln(α/β)，其中α和β分別為勢函數(shù)f1的最大邊際效益和最小邊際效益。

根據(jù)勢函數(shù)f1的次模性，即邊際效益遞減規(guī)律，可計算α=maxu∈VΔuf1(φ)≤(η+θ)，其中θ表示任意節(jié)點和其他節(jié)點的最大相似度之和，即θ=maxu∈V∑v∈(V-{u})s(u,v)。而β≥?，其中對于任意子集D?V,?表示任意節(jié)點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進行以下約定：

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

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

在這種約定下，對于?v∈V，其pD(v)關于D是非增的，表示?v∈V被選為代表點或滿足∑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是一個第2種形式的SRS時，f2(D)=nμ。

(3)若f2(D)0。

證明(1)顯然f2(?)=0。由pD(v)=max(0,μ-∑u∈Ds(v,u))可知pD(v)關于D是非增的，那么f2(D)關于D是非減的。要證明f2(D)是次模函數(shù)，只需證明對于任意A?B?V和任意x∈(V-B)，勢函數(shù)f2滿足Δxf2(A)≥Δxf2(B)，由式(11)可計算式(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é)點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ù)，那么采用算法GAMCSC的貪心思想求解第2種形式的最小SRS問題，即算法GAMCSC的輸入為集合函數(shù)f2:2V→R+。本文將基于定理B證明算法GAMCSC是求解第2種形式的最小SRS問題的一個近似算法。

定理3當算法GAMCSC中的輸入為集合函數(shù)f2:2V→R+時，算法GAMCSC是求解第2種形式的最小SRS問題的一個近似算法,近似比為(1+ln((μ+θ)/ρ))，其中θ表示任意節(jié)點和其他節(jié)點的最大相似度之和，即θ=maxu∈V∑v∈(V-{u})s(u,v),ρ表示任意節(jié)點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ù)。算法GAMCSC的輸入為集合函數(shù)f2:2V→R+，基于定理B可知，算法 GAMCSC的近似比為1+ln(α/β)，其中α和β分別為勢函數(shù)f2的最大邊際效益和最小邊際效益。

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

證畢。

3.2 算法復雜度

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

4 結(jié)束語

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