基于最小路徑覆蓋的復(fù)雜網(wǎng)絡(luò)目標(biāo)控制的研究.pdf

1、復(fù)雜網(wǎng)絡(luò)研究的最終目的是控制網(wǎng)絡(luò)。近年來，復(fù)雜網(wǎng)絡(luò)的研究都集中在通過控制一個(gè)最小的驅(qū)動(dòng)節(jié)點(diǎn)集來控制整個(gè)網(wǎng)絡(luò)。然而，一般情況下，控制整個(gè)網(wǎng)絡(luò)既不靈活也不必要。實(shí)事上，目標(biāo)控制是必要的，也是可行的，即只需要控制網(wǎng)絡(luò)中部分節(jié)點(diǎn)，來維持整個(gè)網(wǎng)絡(luò)的正常運(yùn)行。
　　2014年貪婪算法被提出，其可以近似地求出控制網(wǎng)絡(luò)中給定目標(biāo)節(jié)點(diǎn)所需要的驅(qū)動(dòng)節(jié)點(diǎn)集。由于這種貪婪算法的核心是使用最大匹配算法不停地迭代，而最大匹配算法只適用于計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的匹

2、配，即貪婪算法依賴于全局網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；另外，最大匹配集往往不是唯一的，而在貪婪算法每次迭代過程中最大匹配集的不同選擇會(huì)導(dǎo)致最終產(chǎn)生不同的結(jié)果，即貪婪算法的結(jié)果受最大匹配集的選取的影響。因此，本文提出了一種新的目標(biāo)控制方法。
　　本文將圖論中的最小路徑覆蓋與復(fù)雜網(wǎng)絡(luò)的目標(biāo)控制聯(lián)系起來，發(fā)現(xiàn)覆蓋網(wǎng)絡(luò)中所有目標(biāo)節(jié)點(diǎn)所需最少且不相交的路徑數(shù)，即目標(biāo)節(jié)點(diǎn)的最小路徑覆蓋數(shù)，等于目標(biāo)控制所需要的驅(qū)動(dòng)節(jié)點(diǎn)數(shù)，且最小路徑覆蓋中的所有路徑的起點(diǎn)組成的

3、集合可作為一個(gè)最小的驅(qū)動(dòng)節(jié)點(diǎn)集，用以控制網(wǎng)絡(luò)中所有的目標(biāo)節(jié)點(diǎn)。同時(shí)，本文給出了兩個(gè)計(jì)算目標(biāo)節(jié)點(diǎn)最小路徑覆蓋的算法，以及控制目標(biāo)節(jié)點(diǎn)所需要的驅(qū)動(dòng)節(jié)點(diǎn)數(shù)上界與下界的計(jì)算方法。為了驗(yàn)證這種基于最小路徑覆蓋的目標(biāo)控制方法的合理性與效率，本文對(duì)兩個(gè)生成的模型網(wǎng)絡(luò)以及幾個(gè)實(shí)際網(wǎng)絡(luò)進(jìn)行目標(biāo)控制。并根據(jù)兩種不同的目標(biāo)節(jié)點(diǎn)選取策略，即隨機(jī)選取策略和蓄意選取策略，運(yùn)用最小路徑覆蓋算法和上下界計(jì)算方法計(jì)算出目標(biāo)控制所需要的驅(qū)動(dòng)節(jié)點(diǎn)數(shù)及其上下界。結(jié)果表明，本文