網(wǎng)絡(luò)是復(fù)雜系統(tǒng)中近鄰關(guān)系的一種直觀表示，它由節(jié)點(diǎn)和邊組成，節(jié)點(diǎn)代表系統(tǒng)的組成單元，每條邊連接兩個(gè)節(jié)點(diǎn)，意味著某種近鄰關(guān)系。雖說(shuō)網(wǎng)絡(luò)上的邊只連接兩個(gè)節(jié)點(diǎn)，但網(wǎng)絡(luò)組合優(yōu)化問(wèn)題所包含的約束卻常常是多體約束。最小支配集合問(wèn)題就是這樣一個(gè)問(wèn)題。

　　最小支配集合是由網(wǎng)絡(luò)中一部分節(jié)點(diǎn)構(gòu)成的，它具有這樣的性質(zhì)：第一，這個(gè)集合必須是最小的；第二、如果某個(gè)節(jié)點(diǎn)不在該集合里面，那它至少有一個(gè)鄰居在里面。換句話說(shuō)，通過(guò)先訪問(wèn)最小支配集合，最多只需再跳一步就可訪問(wèn)到網(wǎng)絡(luò)中任何一個(gè)節(jié)點(diǎn)。最小支配集合對(duì)于解決資源優(yōu)化配置、網(wǎng)絡(luò)搜索等問(wèn)題很是重要。

　　每個(gè)節(jié)點(diǎn)帶來(lái)一個(gè)多體約束：或者它自己，或者它的某個(gè)鄰居，必須屬于最小支配集合。如果某節(jié)點(diǎn)沒(méi)有鄰居，那它必須屬于最小支配集合。如果某節(jié)點(diǎn) i 只有一個(gè)鄰居 j 而該鄰居自己還有其它鄰居，那么將 j 放進(jìn)最小支配集合更為經(jīng)濟(jì)，因?yàn)檫@樣的話，j 的所有鄰居（包括 i）都不必屬于最小支配集合了。

　　理論物理研究所研究員周海軍的研究團(tuán)隊(duì)對(duì)最小支配集合問(wèn)題進(jìn)行過(guò)深入研究 [1]。他們注意到上述化簡(jiǎn)方法對(duì)于實(shí)際網(wǎng)絡(luò)系統(tǒng)效果有限，簡(jiǎn)化之后網(wǎng)絡(luò)仍然包含很多節(jié)點(diǎn)和邊，不能得到精確的全局最優(yōu)解。最近，周海軍研究員參與的葡萄牙、美國(guó)、中國(guó)合作研究對(duì)于超網(wǎng)絡(luò)的一般覆蓋問(wèn)題進(jìn)行了理論探索 [2]。該論文發(fā)現(xiàn)如果將最小支配集合問(wèn)題表述為超網(wǎng)絡(luò)的覆蓋問(wèn)題，即將每個(gè)節(jié)點(diǎn) i 的約束用一條超邊來(lái)表示，該超邊連接節(jié)點(diǎn) i 和它的所有鄰居，然后在超網(wǎng)絡(luò)上優(yōu)化問(wèn)題進(jìn)行化簡(jiǎn)，常常能導(dǎo)致問(wèn)題被簡(jiǎn)化更多，有時(shí)甚至直接達(dá)到全局最優(yōu)解。

　　圖一：GLR （普通網(wǎng)絡(luò)化簡(jiǎn)方法 [1]）；Hypergraph （超網(wǎng)絡(luò)化簡(jiǎn)方法 [2]）；Core （化簡(jiǎn)后網(wǎng)絡(luò)的大?。?；橫軸是不同的實(shí)際測(cè)試網(wǎng)絡(luò) 　　 

　　這一工作表明用超網(wǎng)絡(luò)表示來(lái)處理普通網(wǎng)絡(luò)多體約束問(wèn)題，將連接兩個(gè)節(jié)點(diǎn)的邊推廣為連接多個(gè)節(jié)點(diǎn)的超邊，有可能帶來(lái)算法上的較大改進(jìn)。更多理論細(xì)節(jié)，參見(jiàn)文獻(xiàn) [2]。 

　　[1]  J.-H. Zhao, Y. Habibulla, H.-J. Zhou, Statistical mechanics of the minimum dominating set problem, Journal of Statistical Physics 159, 1154 (2015).

　　[2]  B. C. Coutinho, A.-K. Wu, H.-J. Zhou, Y.-Y. Liu, Covering problems and core percolations on hypergraphs, Physical Review Letters 124, 248301 (2020).