大規(guī)模符號網(wǎng)絡(luò)劃分的學(xué)習(xí)驅(qū)動型擴(kuò)展變鄰域搜索算法

摘 要：給定一個無向圖，符號網(wǎng)絡(luò)劃分問題（signed graph partitioning problem，SGPP）是將節(jié)點集合劃分為K（K≥2）個互不相交的非空分組，旨在最小化所有位于分組內(nèi)的負(fù)符號邊權(quán)重之和加上位于分組之間的正符號邊權(quán)重之和，使網(wǎng)絡(luò)劃分結(jié)構(gòu)盡量趨于平衡。SGPP是NP難問題，在計算機(jī)視覺、社交網(wǎng)絡(luò)分析、生物信息學(xué)等實際領(lǐng)域中具有重要應(yīng)用。但大數(shù)據(jù)時代的到來給求解大規(guī)模SGPP帶來一定的挑戰(zhàn)。因此，設(shè)計新穎且高效的學(xué)習(xí)驅(qū)動型擴(kuò)展變鄰域搜索算法（learning driven extended variable neighborhood search，LDEVNS）來求解SGPP。具體來說，該算法設(shè)計全新的快速增量更新策略以及高效的擴(kuò)展變鄰域搜索，同時結(jié)合強化學(xué)習(xí)機(jī)制來調(diào)整算法搜索過程中的前進(jìn)方向，進(jìn)一步探索更有希望的解空間區(qū)域來找到更高質(zhì)量的求解方案。實驗部分使用15組大規(guī)模社交網(wǎng)絡(luò)圖來評估LDEVNS的高性能，實驗結(jié)果顯示，LDEVNS在求解質(zhì)量和計算時間方面相較于當(dāng)前表現(xiàn)最佳的算法具有顯著優(yōu)勢，同時也驗證了強化學(xué)習(xí)在LDEVNS中的有效性。

關(guān)鍵詞：符號網(wǎng)絡(luò)劃分；啟發(fā)式；變鄰域搜索；強化學(xué)習(xí)

中圖分類號：TP181"" 文獻(xiàn)標(biāo)志碼：A"" 文章編號：1001-3695（2025）03-017-0770-07

doi：10.19734/j.issn.1001-3695.2024.07.0309

Learning-driven extended variable neighborhood search forsigned graph partitioning

Tao Zijun，Lu Zhi，Meng Bingjin

（Business School，University of Shanghai for Science amp; Technology，Shanghai 200093，China）

Abstract：Given an undirected signed graph，the SGPP divides the set of nodes into K（K≥2）pairwise disjoint nonempty subsets to minimize the number of positive edges between the subsets and the number of negative edges within the subsets.The SGPP is an NP-hard problem with significant applications in real-world fields such as computer vision，social network analysis，bioinformatics，etc.However，the SGPP has become more challenging to address in the big data era.This paper proposed a learning driven extended variable neighborhood search（LDEVNS）to tackle the SGPP.Specifically，it designed a new fast incremental update strategy and an efficient extended variable neighborhood search.To explore the search space more efficiently，it combined a reinforcement learning mechanism to guide the search direction.The experiment utilized 15 large-scale social networks to assess the performance of the LDEVNS algorithm.Experimental results show that the LDEVNS outperforms the best-performing algorithms in terms of solution quality and computing time.Additionally，it verifies the effectiveness of the reinforcement learning mechanism in the LDEVNS.

Key words：signed network partitioning;heuristics;variable neighborhood search;reinforcement learning

0 引言

符號網(wǎng)絡(luò)起源于Heider［1］，是指邊具有正負(fù)符號屬性的網(wǎng)絡(luò)。其中，正符號邊表示友好關(guān)系，如朋友、信任、喜歡、支持等，通常使用正號“+”進(jìn)行標(biāo)識；負(fù)符號邊表示對立關(guān)系，例如敵人、不信任、討厭、反對等，通常使用負(fù)號“-”進(jìn)行標(biāo)識［2］。在社會、生物和信息等領(lǐng)域，許多復(fù)雜系統(tǒng)都明確包含著對立關(guān)系，例如，人際關(guān)系中的朋友與敵人［1］、國際關(guān)系中的合作與敵對［2］、生物領(lǐng)域中神經(jīng)元之間的促進(jìn)和抑制［3］以及信息領(lǐng)域中用戶在社交網(wǎng)站上表達(dá)信任或不信任態(tài)度［4］等。

結(jié)構(gòu)平衡理論作為符號網(wǎng)絡(luò)研究的理論基礎(chǔ)，刻畫了符號網(wǎng)絡(luò)的主要結(jié)構(gòu)和特征。Harary［5］將Heider［1］提出的結(jié)構(gòu)平衡理論概念形式化，為描述社會關(guān)系正式引入了符號網(wǎng)絡(luò)的概念，為確定符號網(wǎng)絡(luò)整體結(jié)構(gòu)奠定了基礎(chǔ)。Harary［5］最初考慮將符號網(wǎng)絡(luò)劃分為兩個互不相交的分組，并證明如果使得正符號邊在分組內(nèi)，負(fù)符號邊在分組間，這個符號網(wǎng)絡(luò)就是平衡的。Davis［6］將分組擴(kuò)展到任意數(shù)量，并證明當(dāng)且僅當(dāng)一個圖中所有環(huán)都是正符號環(huán)時該圖才是平衡的。然而，在大多數(shù)實際的社會符號網(wǎng)絡(luò)中，完美的平衡結(jié)構(gòu)并不存在，通過對這些網(wǎng)絡(luò)劃分來研究其結(jié)構(gòu)是十分必要的。

Davis［6］進(jìn)一步闡述了當(dāng)符號網(wǎng)絡(luò)的節(jié)點被劃分為K個分組時的K平衡屬性，并稱每個分組為一個聚類。隨后，研究者們開始從不同角度刻畫該聚類問題的數(shù)學(xué)模型。Doreian等人［7］將該問題形式化為符號網(wǎng)絡(luò)的廣義結(jié)構(gòu)平衡劃分（gene-ralized structural balance partitioning），也稱為K劃分（K-balance partitioning）。為了描述一致，本文將它們統(tǒng)稱為符號網(wǎng)絡(luò)劃分問題（signed graph partitioning problem，SGPP）。Bansal等人［8］又將該問題表述為相關(guān)聚類（correlation clustering，CC）。具體來說，SGPP是將節(jié)點集合劃分為K（K≥2）個互不相交的非空分組，目標(biāo)是使得所有正符號邊位于分組內(nèi)，負(fù)符號邊位于分組間。SGPP被證明是NP難問題［7］，在大規(guī)模符號網(wǎng)絡(luò)中，上述完美的平衡結(jié)構(gòu)劃分難以找到。因此，文獻(xiàn)中一般使用最小化劃分的不平衡程度（又稱誤差函數(shù)）來評估劃分網(wǎng)絡(luò)對平衡的接近程度，并已經(jīng)出現(xiàn)了一些不同的目標(biāo)函數(shù)，例如總體不一致性［7］、加權(quán)不一致性［7］、正（負(fù)）符號邊不一致性［7］、哈密頓［9］以及拉普拉斯［10］等。本文主要研究最具有代表性的基于總體不一致性［7］目標(biāo)函數(shù)的SGPP，即通過最小化不同分組間的正符號邊權(quán)重之和，加上同一分組內(nèi)的負(fù)符號邊權(quán)重之和，來找到符號網(wǎng)絡(luò)的一種結(jié)構(gòu)最為平衡的劃分方案。

SGPP在一些實際領(lǐng)域中擁有廣泛應(yīng)用，例如計算機(jī)視覺、社交網(wǎng)絡(luò)分析、生物信息學(xué)等。在計算機(jī)視覺領(lǐng)域，SGPP旨在將具有符號信息的圖像劃分為具有獨立語義的區(qū)域，這對于處理擁有復(fù)雜結(jié)構(gòu)的圖像、符號或文本數(shù)據(jù)具有重要意義［11］。在社交網(wǎng)絡(luò)分析中，SGPP用于識別社交網(wǎng)絡(luò)中的不同社群，幫助人們更好地理解社交網(wǎng)絡(luò)中的社群結(jié)構(gòu)、信息傳播等特性［12］。在生物信息學(xué)領(lǐng)域，蛋白質(zhì)相互作用網(wǎng)絡(luò)被構(gòu)建為符號網(wǎng)絡(luò)，通過劃分該網(wǎng)絡(luò)可以揭示蛋白質(zhì)之間的功能和相互作用［13］。

對于SGPP求解方法的研究，早期主要集中在精確算法。Brusco等人［14］提出了分支定界算法，但僅能求解小于30個節(jié)點的符號網(wǎng)絡(luò)。Figueiredo等人［15］提出了更加通用的混合整數(shù)規(guī)劃。Aref等人［16］提出了整數(shù)線性規(guī)劃，并已成為求解SGPP使用最為廣泛的技術(shù)之一。盡管精確算法的研究取得了一定進(jìn)展，但隨著社交網(wǎng)絡(luò)規(guī)模的逐漸增大，一些研究者們開始轉(zhuǎn)向更為高效的啟發(fā)式算法，力求在有限的時間范圍內(nèi)快速找到問題的高質(zhì)量求解方案，例如基于不同目標(biāo)函數(shù)的重定位啟發(fā)式（relocation heuristic，RH）［7］、模因算法（memetic algorithm，MA）［17］、GRASP（greedy randomized adaptive search procedure）［18］、迭代局部搜索（iterated local search，ILS）［19～22］、貪心算法［23］等。Brusco等人［24］提出了兩階段搜索策略來求解基于總體不一致性的SGPP，第一階段使用RH獲得穩(wěn)定初始解，第二階段使用禁忌搜索（tabu search，TS）或變鄰域搜索（variable neighborhood search，VNS）來進(jìn)一步提升解的質(zhì)量。

通過文獻(xiàn)可知，雖然現(xiàn)有方法在一定程度上解決了SGPP，但仍然存在一些明顯不足。SGPP求解方法的早期研究主要集中在針對中小規(guī)模問題的精確算法。近些年來，由于大規(guī)模問題數(shù)據(jù)量和復(fù)雜性的急劇增加，算法的時間復(fù)雜度成倍上升，精確算法因為計算復(fù)雜度的限制而變得不可行［21］。而啟發(fā)式算法在可接受的時間范圍內(nèi)能夠找到足夠好的問題求解方案，是目前求解大規(guī)模問題的高效方法。文獻(xiàn)［19］指出，啟發(fā)式算法是求解大規(guī)模CC和SGPP的主要方法。因此，開發(fā)高效的啟發(fā)式算法是求解SGPP的最重要方向之一。通過文獻(xiàn)分析可知，基于總體不一致性目標(biāo)函數(shù)的SGPP研究還較少，盡管已有一些嘗試，但針對該問題的啟發(fā)式算法研究仍然較為有限。Brusco等人［24］提出的VNS是目前最新且性能最好的啟發(fā)式算法，其通過在多種鄰域中進(jìn)行搜索，避免算法陷入局部最優(yōu)，但仍然存在一些不足。首先，該算法在求解質(zhì)量和算法效率之間無法取得平衡，難以保證劃分結(jié)果的準(zhǔn)確性和高效性。其次，處理大規(guī)模符號網(wǎng)絡(luò)通常需要存儲和處理大量信息，該方法計算復(fù)雜度較高，限制了在實際應(yīng)用中的可能性。因此，新方法需要在保證準(zhǔn)確性的同時，提升算法的效率。強化學(xué)習(xí)（reinforcement learning，RL）［25，26］是通過與環(huán)境交互，基于反饋獎勵來逐步改進(jìn)策略的前沿方法。RL具有自適應(yīng)性，通過在不斷地試探和反饋過程中優(yōu)化決策，其與啟發(fā)式算法相結(jié)合，能夠?qū)W習(xí)到高質(zhì)量的解，進(jìn)一步提高算法的性能。結(jié)合目前高效的VNS搜索策略與強大的RL學(xué)習(xí)能力，可以實現(xiàn)更加高效的優(yōu)化框架，尤其適合解決大規(guī)模問題。因此，本文以符號網(wǎng)絡(luò)劃分的總體不一致性為優(yōu)化目標(biāo)，擬設(shè)計全新且高效的學(xué)習(xí)驅(qū)動型擴(kuò)展變鄰域搜索算法（learning driven extended variable neighborhood search，LDEVNS）。該算法設(shè)計了全新的快速增量更新策略以及高效的擴(kuò)展變鄰域搜索，并首次將VNS框架與強化學(xué)習(xí)相結(jié)合，利用分組信息指導(dǎo)算法的搜索方向來獲得高質(zhì)量的求解方案。本文的實驗使用15組代表性的大規(guī)模社交網(wǎng)絡(luò)圖來評估LDEVNS的高性能，并與現(xiàn)有實驗結(jié)果最好的啟發(fā)式算法RH、TS和VNS［24］進(jìn)行對比。實驗結(jié)果顯示，隨著分組數(shù)量K的逐漸增大，LDEVNS能夠快速獲得更高質(zhì)量的求解方案，強化學(xué)習(xí)的加入也進(jìn)一步提升了算法性能。

2.5 算法復(fù)雜度分析

LDEVNS算法主要由三部分組成：RH生成初始解、EVNS和強化學(xué)習(xí)機(jī)制。開始階段，算法生成初始解的時間復(fù)雜度為O（N·K）。然后算法進(jìn)入while循環(huán)，首先EVNS由局部搜索和擾動兩部分組成。在局部搜索部分，鄰居解的評估和移動使用的是快速增量更新策略，時間復(fù)雜度為O（N·K）。在擾動部分，包括對Freq數(shù)組進(jìn)行排序和選擇部分節(jié)點進(jìn)行擾動兩部分，時間復(fù)雜度分別為O（N logN）和O（N）。因此，整個EVNS的時間復(fù)雜度為O（N logN+N·K）。然后是強化學(xué)習(xí)機(jī)制，其中分組選擇策略、學(xué)習(xí)概率更新技術(shù)和學(xué)習(xí)概率平滑技術(shù)的時間復(fù)雜度均為O（N·K）。因此，LDEVNS算法整體時間復(fù)雜度為O（N logN+N·K）。

3 實驗測試與分析

為了驗證本文所設(shè)計的LDEVNS算法的高性能，首先將LDEVNS與目前最好的參照算法RH、TS、VNS［24］進(jìn)行實驗對比，然后分析強化學(xué)習(xí)機(jī)制的有效性，最后總結(jié)實驗結(jié)果。

3.1 測試算例

本文使用15組大規(guī)模社交網(wǎng)絡(luò)圖來評估所有算法的性能，它們均來自于公共數(shù)據(jù)集SNAP［28］（https：//snap.stanford.edu/data/）和KONECT［29］（http：//konect.cc/）。在進(jìn)行實驗前，本文首先對數(shù)據(jù)集進(jìn)行預(yù)處理，將其統(tǒng)一轉(zhuǎn)換為無向圖，并且確保圖中不包含平行邊和自環(huán)邊，具體方法為：首先移除圖中所有自環(huán)邊，然后將所有平行和相反方向的弧合并為一條無向邊，其權(quán)重為原有弧權(quán)重的總和［16］。預(yù)處理后的15組數(shù)據(jù)集如表1所示。這些圖的節(jié)點范圍為［3 783，138 592］，符號邊范圍為［14 081，1 461 058］，涵蓋了不同結(jié)構(gòu)的大規(guī)模社交網(wǎng)絡(luò)圖，為算法的評估提供了全面且準(zhǔn)確的數(shù)據(jù)基礎(chǔ)。

3.2 實驗平臺配置

為了公平地驗證所有算法的性能，本文采用相同的實驗運行環(huán)境測試提出的LDEVNS算法以及參照算法RH、TS和VNS。在硬件方面，處理器為Intel Xeon E5-2670 v4 processor（2.5 GHz，12 GB RAM），操作系統(tǒng)為Linux操作系統(tǒng)。在軟件方面，使用Python 3.8實現(xiàn)LDEVNS、RH、TS和VNS算法。需要注意的是，本文使用PyPy解釋器進(jìn)行編譯，其是標(biāo)準(zhǔn)CPython解釋器的另一個版本，在處理長時間運行的純Python腳本時表現(xiàn)出色，特別適用于本文的計算密集型任務(wù)。本文的15組測試算例運行時間為［900，3 600］ s，每個算例都在不同的隨機(jī)數(shù)種子下運行10次，并記錄K∈［2，512］的結(jié)果，如表2所示。

3.3 參數(shù)設(shè)置

LDEVNS一共有2個參數(shù)：最大重啟次數(shù)L和擾動節(jié)點百分比Percent，如表3所示。為了分析參數(shù)對LDEVNS性能的影響，本文進(jìn)行了參數(shù)敏感性分析實驗［30］。具體來說，本文首先根據(jù)前期實驗測試，經(jīng)驗性地確定了每個參數(shù)的合理取值范圍，參數(shù)L的取值為［4 000，…，12 000］，參數(shù)Percent的取值為［0.05，…，0.25］。在此基礎(chǔ)上，通過改變一個參數(shù)并固定其他參數(shù)來在算例上進(jìn)行測試，以結(jié)果判斷參數(shù)的取值。本文選取大小和難度較合適的數(shù)據(jù)集slashdot-undirected-size10000-part1進(jìn)行調(diào)參，實驗運行配置與前述一致。

圖3和4是實驗結(jié)果的箱線圖，其中x軸表示參數(shù)取值，y軸表示10次測試結(jié)果的累積最好目標(biāo)函數(shù)值的統(tǒng)計平均值Z（P）。同時，本文還采用了置信水平為95%的Friedman秩和檢驗來評估不同參數(shù)值樣本是否存在統(tǒng)計性差異。從圖3可以看出，參數(shù)L的變化對LDEVNS性能影響不明顯，其統(tǒng)計檢測結(jié)果也沒有表現(xiàn)出顯著性差異（p-value=0.07）。而從圖4可以看出，參數(shù)Percent的變化對LDEVNS性能有明顯影響，其在Percent=0.1處取得最好值，且其統(tǒng)計檢測結(jié)果在性能上存在顯著性差異（p-value=0.03）。因此，本文選取L=6 000，Percent=0.1作為參數(shù)的最終取值。

3.4 實驗結(jié)果

3.4.1 實驗結(jié)果比較與分析

表4～7為參照算法RH、TS、VNS和LDEVNS在15個大規(guī)模社交網(wǎng)絡(luò)圖上統(tǒng)計最好值Zbest、平均值Zavg、統(tǒng)計最差值Zworst以及達(dá)到最好值的統(tǒng)計平均時間t（s）的結(jié)果比較（詳細(xì)結(jié)果可參見https：//github.com/hellozhilu/LDEVNS/）。觀察表4～6的三個指標(biāo)可以發(fā)現(xiàn)，在分區(qū)K=2和K=4時，LDEVNS的結(jié)果略差于VNS，但差距微小。而隨著K的逐漸增大，在8≤K≤512，LDEVNS性能明顯優(yōu)于參照算法RH、TS、VNS。在運行時間方面，從表7可以看出，LDEVNS運行時間比RH、TS、VNS明顯更短。例如，當(dāng)K=8時，LDEVNS在平均時間1 173.5 s可以達(dá)到統(tǒng)計平均最好值44 631.5，而VNS要在2 312.2 s才能達(dá)到最好值44 712.8。圖5～8的折線圖也進(jìn)一步說明，LDEVNS雖然在K較小時結(jié)果略差于參照算法，但隨著K的逐漸變大和算法時間復(fù)雜度增大，LDEVNS明顯優(yōu)于參照算法。綜上所述，LDEVNS在15組測試數(shù)據(jù)集上展現(xiàn)出了非常優(yōu)異的性能，雖然在K較小時算法性能略低于參照算法，但當(dāng)K逐漸變大時，在統(tǒng)計最好、平均、最差結(jié)果上，LDEVNS均優(yōu)于參照算法，且其優(yōu)勢在K越大時變得越明顯。在計算時間方面LDEVNS也更少，說明LDEVNS在解決大規(guī)模網(wǎng)絡(luò)時具有較好的求解性能、求解效率以及穩(wěn)定性。

3.4.2 強化學(xué)習(xí)機(jī)制的有效性驗證

為了驗證強化學(xué)習(xí)在LDEVNS中的性能，本文對LDEVNS與未加入強化學(xué)習(xí)的REVNS進(jìn)行對比實驗。其中，REVNS是將LDEVNS中的強化學(xué)習(xí)替換成了隨機(jī)重啟機(jī)制。本部分實驗運行配置與前述一致。表8為REVNS和LDEVNS在測試數(shù)據(jù)集soc-sign-bitcoinotc上的結(jié)果比較，包括每個算法在不同K值下的最好值Zbest、平均值Zavg、最差值Zworst、達(dá)到最好值的次數(shù)hit和達(dá)到最好值的平均時間t（s）。從表8可以看出，在K較小時（如K=2），LDEVNS的最好值和平均值和REVNS持平，但在K較大時（如4≤K≤512），LDEVNS的最好值明顯優(yōu)于REVNS，平均值略好于REVNS。綜上所述，LDEVNS和REVNS在K較小時表現(xiàn)趨于一致，而當(dāng)K逐漸變大時，LDEVNS整體效果更優(yōu)。該現(xiàn)象說明強化學(xué)習(xí)對算法性能有著非常積極的影響，尤其當(dāng)問題規(guī)模較大且對計算時間要求較高時，結(jié)合強化學(xué)習(xí)機(jī)制的LDEVNS性能越好。

4 結(jié)束語

符號網(wǎng)絡(luò)劃分問題（SGPP）是將節(jié)點集合劃分為K（K≥2）個互不相交的非空分組，旨在最小化所有位于分組內(nèi)的負(fù)符號邊權(quán)重之和加上位于分組之間的正符號邊權(quán)重之和，使劃分網(wǎng)絡(luò)結(jié)構(gòu)盡量趨向于平衡。SGPP是NP難問題，在計算機(jī)視覺、社交網(wǎng)絡(luò)分析、生物信息學(xué)等實際領(lǐng)域中具有重要應(yīng)用。本文首次提出了新穎且高效的學(xué)習(xí)驅(qū)動型擴(kuò)展變鄰域搜索算法（LDEVNS）來求解SGPP。具體來說，該算法設(shè)計了全新的快速增量更新策略以及高效的擴(kuò)展變鄰域搜索，并結(jié)合強化學(xué)習(xí)機(jī)制來調(diào)整算法搜索過程中的前進(jìn)方向，進(jìn)一步探索更有希望的解空間區(qū)域并找到更高質(zhì)量的求解方案。實驗部分使用了15組大規(guī)模社交網(wǎng)絡(luò)圖對算法性能進(jìn)行評估和測試，并與目前文獻(xiàn)中最好的算法RH、TS、VNS進(jìn)行對比。實驗結(jié)果顯示，LDEVNS明顯優(yōu)于參照算法，特別當(dāng)分區(qū)K越大時，LDEVNS在求解質(zhì)量和時間方面均占據(jù)顯著優(yōu)勢。本文還驗證了強化學(xué)習(xí)在LDEVNS中的有效性，結(jié)果表明當(dāng)問題規(guī)模越大且計算時間要求越高時，LDEVNS的性能越好。在未來研究中，還可以進(jìn)一步探索更高效的啟發(fā)式算法來求解更大規(guī)模的SGPP，考慮將算法應(yīng)用到一些實際的工程問題中。

參考文獻(xiàn)：

［1］Heider F.Attitudes and cognitive organization［J］.The Journal of Psychology，1946，21：107-112.

［2］劉苗苗，扈慶翠，郭景峰，等.融合局部與全局緊密度的符號網(wǎng)絡(luò)鏈接預(yù)測算法［J］.計算機(jī)應(yīng)用研究，2021，38（7）：2003-2008，2017.（Liu Miaomiao，Hu Qingcui，Guo Jingfeng，et al.Link prediction in signed networks based on local and global tightness［J］.Application Research of Computers，2021，38（7）：2003-2008，2017.）

［3］Parisien C，Anderson C H，Eliasmith C.Solving the problem of negative synaptic weights in cortical models［J］.Neural Computation，2008，20（6）：1473-1494.

［4］顏仕雄，朱焱，李春平.基于多頭注意力機(jī)制的社交網(wǎng)絡(luò)符號預(yù)測［J］.計算機(jī)應(yīng)用研究，2021，38（5）：1360-1364.（Yan Shixiong，Zhu Yan，Li Chunping.Social network sign prediction based on multi-head attention mechanism［J］.Application Research of Compu-ters，2021，38（5）：1360-1364.）

［5］Harary F.On the notion of balance of a signed graph［J］.Michigan Mathematical Journal，1953，2（2）：143-146.

［6］Davis J A.Clustering and structural balance in graphs［J］.Human Relations，1967，20（2）：181-187.

［7］Doreian P，Mrvar A.A partitioning approach to structural balance［J］.Social Networks，1996，18（2）：149-168.

［8］Bansal N，Blum A，Chawla S.Correlation clustering［J］.Machine Learning，2004，56（1）：89-113.

［9］Xia Chengyi，Luo Yongping，Wang Li，et al.A fast community detection algorithm based on reconstructing signed networks［J］.IEEE Systems Journal，2022，16（1）：614-625.

［10］Ko T，Choi Y，Kim C K.A spectral graph convolution for signed directed graphs via magnetic Laplacian［J］.Neural Networks，2023，164：562-574.

［11］Kim S，Nowozin S，Kohli P，et al.Higher-order correlation clustering for image segmentation［C］//Proc of the 24th International Confe-rence on Neural Information Processing Systems.Red Hook，NY：Curran Associates Inc.，2011：1530-1538.

［12］Altafini C.Dynamics of opinion forming in structurally balanced social networks［J］.PLoS One，2012，7（6）：e38135.

［13］DasGupta B，Enciso G A，Sontag E，et al.Algorithmic and complexity results for decompositions of biological networks into monotone subsystems［J］.Biosystems，2007，90（1）：161-178.

［14］Brusco M，Steinley D.K-balance partitioning：an exact method with applications to generalized structural balance and other psychological contexts［J］.Psychological Methods，2010，15（2）：145-157.

［15］Figueiredo R，Moura G.Mixed integer programming formulations for clustering problems related to structural balance［J］.Social Networks，2013，35（4）：639-651.

［16］Aref S，Mason A J，Wilson M C.An exact method for computing the frustration index in signed networks using binary programming［EB/OL］.（2016-11-28）.https：//arxiv.org/abs/1611.09030v1.

［17］Hausberger F，F(xiàn)onseca M，Schulz C，et al.A distributed multilevel memetic algorithm for signed graph clustering［C］//Proc of Compa-nion Conference on Genetic and Evolutionary Computation.New York：ACM Press，2023：207-210.

［18］Wahid D F，Hassini E.A literature review on correlation clustering：cross-disciplinary taxonomy with bibliometric analysis［J］.Operations Research Forum，2022，3（3）：47.

［19］Levorato M，F(xiàn)igueiredo R，F(xiàn)rota Y，et al.Evaluating balancing on social networks through the efficient solution of correlation clustering problems［J］.EURO Journal on Computational Optimization，2017，5（4）：467-498.

［20］Queiroga E，Subramanian A，F(xiàn)igueiredo R，et al.Integer programming formulations and efficient local search for relaxed correlation clustering［J］.Journal of Global Optimization，2021，81（4）：919-966.

［21］伍康，夏維，王子源.一種基于圖神經(jīng)網(wǎng)絡(luò)的改進(jìn)鄰域搜索算法［J］.計算機(jī)應(yīng)用研究，2024，41（5）：1402-1408.（Wu Kang，Xia Wei，Wang Ziyuan.Improved neighborhood search algorithm based on graph neural network［J］.Application Research of Computers，2024，41（5）：1402-1408.）

［22］Cordner N，Kollios G.An efficient local search algorithm for correlation clustering on large graphs［C］//Proc of International Conference on Combinatorial Optimization and Applications.Cham：Springer，2023：3-15.

［23］Soldatenko A，Semenova D，Ibragimova E.On heuristic algorithm with greedy strategy for the correlation clustering problem solution［C］//Proc of International Conference on Distributed Computer and Communication Networks：Control，Computation，Communications.Cham：Springer，2024：462-477.

［24］Brusco M J，Doreian P.Partitioning signed networks using relocation heuristics，tabu search，and variable neighborhood search［J］.Social Networks，2019，56：70-80.

［25］Zhou Yangming，Hao Jinkao，Duval B.Reinforcement learning based local search for grouping problems：a case study on graph coloring［J］.Expert Systems with Applications，2016，64：412-422.

［26］劉全，翟建偉，章宗長，等.深度強化學(xué)習(xí)綜述［J］.計算機(jī)學(xué)報，2018，41（1）：1-27.（Liu Quan，Zhai Jianwei，Zhang Zongchang，et al.A survey on deep reinforcement learning［J］.Chinese Journal of Computers，2018，41（1）：1-27.）

［27］Brimberg J，Salhi S，Todosijevic＇ R，et al.Variable neighborhood search：the power of change and simplicity［J］.Computers amp; Ope-rations Research，2023，155：106221.

［28］Jure L.SNAP datasets：Stanford large network dataset collection［EB/OL］.［2024］.http：//snap.stanford.edu/data 2014.

［29］Kunegis J.KONECT：the Koblenz network collection［C］//Proc of the 22nd International Conference on World Wide Web.New York：ACM Press，2013：1343-1350.

［30］Hamby D M.A review of techniques for parameter sensitivity analysis of environmental models［J］.Environmental Monitoring and Assessment，1994，32（2）：135-154.