萬 科

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

0 引 言

隨著時代的發(fā)展，包括社交網(wǎng)絡(luò)在內(nèi)的各種各樣的復雜網(wǎng)絡(luò)逐漸興起，人們也越來越關(guān)注和研究這種類型的網(wǎng)絡(luò)。如果將復雜網(wǎng)絡(luò)建模成圖，圖中點代表對象，圖中的點與點之間的關(guān)系代表著網(wǎng)絡(luò)中對象之間的聯(lián)系。那么對復雜網(wǎng)絡(luò)的研究就變成了對圖的研究。近年來,支配集問題由于其在現(xiàn)實世界中的廣泛應(yīng)用而受到了關(guān)注[1-3]。隨之而來也有一系列支配集的變體，例如連通支配集、符號支配集、k-重支配集等，這些概念也被廣泛應(yīng)用于優(yōu)化理論、通訊網(wǎng)絡(luò)的設(shè)計與分析、社會科學、計算復雜性和算法設(shè)計等許多領(lǐng)域[3-4]。

最近，有關(guān)支配集的一種新的變體被提出來，即正影響支配集(Positive Influence Dominating Set, PIDS)[5-6]。通過找到社交網(wǎng)絡(luò)的正影響支配集就可以通過該集合對這個網(wǎng)絡(luò)起到一個積極的影響。例如想在一個社區(qū)推廣某種產(chǎn)品，如果對社區(qū)的每一個用戶逐一進行推薦，就會非常費時費力。但可以針對網(wǎng)絡(luò)中一小群有影響力的用戶，選定這些用戶可以在市場上產(chǎn)生最大的影響力覆蓋范圍，先向他們推薦讓其接受這項產(chǎn)品，然后通過他們就可以影響到整個社區(qū)。當然，要達到時間最短、代價更小，就必須使有影響力的用戶更少，即圖中的正影響支配集的點數(shù)更小。點數(shù)最小的正影響支配集叫最小正影響支配集(MPIDS)。求解最小正影響支配集已被證明是一個NP難問題[7-9]。

對于NP難度問題，不太可能有多項式時間的精確求解算法。因此，從實用性角度看通常采用啟發(fā)式算法近似求解，其中最簡單的啟發(fā)式算法是各種貪心類算法。貪心算法的基本思想是基于貪心勢函數(shù)作出判斷和選擇依次形成一個可行解向量作為貪心解輸出。其優(yōu)點是簡單、快速，但由于貪心勢函數(shù)是基于局部信息，因此形成的貪心解易過早陷入局部最優(yōu)，往往不盡人意。有一些策略可以增強貪心算法所得解的質(zhì)量，典型的增強策略包括Pilot方法、后悔貪心策略、迭代貪心策略和輪轉(zhuǎn)貪心策略等[10-17]。

Pilot方法是一種類似于博弈中向前看的策略。其基本思想是基于貪心勢函數(shù)選擇解向量X的當前第i分量值xi時，窮盡xi所有可能的情況，針對每一種可能情況向前繼續(xù)用貪心算法試探求出最終結(jié)果，其中導致最好結(jié)果的xi將作為解向量X的第i分量值。該方法產(chǎn)生的解理論上要好于原貪心算法解，但其時間代價較大[10]。

迭代貪心策略的基本思想是針對貪心算法獲得的貪心解，先隨機撤銷(Deconstruction)若干分量，然后對剩余的部分解向量用貪心算法進行重構(gòu)(Reconstruction)。這2個階段的過程(即撤消、重構(gòu))可進行多次迭代，最終將最好的結(jié)果輸出[11-12]。

后悔貪心策略的基本思想是，在貪心算法基于貪心勢函數(shù)逐次形成貪心解向量的過程中，允許對之前作出的解向量的分量進行適量修改(比如，如果發(fā)現(xiàn)對之前的分量作更換結(jié)果會更好就更換之前的分量)。對于集合覆蓋問題已從理論上證明了允許后悔的貪心算法比原貪心算法具有更好的近似性能。在后悔貪心算法最近應(yīng)用于無線傳感器網(wǎng)絡(luò)中干擾最小化問題上，實驗研究表明該算法可明顯提高現(xiàn)有貪心算法的精度[13]。

最近提出的輪轉(zhuǎn)貪心策略的基本思想是，先用貪心算法形成貪心解向量，保留前面一定比例的連續(xù)個解分量(即部分解向量)，然后依次對這個部分解向量去掉最前面的1個分量，并隨后用貪心算法補構(gòu)1個分量。這個過程可以反復多次。最后連續(xù)執(zhí)行貪心法直至形成一個可行解作為最終輸出結(jié)果。對于點覆蓋、集合覆蓋、MLST、隨機森林等問題，輪轉(zhuǎn)貪心算法可以在一定程度上提高貪心解的質(zhì)量且增加的計算時間較小[14-17]。

相較而言，這些增強策略中輪轉(zhuǎn)貪心策略在時間復雜度方面有明顯的優(yōu)勢，能保持時間復雜度幾乎不變的前提下有效增強貪心解的質(zhì)量。

關(guān)于最小正影響支配集問題，目前文獻中有2個典型的貪心算法，即Greedy-by-Wang和Greedy-by-Raei，根據(jù)來自不同視角的貪心勢函數(shù)反復添加最佳的節(jié)點進入正影響支配集。這2個算法在不同的數(shù)據(jù)集上各有一定的優(yōu)勢。本文將輪轉(zhuǎn)策略結(jié)合求解正影響支配集問題的2個貪心算法進行結(jié)合，提出求解最小正影響支配集的相應(yīng)的輪轉(zhuǎn)貪心算法，并通過實驗表明新算法比現(xiàn)有貪心算法所獲得解的質(zhì)量有一定程度上的提高，且增加的計算時間也在可接受范圍內(nèi)。

1 問題描述和相關(guān)算法

1.1 問題描述

社交網(wǎng)絡(luò)可用圖來表示，因此社交網(wǎng)絡(luò)的正影響支配集問題可通過圖的相關(guān)概念來描述。給定無向圖G=，其中V是節(jié)點集，E是邊集。對于任意點vV，用N(v)表示v的相鄰點的集合，即N(v)={uV|(v,u)E}；d(v)=|N(v)|為節(jié)點v的度。度為0的點稱為孤立點。本文考慮的圖都是無孤立點的無向圖。

定義1給定無向圖G=，如果圖G的一個點集DV滿足對于任意的vV，N(v)中至少有d(v)/2個點屬于D，則稱D為圖G的一個正影響支配集。圖G中點數(shù)最少的正影響支配集為圖G的最小正影響支配集。

為了便于描述正影響支配集的貪心算法，下面引入幾個概念。

定義2給定無向圖G=V,E，假設(shè)D為貪心算法當前選中的支配點集，對于任意點vV，定義其滿足度為相鄰點中為支配點的個數(shù)與其度的一半之差，記作Sat(v)，即：

Sat(v)=|DN(v)|-d(v)/2

對于圖中任意點vV，如果滿足度Sat(v)0，則稱點v為已滿足點，否則稱為未滿足點。顯然，如果圖中所有點均是已滿足點，則D為圖的一個正影響支配集。

定義3給定無向圖G=V,E，假設(shè)D為貪心算法當前選中的支配點集，對于任意非支配點vV-D，定義其覆蓋面為鄰域N(v)中未滿足點的個數(shù)，記作Cov(v)，即：

Cov(v)=|uN(v)|Sat(v)<0|

定義4給定無向圖G=V,E，假設(shè)D為貪心算法當前選中的支配點集，對于任意非支配點vV-D，定義其期盼度為鄰域N(v)中未滿足點的滿足度絕對值之和，記作Exp(v)，即：

Exp(v)=uN(v)Sat(u)<0|Sat(u)|

1.2 相關(guān)算法

求解最小正支配集問題有2個典型的貪心算法，它們基于不同的視角采用不同的貪心勢函數(shù)來依次選取最佳節(jié)點加入到當前支配點集中，直到支配點集成為一個正影響支配集。其中一個貪心算法的貪心勢函數(shù)是基于覆蓋面Cov(·)[18]，本文稱作算法Greedy-by-Wang，另一個貪心算法的貪心勢函數(shù)是基于期盼度Exp(·)[19]，本文稱作算法Greedy-by-Raei。

算法Greedy-by-Wang的思想比較直觀自然，基本思路是先將圖中全部點初始化為非支配點和未滿足點，選取一個當前覆蓋面Cov(·)最大的點加入正影響支配集中，然后更新每個點的覆蓋面。重復此步驟直到圖中所有節(jié)點都為已滿足點為止。算法Greedy-by-Raei的基本思想是先將圖中全部點初始化為非支配點和未滿足點，選取一個當前期盼度Exp(·)最大的點加入到正影響支配集中，然后更新每個點的期盼度。重復此步驟，直到圖中所有節(jié)點都為已滿足點為止。這2個算法的時間復雜度均為O(n3)，其中n=|V|。實驗研究表明，與算法Greedy-by-Wang相比，算法Greedy-by-Raei通常求得的解的質(zhì)量有一定優(yōu)勢，但在一些平均度比較大的實例圖中效果較差[20-21]。

鑒于算法Greedy-by-Wang和算法Greedy-by-Raei各有優(yōu)勢，將這兩者進行融合得到一種混合貪心算法Hybrid-Greedy，其基本思想是在執(zhí)行貪心算法Greedy-by-Wang的過程中，如果當前覆蓋面Cov(·)取最大值的點有多個，則選擇其期盼度最大點作為支配點。算法Hybrid-Greedy的時間復雜度仍為O(n3)，但其實際運行時間約等于參與融合的這2種貪心算法的運行時間之和。實驗研究表明，Hybrid-Greedy能融合2種貪心算法的優(yōu)勢，在大多數(shù)測試算例中所得解的質(zhì)量有明顯提高[21]。

2 輪轉(zhuǎn)貪心算法

2.1 輪轉(zhuǎn)貪心策略

貪心算法通常都是基于選定的貪心勢函數(shù)依次構(gòu)建出貪心解向量的每個分量。在這個過程中，每一步都要根據(jù)貪心勢函數(shù)做出貪心選擇。盡管這種貪心選擇都是基于局部信息的，但在形成貪心解向量的早期，由于依賴的信息少，比較盲目，而在后期因為貪心解向量的前面很多分量已經(jīng)選定，會使得此時做出的貪心選擇往往比較精準?；谶@一洞察，貪心解向量的前面分量的構(gòu)造對最終獲得好的貪心解向量非常關(guān)鍵[14]。

輪轉(zhuǎn)貪心策略旨在通過精心構(gòu)造好一個貪心解向量的前面部分來最終獲得一個高質(zhì)量的貪心解，它由3個階段組成。第1階段，根據(jù)貪心算法構(gòu)造出一個貪心解向量S=(v1,v2,…,vk,…,vt)。第2階段，先將該向量尾部β|S|個分量舍棄后獲得當前的部分解向量R=(v1,v2,…,vk)，然后對該當前部分解向量迭代如下操作α|S|次：去掉頭部(即當前解最前面)的1個分量，并使用貪心算法構(gòu)造出1個分量放在尾部(即當前解最后面)。第3階段，根據(jù)迭代后獲得的部分解向量R，繼續(xù)使用貪心算法構(gòu)造出一個完整的可行解R作為輪轉(zhuǎn)算法的最終結(jié)果。輪轉(zhuǎn)貪心策略的直觀示意圖見圖1。

圖1 輪轉(zhuǎn)貪心策略示意圖(假設(shè)|S|=t,α=1,β=(tk)/t)

該策略中需要指定參數(shù)α和β，其中α用于控制輪轉(zhuǎn)次數(shù)，β是要舍棄貪心解向量的百分比。實際應(yīng)用中可根據(jù)期望獲得解的質(zhì)量和運行時間來合理選擇。

2.2 輪轉(zhuǎn)貪心算法

基于前述討論，輪轉(zhuǎn)貪心算法是在基本貪心算法產(chǎn)生了完整的貪心解向量(可視作隊列結(jié)構(gòu))之后，再以該解向量的前面部分為出發(fā)點，多次輪轉(zhuǎn)進行刪除、插入操作。下面以算法Greedy-by-Wang為基本貪心算法，描述對應(yīng)的輪轉(zhuǎn)貪心算法，具體實現(xiàn)過程見算法1。

算法1Caro-Greedy-by-Wang

Input:無向圖G=V,E,參數(shù)α和β

Output:G的一個正影響支配集

Begin

1.由算法Greedy-by-Wang產(chǎn)生解向量S

2.RS中去掉后面β|S|個分量

3.Fori=1 Toα|S| Do

4.刪除R中排在最前的1個分量

5.用算法Greedy-by-Wang在R后添加1個分量

6.End For

7.用算法Greedy-by-Wang在R后依次添加分量直到R為一可行解

8.ReturnR

End

根據(jù)算法1易知，如果將基本貪心算法換為算法Greedy-by-Raei，則得到其相應(yīng)的輪轉(zhuǎn)貪心算法，記作Caro-Greedy-by-Raei。

下面以上述算法為例來分析輪轉(zhuǎn)貪心算法的時間復雜度。設(shè)圖G中點數(shù)為n=|V|，貪心算法Greedy-by-Wang用時間t(n)求得貪心解向量S。求得貪心解向量S的每個分量的平均時間為t(n)/|S|。從中容易看出，Caro-Greedy-by-Wang運行中總共做了添加解向量分量的操作次數(shù)為|S|+α|S|+β|S|=(1+α+β)|S|<(2+α)|S|，故總時間不超過(2+α)t(n)。由于α通常是一個很小的常數(shù)，故Caro-Greedy-by-Wang的時間復雜度與算法Greedy-by-Wang相同，均為t(n)，而其實際運行時間不超過算法Greedy-by-Wang實際運行時間的一個常數(shù)倍，即(2+α)倍。由此可見，輪轉(zhuǎn)貪心算法的時間復雜度與其基本的貪心算法相同。

輪轉(zhuǎn)貪心算法除了開始需要運行貪心算法得到貪心解作為出發(fā)點，之后只產(chǎn)生問題的唯一一個完整可行解并輸出。這一點與其他增強型貪心算法不同，比如迭代貪心、Pilot貪心等。也正是這一點導致輪轉(zhuǎn)貪心算法的時間復雜度與其基本貪心算法相同，并成為輪轉(zhuǎn)貪心算法相比其他增強型貪心算法的一大優(yōu)勢。

3 實驗結(jié)果及分析

3.1 實驗方法和實驗數(shù)據(jù)

本節(jié)通過實驗來評估輪轉(zhuǎn)貪心算法的性能，包括實際運行時間和解的質(zhì)量。實驗中將2種輪轉(zhuǎn)貪心算法Caro-Greedy-by-Wang和Caro-Greedy-by-Raei分別與其基本貪心算法(算法Greedy-by-Wang和算法Greedy-by-Raei)作比較。此外，還將2種輪轉(zhuǎn)貪心算法與吸收2種基本貪心算法優(yōu)勢的混合貪心算法Hybrid-Greedy做比較。所采用的數(shù)據(jù)是社交網(wǎng)絡(luò)中的真實實例，包括來自斯坦福大學的大型網(wǎng)絡(luò)數(shù)據(jù)集(http://snap.stanford.edu/data/)中的7個無向圖類型的社交網(wǎng)絡(luò)實例(前7個算例)，以及2個著名社交網(wǎng)絡(luò)實例(其中ncstrlwg2是科研合作網(wǎng)，數(shù)據(jù)來自文獻[22]，actors-data是演員合作網(wǎng)，數(shù)據(jù)來自文獻[23])。由于本文要求圖中沒有孤立點，因此需要對算例做預處理，移去孤立點或?qū)⒐铝Ⅻc隨機連接到某個其他節(jié)點來確保圖中存在正影響支配集。表1給出了這些測試算例的描述。

表1 測試算例描述

3.2 實驗結(jié)果及分析

算法用C語言編程實現(xiàn)，實驗環(huán)境為：PC機處理器為i7-7700，主頻為3.60 GHz，內(nèi)存為8 GB和64位的Win10操作系統(tǒng)。

首先本文測試了輪轉(zhuǎn)算法中的2個參數(shù)α與β的不同取值對輪轉(zhuǎn)貪心算法解質(zhì)量的影響。表2中是在算例CA-HepPh上輪轉(zhuǎn)貪心算法Caro-Greedy-by-Wang對α與β取不同值的實驗結(jié)果，其中α分別取值為1、2、3、4、5、6，β分別取值為5%、10%、15%、20%。表2中的數(shù)字代表最小正影響支配集包含點的個數(shù)，數(shù)字越小說明點的個數(shù)越少，解的質(zhì)量越高。

表2 Caro-Greedy-by-Wang中參數(shù)α、β取不同值時在算例CA-HepPh上的實驗結(jié)果

算例CA-HepPh用算法Greedy-By-Wang的實驗結(jié)果是4892，而從表2可看出Caro-Greedy-by-Wang在α較小時，隨著α與β的增大，解質(zhì)量有提高；當α=4,β=15%時達到峰值，之后解質(zhì)量就慢慢下降。

基于表2的結(jié)果，在隨后的實驗中，對2種輪轉(zhuǎn)貪心算法中α取值分別為1、2、3、4、5、6，β取值分別為5%、10%、15%、20%時進行了實驗，然后取平均值，實驗結(jié)果見表3～表5。表中的PIDS代表求到的最小正支配集的點數(shù)，Time代表運行的時間。

從表3和表4可以看出，Caro-Greedy-by-Wang相比算法Greedy-by-Wang，Caro-Greedy-by-Raei相比算法Greedy-by-Raei，所求的最小正支配集的點數(shù)更少，解的質(zhì)量上均有不同程度的提高，而增加的計算時間在可接受范圍內(nèi)，這說明輪轉(zhuǎn)貪心算法能夠克服基本貪心算法執(zhí)行早期中貪心選擇的一些盲目性。

從表5可以看出，輪轉(zhuǎn)貪心算法與混合貪心算法相比，解質(zhì)量也有一定程度上的提高，而運行時間差別并不是很大，在可接受的范圍內(nèi)。這進一步說明了，輪轉(zhuǎn)貪心策略在一定程度上能糾正基本貪心算法執(zhí)行早期所作出的一些錯誤選擇。

表3 算法Greedy-by-Raei與Caro-Greedy-by-Raei在各測試算例上的實驗結(jié)果

表4 算法Greedy-by-Wang與Caro-Greedy-by-Wang在各測試算例上的實驗結(jié)果

表5 輪轉(zhuǎn)貪心算法與Hybrid-Greedy的實驗結(jié)果

4 結(jié)束語

在求最小正支配集問題中，本文基于現(xiàn)有的2個貪心算法，結(jié)合輪轉(zhuǎn)貪心策略，分別提出了相應(yīng)的輪轉(zhuǎn)貪心算法。與原貪心算法比較，輪轉(zhuǎn)貪心算法可在一定程度上提高解的質(zhì)量且增加的計算時間較小。

未來工作中將通過廣泛實驗探究輪轉(zhuǎn)貪心算法的機理，并探究輪轉(zhuǎn)貪心算法如何與其他啟發(fā)式算法進行融合來求解社交網(wǎng)絡(luò)中包括最小正影響支配集問題在內(nèi)的各種典型問題。