一種高效的動態圖最大加權獨立集求解算法

祁才云，周軍鋒，杜 明

(東華大學，上海 200000)

0 引言

圖是用來描述個體之間相互聯系的一種復雜的數據結構[1]。在現實世界中，可將網絡[2-3]、計算機視覺[4-5]、社交網絡[6-7]、無線傳感網絡[8]等數據抽象為圖模型。在實際生活中，最大加權獨立集問題[9-14]廣泛應用于解決各項問題，例如分配分布式系統中的資源、避免無線網絡中的多址信道干擾等。

動態圖[15-17]是指會隨時間發生變化的圖數據。例如，在現實世界中，個體的數量或個體間的聯系發生變化時，圖也相應的發生著變化，可以把這種圖的變化抽象為動態圖。隨著數據的快速變化，在動態圖上獲取有價值的信息也吸引了大量研究者的關注。在分布式系統中，當系統中計算機的數量、計算機間的干擾頻繁發生變化時，可以不用考慮整個系統，只需單獨觀察發生變化的計算機或計算機間的干擾，快速搜索圖的最大加權獨立集，進而減少數據傳輸過程中數據丟失。在無線網絡中，用戶的數量以及信號傳播中的干擾會隨時發生變化，在這些變化發生后，需要快速獲取該圖的最大加權獨立集，進而避免發生信號干擾。

綜上所述，最大加權獨立集問題在現實生活中應用廣泛。當圖的結構發生變化時，現有的算法只能重新搜索最大加權獨立集，因此無法高效地獲取結果。

針對上述問題，本文首次提出動態圖上的最大加權獨立集問題，并設計出支持高效更新的近似算法LSWTwo，當更新操作發生時，該算法考慮到受影響的點是距離為2范圍內的點，因此，通過只處理該范圍的點，避免對最大加權獨立集的重新搜索，提升更新操作的效率。

1 相關工作

1.1 問題定義

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

定義1 獨立集給定無向圖G= (V,E)，圖中互不相鄰的頂點構成的集合稱為獨立集。

定義2 最大獨立集(Maximum Independent Set，簡稱 MIS)：給定無向圖G= (V,E)，稱頂點個數最多的獨立集為最大獨立集。

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

問題定義給定T時刻的頂點加權無向圖G= (V,E,ω)以及該圖的最大加權獨立集MWIS(T)，T1時刻對圖G進行一次更新操作得到G'，求圖G'的最大加權獨立集MWIS(T1)。

1.2 相關算法

本節介紹靜態圖上搜索最大加權獨立集的近似算法DtTwo[18]。DtTwo算法首先使用等價約簡規則降低問題的規模，然后使用貪心算法得到最大加權獨立集，接下來將詳細介紹DtTwo。

1.2.1 等價約簡規則

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

證明：假設頂點v不屬于MWIS(G)，因此頂點v至少有一個鄰居屬于MWIS(G)，可以用v替換MWIS(G)中v的鄰居，然后得到一個新的獨立集MWIS' (G)，因為ω(MWIS′(G) ) ＞ω(MWIS(G))，所以ω(MWIS′(G) ) ＞ω(MWIS(G))，可得頂點v必屬于MWIS(G)。

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

DtTwo算法首先使用上述兩個等價約簡規則對原始圖進行等價約簡，降低問題的規模。

1.2.2 貪心算法

當圖無法使用等價約簡規則時，選擇權重最大的頂點為MWIS(G)中的頂點，同時刪除該頂點的所有鄰居，每次選擇頂點后迭代使用等價約簡規則，重復此過程，直至圖為空，得到MWIS(G)。

2 LSWT wo算法

LSWTwo算法包含處理刪點、增邊和刪邊更新的方法。

2.1 刪點更新

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

算法1 RV

輸入：刪除的頂點v、T時刻圖G= (V,E,ω)和已知的最大加權獨立集MWIS(T)

輸出：T1時刻的最大加權獨立集MWIS(T1)

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

圖1 刪點更新示意圖Fig.1 Schematic diagram of delete point

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

2.2 增邊更新

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

算法2 AE

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

輸出：T1時刻的最大加權獨立集MWIS(T1)

以圖 2為例介紹 AE的算法過程。針對圖 2的圖a，圖中帶有陰影的頂點表示屬于MWIS(T)，圖a的最大加權獨立集為{8,11}。增邊更新分為兩種情況：（1）假設增加的邊兩端頂點時需要將權值小的頂點 8從MWIS(T)中剔除，當都屬于MWIS(T)，例如增加11和8之間的邊，因為頂點11和頂點8都屬于MWIS(T)，所以在增邊頂點8被剔除時，需要判斷該頂點的鄰居是否可能屬于MWIS(T1)，通過圖a可以發現頂點8的鄰居1、2、3的所有鄰居（除頂點8以外）都不屬于MWIS(T)，所以這三個頂點都可能屬于MWIS(T1)，于是將1、2、3三個頂點添加到子圖中，如圖b所示，子圖b的最大加權獨立集為{2,3}，如圖c所示，最后將子圖b的最大加權獨立集與MWIS(T){8}合并，得到MWIS(T1)為{2,3,11}，如圖e所示。（2）假設增加邊的兩端頂點含有不屬于MWIS(T)的頂點，例如增加頂點2和3之間的邊，因為含有不屬于MWIS(T)的頂點，所以直接增加頂點2和3之間的邊即可，如圖d所示，MWIS(T1)與MWIS(T)相同，都為{8,11}。

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

2.3 刪邊更新

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

算法3 RE

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

輸出：T1時刻的最大加權獨立集MWIS(T1)

以圖3為例介紹RE的算法過程。

例如，針對圖3的圖a，圖中帶有陰影的頂點表示屬于MWIS(T)，圖 a的最大加權獨立集為{8,11}。刪邊操作主要分為兩種情況：（1）假設刪除的邊兩端頂點含有屬于MWIS(T)的頂點，例如刪除頂點8和頂點3之間的邊，因為頂點8屬于MWIS(T)，所以在刪除邊后需要判斷頂點 3是否可能屬于MWIS(T1)，因為頂點 3沒有屬于MWIS(T)的鄰居（除頂點8外），所以頂點3屬于MWIS(T1)，MWIS(T1)為{11,8,3}，如圖b所示。（2）假設刪除的邊兩端頂點都不屬于MWIS(T)，例如刪除頂點2和頂點1之間的邊，因為兩個頂點都不屬于MWIS(T)，所以直接刪邊即可，如圖 c所示，MWIS(T1)與MWIS(T)相同，都為{8,11}。

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

2.4 算法分析

3 實驗分析

3.1 實驗環境

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

3.2 數據集

表1 數據集統計信息Tab.1 Data set statistics

3.3 性能比較分析

本文提出的RV、AE、RE方法的初始加權獨立集均為已知質量最高的最大加權獨立集。

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

表2 刪點更新的最大加權獨立集的權值總和Tab.2 The sum of the weights of the largest weighted independent set updated by deleting points

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

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

表 5展示的是刪點更新的時間比較，觀察可以發現RV方法中有多個值為0的數據集，原因是刪除的頂點未影響到更新后的圖的最大加權獨立集；在其它數據集上，RV方法的時間至少比DtTwo快 70倍，時間差最大的數據集是 soc_LiveJournall，RV比DtTwo快2649倍。

表5 刪點更新時間（ms）Tab.5 Delete point update time (ms)

表6展示的是增邊更新的時間比較。觀察可以發現AE方法中有多個值為0的數據集，原因是增加的邊未影響更新后的圖的最大加權獨立集；在其它數據集上，AE方法至少比DtTwo快70倍，時間差最大的數據集是 WikiTalk，RV比DtTwo快45815倍。

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

表7展示的是處理刪邊更新的時間比較。觀察可以發現RE方法中有多個值為0的數據集，原因是刪邊未影響更新后的圖的最大加權獨立集；在其它數據集上，RE方法的時間至少比DtTwo快70倍，時間差最大的數據集是WikiTalk，RE比DtTwo快2649倍。

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

4 結論

針對動態圖上的最大加權獨立集問題，現有的解決方案是重新計算整個圖的最大加權獨立集。為了加快求解的效率，本文提出了一種只考慮被操作頂點距離為 2范圍內頂點的近似算法LSWTwo。實驗結果表明，LSWTwo算法在不降低結果質量的前提下，將搜索的時間降低了80%～98%。