有向相依網(wǎng)絡(luò)的可控性研究

陳世明，程運(yùn)洪，鄧兵

（華東交通大學(xué) 電氣與自動化工程學(xué)院，江西 南昌 330013）

在過去幾十年中，復(fù)雜網(wǎng)絡(luò)研究吸引了許多來自不同科學(xué)領(lǐng)域?qū)W者的關(guān)注[1]。而以往的工作主要集中在對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜性及其與網(wǎng)絡(luò)動力學(xué)行為之間關(guān)系的研究，通過對復(fù)雜網(wǎng)絡(luò)拓?fù)湫再|(zhì)、復(fù)雜網(wǎng)絡(luò)演化模型以及動力學(xué)行為的分析，揭示出隱藏在復(fù)雜系統(tǒng)中的一系列共同規(guī)律，對于把握復(fù)雜系統(tǒng)的宏觀特征及調(diào)節(jié)復(fù)雜系統(tǒng)上的動力學(xué)行為都將具有重要意義[2-3]。隨著對復(fù)雜網(wǎng)絡(luò)研究的進(jìn)一步深入，復(fù)雜網(wǎng)絡(luò)可控性的研究得到了充分的關(guān)注與重視。Lin[4]給出了線性時(shí)不變控制系統(tǒng)“結(jié)構(gòu)”和“結(jié)構(gòu)可控性”的概念，并通過研究找到了結(jié)構(gòu)可控性的充要條件；Liu等[5]基于線性時(shí)不變控制系統(tǒng)的結(jié)構(gòu)可控性理論，對實(shí)際復(fù)雜系統(tǒng)進(jìn)行了研究并建立了網(wǎng)絡(luò)結(jié)構(gòu)可控性模型；Jia[6-7]發(fā)現(xiàn)了兩種不同的網(wǎng)絡(luò)控制模式：集中式控制和分布式控制；同時(shí)基于控制能力和隨機(jī)抽樣算法對有向復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)可控性做了進(jìn)一步探索，隨后一些研究者通過改變連接邊的方向?qū)崿F(xiàn)了網(wǎng)絡(luò)可控性的優(yōu)化[8-10]。目前復(fù)雜網(wǎng)絡(luò)可控性研究已經(jīng)取得了眾多的重要成果，但復(fù)雜網(wǎng)絡(luò)控制方面的研究仍然處于起步階段，還有很多未解決的理論問題，例如結(jié)構(gòu)可控性理論無法適用于無向網(wǎng)絡(luò)、權(quán)重網(wǎng)絡(luò)和時(shí)變網(wǎng)絡(luò)的可控性等問題。針對結(jié)構(gòu)可控性理論僅適用于有向網(wǎng)絡(luò)的局限性，Yuan[11]引入了嚴(yán)格可控性(exact controllability)的概念，證明完全控制復(fù)雜網(wǎng)絡(luò)所需的最少控制器數(shù)目由網(wǎng)絡(luò)矩陣特征值的最大重?cái)?shù)決定，并提出了利用矩陣初等變換甄別網(wǎng)絡(luò)中需要被獨(dú)立控制的節(jié)點(diǎn)的方法，通過對大量真實(shí)網(wǎng)絡(luò)和模型網(wǎng)絡(luò)的計(jì)算結(jié)果表明了嚴(yán)格可控性理論的有效性和實(shí)用性；Li[12]針對實(shí)際網(wǎng)絡(luò)的分型特征，運(yùn)用嚴(yán)格可控性理論對分型網(wǎng)絡(luò)的可控性進(jìn)行了分析?；趩螌佑邢蚓W(wǎng)絡(luò)和無可控性進(jìn)行的研究已取得了較大突破。但現(xiàn)實(shí)中的網(wǎng)絡(luò)通常是相互依存的，例如，公交–地鐵網(wǎng)絡(luò)、電力–通信網(wǎng)絡(luò)、電力–供水網(wǎng)絡(luò)等，且通過研究已經(jīng)發(fā)現(xiàn)相依網(wǎng)絡(luò)的動態(tài)特性如級聯(lián)失效[13-17]、擴(kuò)散現(xiàn)象[18]、演化博弈動力學(xué)[19]、同步性[20]等，均明顯區(qū)別于單層網(wǎng)絡(luò)。怎樣合理地控制相依網(wǎng)絡(luò)將是面臨的重要挑戰(zhàn)。Yuan[21]運(yùn)用嚴(yán)格可控性理論對多重網(wǎng)絡(luò)的可控性進(jìn)行了研究，發(fā)現(xiàn)在多關(guān)系網(wǎng)中存在主導(dǎo)關(guān)系網(wǎng)，其結(jié)構(gòu)和連接權(quán)重對于整個(gè)網(wǎng)絡(luò)的嚴(yán)格可控性起主導(dǎo)作用；在多層網(wǎng)中，不同層間的連接方式以及疏密程度對整個(gè)網(wǎng)絡(luò)的嚴(yán)格可控能力都有重要的影響，并且發(fā)現(xiàn)在層間加入少量連接能夠大大提高整個(gè)網(wǎng)絡(luò)的可控能力。Nie[22]分析了多層網(wǎng)絡(luò)中層間連邊結(jié)構(gòu)對網(wǎng)絡(luò)可控性能的影響，研究發(fā)現(xiàn)層間連邊比例較小時(shí)，網(wǎng)絡(luò)最少驅(qū)動節(jié)點(diǎn)的數(shù)目隨著連邊度相關(guān)性的增加而減小，層間連邊同配性強(qiáng)的網(wǎng)絡(luò)易于控制；當(dāng)層間連邊比例較大時(shí)，則會出現(xiàn)相反的情況，層間連邊異配性強(qiáng)的網(wǎng)絡(luò)易于控制。然而以上研究僅分析了網(wǎng)絡(luò)層間的連接方式及網(wǎng)絡(luò)層間連接邊的度相關(guān)性對無向相依網(wǎng)絡(luò)可控性的影響，卻未考慮到實(shí)際網(wǎng)絡(luò)中存在有向網(wǎng)絡(luò)相互依存的情況，例如在交通網(wǎng)絡(luò)與供電網(wǎng)絡(luò)中，某一時(shí)間內(nèi)列車的運(yùn)行方向是定向的，同時(shí)供電系統(tǒng)按照列車運(yùn)行的線路提供電力支持保證其正常運(yùn)行。在供電網(wǎng)絡(luò)中某一處發(fā)生故障會通過網(wǎng)絡(luò)之間的相依關(guān)系，將其傳遞到交通網(wǎng)絡(luò)中從而導(dǎo)致經(jīng)過這條線路的列車都無法運(yùn)行，反之亦然。這樣在某個(gè)網(wǎng)絡(luò)中產(chǎn)生的故障會因?yàn)楸舜碎g的相依關(guān)系，使得故障在兩個(gè)網(wǎng)絡(luò)之間相互蔓延，從而對網(wǎng)絡(luò)造成更大的破壞，由此表明有向相依網(wǎng)絡(luò)間的相依關(guān)系對整個(gè)有向相依網(wǎng)絡(luò)有重要影響。為了探究有向網(wǎng)絡(luò)間相依關(guān)系對網(wǎng)絡(luò)的影響，本文首先構(gòu)建了基本的有向相依網(wǎng)絡(luò)模型，并結(jié)合嚴(yán)格可控性理論，給出了基于最少控制輸入的可控性評判指標(biāo)；其次，針對相依方式對有向相依網(wǎng)絡(luò)可控性產(chǎn)生的影響，基于經(jīng)典的有向隨機(jī)網(wǎng)絡(luò)(DER)和有向無標(biāo)度網(wǎng)絡(luò)(DSF)，構(gòu)建了DERDER、DER-DSF、DSF-DSF 3類有向相依網(wǎng)絡(luò)模型，并研究了隨機(jī)相依方式下3類網(wǎng)絡(luò)的可控性能；最后，基于隨機(jī)相依方式下對網(wǎng)絡(luò)可控性的分析，提出了3種有向網(wǎng)絡(luò)的相依方式：最高入度與最高出度節(jié)點(diǎn)相依(HI-HO)、最高入度與最低出度節(jié)點(diǎn)相依(HI-LO)、最低入度與最低出度節(jié)點(diǎn)相依(LI-LO)，且在既定的3種相依方式下對網(wǎng)絡(luò)的可控性進(jìn)行了仿真分析。

1 有向相依網(wǎng)絡(luò)可控性

1.1 有向相依網(wǎng)絡(luò)

有向相依網(wǎng)絡(luò)由兩個(gè)有向子網(wǎng)絡(luò)(子網(wǎng)絡(luò)A和子網(wǎng)絡(luò)B)通過雙向連接線連接而成，表示子網(wǎng)絡(luò)A中的節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)為；表示子網(wǎng)絡(luò)B中的節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)為，子網(wǎng)絡(luò)之間的雙向連接線為網(wǎng)絡(luò)相依邊，其余單向連線為內(nèi)部邊。F表示節(jié)點(diǎn)相依比例。F包括和，其中表示子網(wǎng)絡(luò)A的相依節(jié)點(diǎn)數(shù)占子網(wǎng)絡(luò)A總節(jié)點(diǎn)數(shù)的比例值，表示子網(wǎng)絡(luò)B的相依節(jié)點(diǎn)數(shù)占子網(wǎng)絡(luò)B總節(jié)點(diǎn)數(shù)的比例值，即

圖 1 有向相依網(wǎng)絡(luò)Fig. 1 The interdependent directed network

1.2 嚴(yán)格可控性

在現(xiàn)代控制理論中，如果通過一些控制變量的輸入能使一個(gè)系統(tǒng)從任意初始狀態(tài)達(dá)到理想狀態(tài)，我們稱這個(gè)系統(tǒng)是可控的。這里只考慮線性時(shí)不變系統(tǒng)并且假設(shè)系統(tǒng)內(nèi)部未發(fā)生動態(tài)變化。有向相依網(wǎng)絡(luò)狀態(tài)方程為

定理1 對于一個(gè)可控系統(tǒng)來說，最少控制輸入個(gè)數(shù)是系統(tǒng)矩陣特征值中具有最大代數(shù)重?cái)?shù)的特征值所對應(yīng)的幾何重?cái)?shù)。

1.3 理論分析

對于滿足狀態(tài)方程(2)的系統(tǒng)來說，其節(jié)點(diǎn)總數(shù)是不變的且為，若使得系統(tǒng)滿足其可控性，需通過外部控制輸入作用于系統(tǒng)節(jié)點(diǎn)。假設(shè)得到外部控制輸入作用的節(jié)點(diǎn)個(gè)數(shù)為，未作用的節(jié)點(diǎn)個(gè)數(shù)為，則

對于可控系統(tǒng)來說，必然存在一個(gè)得到外部控制輸入作用節(jié)點(diǎn)的最小個(gè)數(shù)，記為，使得系統(tǒng)達(dá)到可控要求，并且未作用的節(jié)點(diǎn)個(gè)數(shù)達(dá)到最大，記為，得

從而可得

然而需要確定能夠達(dá)到控制效果所需的最少控制輸入個(gè)數(shù)。在這里將最小控制輸入個(gè)數(shù)定義為達(dá)到系統(tǒng)可控性要求時(shí)，輸入矩陣B秩的最小值，即

若滿足狀態(tài)方程(2)的系統(tǒng)是可控的，那么由PHB判定定理可知，對矩陣A的任意特征值，下式恒成立：

式中I為單位矩陣。

根據(jù)矩陣不等式關(guān)系得：

進(jìn)一步得

上式滿足恒成立關(guān)系，則：

進(jìn)一步可得

最后可得：

圖 2 有向相依網(wǎng)絡(luò)可控性Fig. 2 Controllability of the interdependent directed network

2 隨機(jī)相依方式下網(wǎng)絡(luò)可控性的仿真與分析

本文基于經(jīng)典的有向隨機(jī)網(wǎng)絡(luò)(DER)和有向無標(biāo)度網(wǎng)絡(luò)(DER)，構(gòu)建了DER-DER、DER-DSF、DSF-DSF 3類有向相依網(wǎng)絡(luò)模型。同時(shí)在隨機(jī)相依方式下，對不同相依比例的DER-DER網(wǎng)絡(luò)可控性進(jìn)行了獨(dú)立仿真實(shí)驗(yàn)。

在隨機(jī)相依方式下，通過對4組不同相依比例的DER-DER網(wǎng)絡(luò)可控性進(jìn)行多次仿真，其中網(wǎng)絡(luò)規(guī)模，T為實(shí)驗(yàn)次數(shù)，；相依比例為。從圖3(a)中可以發(fā)現(xiàn)在相依比例時(shí)，在區(qū)間內(nèi)出現(xiàn)明顯的波動，即網(wǎng)絡(luò)可控性在這一范圍內(nèi)出現(xiàn)很大的隨機(jī)性；同時(shí)結(jié)合圖3(b)、3(c)、3(d)可知，在相依比例、0.4、0.8時(shí)，同樣在一定范圍內(nèi)出現(xiàn)較大的波動。這表明，在同一相依比例下，隨機(jī)的相依方式使得網(wǎng)絡(luò)可控性表現(xiàn)出明顯的差異性，即有向網(wǎng)絡(luò)的相依方式直接影響著網(wǎng)絡(luò)的可控性。

通過對比以上4組不同相依比例下的網(wǎng)絡(luò)可控性發(fā)現(xiàn)，隨著相依比例F的逐漸增加，逐漸減小，即隨著相依比例的增加，網(wǎng)絡(luò)可控性逐漸增強(qiáng)。為了充分證明相依方式直接影響著有向相依網(wǎng)絡(luò)可控性，我們在隨機(jī)相依方式下對連續(xù)相依比例的3類有向相依網(wǎng)絡(luò)的可控性進(jìn)行了仿真分析。

圖 3 單一相依比例下DER-DER網(wǎng)絡(luò)的可控性Fig. 3 Controllability of DER-DER network with a single dependency ratio

在隨機(jī)相依方式下，通過對連續(xù)相依比例的DER-DER、DER-DSF、DSF-DSF這3類有向相依網(wǎng)絡(luò)的可控性進(jìn)行仿真，如圖4(a)所示，就DERDER有向相依網(wǎng)絡(luò)而言，隨著相依比例F的逐漸增加，總體呈現(xiàn)逐漸減小的趨勢，但由于相依方式的隨機(jī)性，DER-DER有向相依網(wǎng)絡(luò)中存在，的情況，同時(shí)在圖4(b)所示的DER-DSF有向相依網(wǎng)絡(luò)與圖4(c)所示的DSF-DSF有向相依網(wǎng)絡(luò)中均呈現(xiàn)與圖4(a)相同的變化規(guī)律，即網(wǎng)絡(luò)可控性在隨著相依比例增加而增強(qiáng)的過程中會出現(xiàn)一定程度的波動，從而表明有向相依網(wǎng)絡(luò)的可控性不僅與相依比例有著緊密相關(guān)，更與有向網(wǎng)絡(luò)的相依方式有著密不可分的關(guān)系，上述分析為有向相依網(wǎng)絡(luò)可控性的研究提供了充分條件。

圖 4 連續(xù)相依比例下網(wǎng)絡(luò)的可控性Fig. 4 Controllability of the network under continuous dependency ratio

3 有向相依網(wǎng)絡(luò)的相依方式及其可控性對比分析

基于隨機(jī)相依方式下對有向相依網(wǎng)絡(luò)可控性的分析，本文提出了有向網(wǎng)絡(luò)之間的3種相依方式：最高入度與最高出度節(jié)點(diǎn)相依(HI-HO)、最高入度與最低出度節(jié)點(diǎn)相依(HI-LO)、最低入度與最低出度節(jié)點(diǎn)相依(LI-LO)，同時(shí)針對3種相依方式構(gòu)建了如圖5所示的簡單有向相依網(wǎng)絡(luò)模型并分析了其可控性。

圖 5 有向相依網(wǎng)絡(luò)的相依方式Fig. 5 Dependent way of the interdependent directed network

針對提出的3種有向網(wǎng)絡(luò)相依方式，在DERDER、DER-DSF、DSF-DSF 3類有向相依網(wǎng)絡(luò)中對網(wǎng)絡(luò)可控性進(jìn)行了仿真對比。如圖6(a)所示，在DER-DER有向相依網(wǎng)絡(luò)中對3種既定相依方式而言，均呈現(xiàn)隨著相依比例F增大而減小的趨勢，同時(shí)在圖6(b)所示的DER-DSF有向相依網(wǎng)絡(luò)與圖6(c)所示的DSF-DSF有向相依網(wǎng)絡(luò)中，的變化趨勢與圖6(a)相同，即在同一有向相依網(wǎng)絡(luò)中對任一既定相依方式來說，網(wǎng)絡(luò)可控性會隨著相依比例的增加而逐漸增強(qiáng)。在圖6(a)所示的DER-DER有向相依網(wǎng)絡(luò)中，針對相同相依比例，對3種既定相依方式下的網(wǎng)絡(luò)可控性進(jìn)行對比發(fā)現(xiàn)(LI-LO)＜(HI-LO)＜(HI-HO)，同時(shí)在圖6(b)所示的DER-DSF有向相依網(wǎng)絡(luò)與圖6(c)所示的DSF-DSF有向相依網(wǎng)絡(luò)中，在同等相依比例下有(LI-LO)＜(HI-LO)＜(HI-HO)，即在同一網(wǎng)絡(luò)中相同相依比例下，基于最小入度與最小出度節(jié)點(diǎn)相依的有向相依網(wǎng)絡(luò)可控性最強(qiáng)，而基于最大入度與最大出度節(jié)點(diǎn)相依的有向相依網(wǎng)絡(luò)可控性最弱。

圖 6 不同相依方式下有向相依網(wǎng)絡(luò)可控性Fig. 6 Controllability of the interdependent directed network under different dependent way

4 結(jié)束語

相互依存的復(fù)雜網(wǎng)絡(luò)廣泛存在于實(shí)際復(fù)雜系統(tǒng)中，且往往存在有向網(wǎng)絡(luò)之間的相依，本文首先構(gòu)建了基本的有向相依網(wǎng)絡(luò)模型，并結(jié)合嚴(yán)格可控性理論，給出了基于最少控制輸入的可控性評判指標(biāo)；考慮相依方式對有向相依網(wǎng)絡(luò)可控性產(chǎn)生的影響，本文基于經(jīng)典的有向隨機(jī)網(wǎng)絡(luò)(DER)和有向無標(biāo)度網(wǎng)絡(luò)(DSF)，構(gòu)建了DER-DER、DER-DSF、DSF-DSF 三類有向相依網(wǎng)絡(luò)模型，并在4組不同相依比例下，研究了隨機(jī)相依方式下的DER-DER網(wǎng)絡(luò)的可控性能，研究發(fā)現(xiàn)，隨著相依比例的增加，網(wǎng)絡(luò)可控性逐漸增強(qiáng)。但每組相依比例下的網(wǎng)絡(luò)可控性均會在一定范圍內(nèi)出現(xiàn)大幅的波動。為了進(jìn)一步證實(shí)相依方式影響著網(wǎng)絡(luò)的可控性，通過在隨機(jī)相依方式下對連續(xù)相依比例下的3類有向相依網(wǎng)絡(luò)可控性進(jìn)行了仿真，我們發(fā)現(xiàn)隨著相依比例的逐漸增加，網(wǎng)絡(luò)可控性總體均呈現(xiàn)逐漸增強(qiáng)的趨勢，但由于相依方式的隨機(jī)性，網(wǎng)絡(luò)可控性在增強(qiáng)過程中會出現(xiàn)明顯的波動情況，即有向網(wǎng)絡(luò)的相依方式對網(wǎng)絡(luò)可控性產(chǎn)生著重要影響。

基于分析本文提出了3種有向網(wǎng)絡(luò)的相依方式：最高入度與最高出度節(jié)點(diǎn)相依(HI-HO)、最高入度與最低出度節(jié)點(diǎn)相依(HI-LO)、最低入度與最低出度節(jié)點(diǎn)相依(LI-LO)，同時(shí)就提出的3種相依方式在3類有向相依網(wǎng)絡(luò)中對網(wǎng)絡(luò)可控性進(jìn)行了仿真對比，且通過對比發(fā)現(xiàn)，在同一網(wǎng)絡(luò)中同等相依比例下，基于最低入度與最低出度節(jié)點(diǎn)相依的有向相依網(wǎng)絡(luò)可控性最強(qiáng)，而基于最高入度與最高出度節(jié)點(diǎn)相依的有向相依網(wǎng)絡(luò)可控性最弱。研究證實(shí)了有向網(wǎng)絡(luò)相依方式密切影響著網(wǎng)絡(luò)的可控性，且得到3種相依方式下有向相依網(wǎng)絡(luò)可控性的強(qiáng)弱關(guān)系，這為構(gòu)建強(qiáng)可控性能的實(shí)際有向相依網(wǎng)絡(luò)提供了參考依據(jù)。