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

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

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

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