一種高效的動(dòng)態(tài)圖最大加權(quán)獨(dú)立集求解算法

祁才云，周軍鋒，杜 明

(東華大學(xué)，上海 200000)

0 引言

圖是用來(lái)描述個(gè)體之間相互聯(lián)系的一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)[1]。在現(xiàn)實(shí)世界中，可將網(wǎng)絡(luò)[2-3]、計(jì)算機(jī)視覺(jué)[4-5]、社交網(wǎng)絡(luò)[6-7]、無(wú)線傳感網(wǎng)絡(luò)[8]等數(shù)據(jù)抽象為圖模型。在實(shí)際生活中，最大加權(quán)獨(dú)立集問(wèn)題[9-14]廣泛應(yīng)用于解決各項(xiàng)問(wèn)題，例如分配分布式系統(tǒng)中的資源、避免無(wú)線網(wǎng)絡(luò)中的多址信道干擾等。

動(dòng)態(tài)圖[15-17]是指會(huì)隨時(shí)間發(fā)生變化的圖數(shù)據(jù)。例如，在現(xiàn)實(shí)世界中，個(gè)體的數(shù)量或個(gè)體間的聯(lián)系發(fā)生變化時(shí)，圖也相應(yīng)的發(fā)生著變化，可以把這種圖的變化抽象為動(dòng)態(tài)圖。隨著數(shù)據(jù)的快速變化，在動(dòng)態(tài)圖上獲取有價(jià)值的信息也吸引了大量研究者的關(guān)注。在分布式系統(tǒng)中，當(dāng)系統(tǒng)中計(jì)算機(jī)的數(shù)量、計(jì)算機(jī)間的干擾頻繁發(fā)生變化時(shí)，可以不用考慮整個(gè)系統(tǒng)，只需單獨(dú)觀察發(fā)生變化的計(jì)算機(jī)或計(jì)算機(jī)間的干擾，快速搜索圖的最大加權(quán)獨(dú)立集，進(jìn)而減少數(shù)據(jù)傳輸過(guò)程中數(shù)據(jù)丟失。在無(wú)線網(wǎng)絡(luò)中，用戶的數(shù)量以及信號(hào)傳播中的干擾會(huì)隨時(shí)發(fā)生變化，在這些變化發(fā)生后，需要快速獲取該圖的最大加權(quán)獨(dú)立集，進(jìn)而避免發(fā)生信號(hào)干擾。

綜上所述，最大加權(quán)獨(dú)立集問(wèn)題在現(xiàn)實(shí)生活中應(yīng)用廣泛。當(dāng)圖的結(jié)構(gòu)發(fā)生變化時(shí)，現(xiàn)有的算法只能重新搜索最大加權(quán)獨(dú)立集，因此無(wú)法高效地獲取結(jié)果。

針對(duì)上述問(wèn)題，本文首次提出動(dòng)態(tài)圖上的最大加權(quán)獨(dú)立集問(wèn)題，并設(shè)計(jì)出支持高效更新的近似算法LSWTwo，當(dāng)更新操作發(fā)生時(shí)，該算法考慮到受影響的點(diǎn)是距離為2范圍內(nèi)的點(diǎn)，因此，通過(guò)只處理該范圍的點(diǎn)，避免對(duì)最大加權(quán)獨(dú)立集的重新搜索，提升更新操作的效率。

1 相關(guān)工作

1.1 問(wèn)題定義

給定頂點(diǎn)加權(quán)無(wú)向圖G= (V,E,ω)以及該圖的最大加權(quán)獨(dú)立集，其中V表示G中頂點(diǎn)的集合，E表示G中邊的集合，ω表示頂點(diǎn)權(quán)值的集合。對(duì)于圖G中的頂點(diǎn)v，用N(v)表示該頂點(diǎn)的所有鄰居頂點(diǎn)。

定義1 獨(dú)立集給定無(wú)向圖G= (V,E)，圖中互不相鄰的頂點(diǎn)構(gòu)成的集合稱為獨(dú)立集。

定義2 最大獨(dú)立集(Maximum Independent Set，簡(jiǎn)稱 MIS)：給定無(wú)向圖G= (V,E)，稱頂點(diǎn)個(gè)數(shù)最多的獨(dú)立集為最大獨(dú)立集。

定義3 最大加權(quán)獨(dú)立集(Maximum Weight Independent Set，簡(jiǎn)稱 MWIS)：給定頂點(diǎn)加權(quán)無(wú)向圖G= (V,E,ω)，稱權(quán)值總和最大的獨(dú)立集為最大加權(quán)獨(dú)立集。

問(wèn)題定義給定T時(shí)刻的頂點(diǎn)加權(quán)無(wú)向圖G= (V,E,ω)以及該圖的最大加權(quán)獨(dú)立集MWIS(T)，T1時(shí)刻對(duì)圖G進(jìn)行一次更新操作得到G'，求圖G'的最大加權(quán)獨(dú)立集MWIS(T1)。

1.2 相關(guān)算法

本節(jié)介紹靜態(tài)圖上搜索最大加權(quán)獨(dú)立集的近似算法DtTwo[18]。DtTwo算法首先使用等價(jià)約簡(jiǎn)規(guī)則降低問(wèn)題的規(guī)模，然后使用貪心算法得到最大加權(quán)獨(dú)立集，接下來(lái)將詳細(xì)介紹DtTwo。

1.2.1 等價(jià)約簡(jiǎn)規(guī)則

定理1：（單頂點(diǎn)約簡(jiǎn)）給定一個(gè)頂點(diǎn)v∈V，如果ω(v) ＞ω(N(v))，則v必定屬于MWIS(G)，因此N(v)中的頂點(diǎn)可以刪除，得到MWIS(G)=MWIS(G') ∪ {v}，其中G'=G(N(v) ∪v)。

證明：假設(shè)頂點(diǎn)v不屬于MWIS(G)，因此頂點(diǎn)v至少有一個(gè)鄰居屬于MWIS(G)，可以用v替換MWIS(G)中v的鄰居，然后得到一個(gè)新的獨(dú)立集MWIS' (G)，因?yàn)棣?MWIS′(G) ) ＞ω(MWIS(G))，所以ω(MWIS′(G) ) ＞ω(MWIS(G))，可得頂點(diǎn)v必屬于MWIS(G)。

定理2：（雙頂點(diǎn)約簡(jiǎn)）給定兩個(gè)頂點(diǎn)v,u∈V和它們的鄰居P，如果ω(v) +ω(u)＞ω(P)，則v和u必屬于MWIS(G)，因此P中的頂點(diǎn)可以刪除，得到MWIS(G) =MWIS(G′ ) ∪ {v,u}，其中G′=G(P∪v∪u)。

DtTwo算法首先使用上述兩個(gè)等價(jià)約簡(jiǎn)規(guī)則對(duì)原始圖進(jìn)行等價(jià)約簡(jiǎn)，降低問(wèn)題的規(guī)模。

1.2.2 貪心算法

當(dāng)圖無(wú)法使用等價(jià)約簡(jiǎn)規(guī)則時(shí)，選擇權(quán)重最大的頂點(diǎn)為MWIS(G)中的頂點(diǎn)，同時(shí)刪除該頂點(diǎn)的所有鄰居，每次選擇頂點(diǎn)后迭代使用等價(jià)約簡(jiǎn)規(guī)則，重復(fù)此過(guò)程，直至圖為空，得到MWIS(G)。

2 LSWT wo算法

LSWTwo算法包含處理刪點(diǎn)、增邊和刪邊更新的方法。

2.1 刪點(diǎn)更新

刪點(diǎn)更新分為兩種情況：（1）當(dāng)刪除的頂點(diǎn)v不屬于MWIS(T)時(shí)，刪除該頂點(diǎn)v并不影響MWIS(T1)，所以MWIS(T1)和MWIS(T)相同；（2）當(dāng)刪除的頂點(diǎn)屬于MWIS(T)時(shí)，頂點(diǎn)v的鄰居u必定不屬于MWIS(T)，此時(shí)需要判斷頂點(diǎn)u是否有鄰居頂點(diǎn)屬于MWIS(T1)，若有，則頂點(diǎn)u必定不屬于MWIS(T1)，反之頂點(diǎn)u可能屬于MWIS(T1)，最后將所有可能屬于MWIS(T1)的頂點(diǎn)合起來(lái)生成一個(gè)子圖，對(duì)子圖進(jìn)行最大加權(quán)獨(dú)立集的搜索，搜索的最大加權(quán)獨(dú)立集與MWIS(T) v的并集為MWIS(T1)。刪點(diǎn)更新的具體過(guò)程如算法1所示。

算法1 RV

輸入：刪除的頂點(diǎn)v、T時(shí)刻圖G= (V,E,ω)和已知的最大加權(quán)獨(dú)立集MWIS(T)

輸出：T1時(shí)刻的最大加權(quán)獨(dú)立集MWIS(T1)

下面以圖1為例介紹RV的算法過(guò)程。

圖1 刪點(diǎn)更新示意圖Fig.1 Schematic diagram of delete point

例如，針對(duì)圖1的圖a，圖中帶有陰影的頂點(diǎn)表示屬于MWIS(T)，圖 a的最大加權(quán)獨(dú)立集為{11,12}。刪點(diǎn)更新分為兩種情況：（1）假設(shè)刪除的頂點(diǎn)屬于MWIS(T)，例如刪除權(quán)值為 12的頂點(diǎn)，因?yàn)樵擁旤c(diǎn)屬于MWIS(T)，所以刪除頂點(diǎn)時(shí)需要判斷該頂點(diǎn)的鄰居是否可能屬于MWIS(T1)，權(quán)值為12的頂點(diǎn)的鄰居有1、2、8三個(gè)頂點(diǎn)，通過(guò)遍歷可以發(fā)現(xiàn)1、2、8頂點(diǎn)的所有鄰居（除頂點(diǎn)12以外）都不屬于MWIS(T)，所以這三個(gè)頂點(diǎn)都可能屬于MWIS(T1)，于是生成由1、2、8三個(gè)頂點(diǎn)組成的子圖，如圖b所示，子圖b的最大加權(quán)獨(dú)立集為{1,8}，如圖c所示，最后將子圖b的最大加權(quán)獨(dú)立集與MWIS(T){12}合并，得到MWIS(T1)為{1,8,11}（如圖 e所示）。（2）假設(shè)刪除的頂點(diǎn)不屬于MWIS(T)，例如刪除權(quán)值為 9的頂點(diǎn)，因?yàn)樵擁旤c(diǎn)不屬于MWIS(T)，所以直接刪除該頂點(diǎn)及其所有的邊即可，如圖 d所示，MWIS(T1)與MWIS(T)相同，都為{11,12}。

2.2 增邊更新

增邊更新分為兩種情況：（1）當(dāng)增加的邊的兩端頂點(diǎn)有一個(gè)頂點(diǎn)不屬于MWIS(T)時(shí)，增邊后并不影響MWIS(T1)，所以MWIS(T1)和MWIS(T)相同；（2）當(dāng)增加的邊的兩端頂點(diǎn)都屬于MWIS(T)時(shí)，該操作會(huì)對(duì)MWIS(T1)造成影響，增加的邊兩端頂點(diǎn)必有一個(gè)屬于MWIS(T1)，另一個(gè)不屬于MWIS(T1)，本節(jié)方法將權(quán)值大的頂點(diǎn)添加到MWIS(T1)，減少權(quán)值的損失，權(quán)值小的頂點(diǎn)v則必定不屬于MWIS(T1)，所以頂點(diǎn)v的鄰居可能屬于MWIS(T1)，將所有可能屬于MWIS(T1)的頂點(diǎn)集合起來(lái)生成一個(gè)子圖，對(duì)子圖進(jìn)行最大加權(quán)獨(dú)立集的搜索，搜索的最大加權(quán)獨(dú)立集與MWIS(T) v的并集為MWIS(T1)。增邊更新的具體過(guò)程如算法2所示。

算法2 AE

輸入：增加的邊的兩端頂點(diǎn)v和u、T時(shí)刻圖G= (V,E,ω)和已知的最大加權(quán)獨(dú)立集MWIS(T)

輸出：T1時(shí)刻的最大加權(quán)獨(dú)立集MWIS(T1)

以圖 2為例介紹 AE的算法過(guò)程。針對(duì)圖 2的圖a，圖中帶有陰影的頂點(diǎn)表示屬于MWIS(T)，圖a的最大加權(quán)獨(dú)立集為{8,11}。增邊更新分為兩種情況：（1）假設(shè)增加的邊兩端頂點(diǎn)時(shí)需要將權(quán)值小的頂點(diǎn) 8從MWIS(T)中剔除，當(dāng)都屬于MWIS(T)，例如增加11和8之間的邊，因?yàn)轫旤c(diǎn)11和頂點(diǎn)8都屬于MWIS(T)，所以在增邊頂點(diǎn)8被剔除時(shí)，需要判斷該頂點(diǎn)的鄰居是否可能屬于MWIS(T1)，通過(guò)圖a可以發(fā)現(xiàn)頂點(diǎn)8的鄰居1、2、3的所有鄰居（除頂點(diǎn)8以外）都不屬于MWIS(T)，所以這三個(gè)頂點(diǎn)都可能屬于MWIS(T1)，于是將1、2、3三個(gè)頂點(diǎn)添加到子圖中，如圖b所示，子圖b的最大加權(quán)獨(dú)立集為{2,3}，如圖c所示，最后將子圖b的最大加權(quán)獨(dú)立集與MWIS(T){8}合并，得到MWIS(T1)為{2,3,11}，如圖e所示。（2）假設(shè)增加邊的兩端頂點(diǎn)含有不屬于MWIS(T)的頂點(diǎn)，例如增加頂點(diǎn)2和3之間的邊，因?yàn)楹胁粚儆贛WIS(T)的頂點(diǎn)，所以直接增加頂點(diǎn)2和3之間的邊即可，如圖d所示，MWIS(T1)與MWIS(T)相同，都為{8,11}。

圖2 增邊更新示意圖Fig.2 Schematic diagram of added edge

2.3 刪邊更新

刪邊更新分為兩種情況：（1）當(dāng)刪除的邊的兩端頂點(diǎn)都不屬于MWIS(T)時(shí)，刪邊后并不影響MWIS(T1)，所以MWIS(T1)和MWIS(T)相同；（2）當(dāng)刪除的邊的兩端頂點(diǎn)中有一個(gè)頂點(diǎn)屬于MWIS(T)時(shí)，該更新會(huì)對(duì)MWIS(T1)造成影響，判斷兩端頂點(diǎn)中不屬于MWIS(T)的頂點(diǎn)是否屬于MWIS(T1)即可。刪邊更新的具體過(guò)程如算法3所示。

算法3 RE

輸入：刪除邊的兩端頂點(diǎn)v和u、T時(shí)刻的圖G= (V,E,ω)和已知的最大加權(quán)獨(dú)立集MWIS(T)

輸出：T1時(shí)刻的最大加權(quán)獨(dú)立集MWIS(T1)

以圖3為例介紹RE的算法過(guò)程。

例如，針對(duì)圖3的圖a，圖中帶有陰影的頂點(diǎn)表示屬于MWIS(T)，圖 a的最大加權(quán)獨(dú)立集為{8,11}。刪邊操作主要分為兩種情況：（1）假設(shè)刪除的邊兩端頂點(diǎn)含有屬于MWIS(T)的頂點(diǎn)，例如刪除頂點(diǎn)8和頂點(diǎn)3之間的邊，因?yàn)轫旤c(diǎn)8屬于MWIS(T)，所以在刪除邊后需要判斷頂點(diǎn) 3是否可能屬于MWIS(T1)，因?yàn)轫旤c(diǎn) 3沒(méi)有屬于MWIS(T)的鄰居（除頂點(diǎn)8外），所以頂點(diǎn)3屬于MWIS(T1)，MWIS(T1)為{11,8,3}，如圖b所示。（2）假設(shè)刪除的邊兩端頂點(diǎn)都不屬于MWIS(T)，例如刪除頂點(diǎn)2和頂點(diǎn)1之間的邊，因?yàn)閮蓚€(gè)頂點(diǎn)都不屬于MWIS(T)，所以直接刪邊即可，如圖 c所示，MWIS(T1)與MWIS(T)相同，都為{8,11}。

圖3 刪邊更新示意圖Fig.3 Schematic diagram of edge deletion

2.4 算法分析

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)所使用的硬件配置是 Intel(R) Core(TM)i5-6600 CPU @3.30 GHz，8.00 GB RAM 以及Windows 7專(zhuān)業(yè)版；實(shí)驗(yàn)的運(yùn)行環(huán)境為Microsoft Visual Studio 2015。實(shí)驗(yàn)用于比較的算法是DtTwo算法和處理單一更新的RV、AE和RE算法。以上算法均采用C++語(yǔ)言實(shí)現(xiàn)。

3.2 數(shù)據(jù)集

表1 數(shù)據(jù)集統(tǒng)計(jì)信息Tab.1 Data set statistics

3.3 性能比較分析

本文提出的RV、AE、RE方法的初始加權(quán)獨(dú)立集均為已知質(zhì)量最高的最大加權(quán)獨(dú)立集。

表2、表 3和表4分別展示的是處理單一刪點(diǎn)、增邊、刪邊更新的最大加權(quán)獨(dú)立集的權(quán)值總和比較。觀察發(fā)現(xiàn)本文提出的RV、AE和RE方法搜索的最大加權(quán)獨(dú)立集的權(quán)值總和均大于DtTwo方法搜索的最大加權(quán)獨(dú)立集的權(quán)值總和。

表2 刪點(diǎn)更新的最大加權(quán)獨(dú)立集的權(quán)值總和Tab.2 The sum of the weights of the largest weighted independent set updated by deleting points

表3 增邊更新的最大加權(quán)獨(dú)立集的權(quán)值總和Tab.3 The sum of the weights of the largest weighted independent set updated by the incremental edge

表4 刪邊更新的最大加權(quán)獨(dú)立集的權(quán)值總和Tab.4 The sum of the weights of the largest weighted independent set updated by deleting edges

表 5展示的是刪點(diǎn)更新的時(shí)間比較，觀察可以發(fā)現(xiàn)RV方法中有多個(gè)值為0的數(shù)據(jù)集，原因是刪除的頂點(diǎn)未影響到更新后的圖的最大加權(quán)獨(dú)立集；在其它數(shù)據(jù)集上，RV方法的時(shí)間至少比DtTwo快 70倍，時(shí)間差最大的數(shù)據(jù)集是 soc_LiveJournall，RV比DtTwo快2649倍。

表5 刪點(diǎn)更新時(shí)間（ms）Tab.5 Delete point update time (ms)

表6展示的是增邊更新的時(shí)間比較。觀察可以發(fā)現(xiàn)AE方法中有多個(gè)值為0的數(shù)據(jù)集，原因是增加的邊未影響更新后的圖的最大加權(quán)獨(dú)立集；在其它數(shù)據(jù)集上，AE方法至少比DtTwo快70倍，時(shí)間差最大的數(shù)據(jù)集是 WikiTalk，RV比DtTwo快45815倍。

表6 增邊更新時(shí)間（ms）Tab.6 Increased update time (ms)

表7展示的是處理刪邊更新的時(shí)間比較。觀察可以發(fā)現(xiàn)RE方法中有多個(gè)值為0的數(shù)據(jù)集，原因是刪邊未影響更新后的圖的最大加權(quán)獨(dú)立集；在其它數(shù)據(jù)集上，RE方法的時(shí)間至少比DtTwo快70倍，時(shí)間差最大的數(shù)據(jù)集是WikiTalk，RE比DtTwo快2649倍。

表7 刪邊更新時(shí)間（ms）Tab.7 Delete edge update time

4 結(jié)論

針對(duì)動(dòng)態(tài)圖上的最大加權(quán)獨(dú)立集問(wèn)題，現(xiàn)有的解決方案是重新計(jì)算整個(gè)圖的最大加權(quán)獨(dú)立集。為了加快求解的效率，本文提出了一種只考慮被操作頂點(diǎn)距離為 2范圍內(nèi)頂點(diǎn)的近似算法LSWTwo。實(shí)驗(yàn)結(jié)果表明，LSWTwo算法在不降低結(jié)果質(zhì)量的前提下，將搜索的時(shí)間降低了80%～98%。