復雜網絡中最小驅動邊的選取研究

陳志昂 紀志堅

摘要：? 針對復雜網絡中邊動態的能控性問題，本文主要對有向復雜網絡下維持系統邊能控的最小驅動邊的選取問題進行研究。建立了復雜網絡中邊動態的系統模型，從結構能控性和精確能控性兩個方面研究邊動態能控性，提出了邊控制力的概念。同時，對有向復雜網絡中最小驅動邊的選取提出了新的算法，并通過實例，對所提出的理論結果進行驗證。驗證結果表明，與以往驅動邊的選取方法相比，新算法建立在Kalman秩判據基礎之上，通過引入邊控制力的概念，可有效避免干擾，從而更加精準高效地尋找維持網絡邊動態能控所需的最小驅動邊，且該算法適用于任意結構的有向復雜網絡。該研究為解決具有任意結構復雜網絡的邊能控性問題和最小驅動邊的選取問題提供了理論基礎。

關鍵詞：? 復雜網絡;? 最小驅動邊;? 邊能控;? 邊動態

中圖分類號： TP273; TP393 文獻標識碼： A

自然界中存在著各種復雜網絡，不僅包括城市交通網絡和電力網絡等有形網絡，而且還包括人際關系網絡、代謝網絡和生態網絡等無形網絡[12]。因此，對復雜網絡可控性的研究已成為近10年來的熱點問題。為理解復雜網絡的演化及網絡結構和動態過程之間的相互關系[34]，國內外學者做了很多研究，但復雜網絡的可控性問題仍然沒有得到解決。R.E.Kalman[5]最先提出了動態系統可控性的概念，即用一組代數矩陣來檢驗給定系統是否可控，然而由于網絡中權重測量的困難性，使用固定權重很難在數值上驗證Kalman能控性。因此，Lin C T[6]從圖論的角度分析了復雜網絡的可控性，提出了結構能控性的概念，并給出了代表該系統可控的關鍵結構——仙人掌，這為復雜網絡的結構化系統理論奠定了基礎。與Kalman能控性相比，結構能控性具有簡潔直接的優點，而且它還可以避免復雜繁瑣的代數運算。近年來，由于復雜網絡控制問題的重要性，國內外學者對復雜網絡可控性的研究越來越多[710]。Liu Y Y等人[11]研究了復雜網絡結構能控性的最小輸入定理。盡管結構能控性理論為解決有向網絡的可控性問題提供了有效工具，但當網絡中的邊為無向邊或有鏈接權重時，便違反了結構能控性理論中參數自由的條件。為解決該問題，Yuan Z Z等人[12]提出了精確能控性的概念，并證明了網絡完全能控所需的最小驅動節點數等于系統矩陣中特征值的最大幾何重數。大多數關于網絡可控性的研究都集中在節點動力學系統上，而在許多現實世界的網絡中，邊動態系統的研究具有非常重要的意義。例如，在具有路由器（定向網絡）的互聯網中，邊表示物理連接，譬如無線連接。因此，研究邊動態比研究點動態更有意義。2011年，T.Nepusz等人[13]首次提出了復雜網絡邊動態的概念，并構造了邊動態系統的數學模型，分析了網絡節點的度對動態系統邊能控性的影響，證明了網絡G邊動態系統完全能控所需的驅動邊的最小數目等于其線圖L（G）所對應的鄰接矩陣W的秩虧的數目;Pang S P等人[14]研究了邊動態系統特性，通過引入精確能控性理論，提出了研究復雜網絡邊能控性的框架。目前，關于邊動態的研究取得了一定進展[1516]，但對于任意網絡結構和任意鏈接權重下的復雜網絡，仍然缺少一個通用的邊能控性框架。基于此，本文主要對無權重的有向復雜網絡的邊能控性進行深入研究，提出了邊控制力的概念，并在邊控制力的基礎上設計了一種新的算法，該算法可以準確高效地找到一組能使網絡邊動態能控的最小驅動邊。該研究為復雜網絡邊動態中最小驅動邊的選取提供了理論基礎。

1 預備知識

1.2 邊動態能控性分析

經典Kalman能控性判據表明，對于由式（2）描述的動態系統，如果在有限時間內，可以驅使系統從任意初始狀態到達任意最終狀態，則稱該系統是完全能控。當系統完全能控時，可控性矩陣C滿秩，即rank＼[C=H，WH，…，WM-1H＼]=M，其中M表示網絡中狀態邊的數量;當系統不完全能控時，此時rank（C）

在計算可控性矩陣的秩rank（C）時，需要狀態矩陣W-T和輸入矩陣H中的元素參數。然而對于大多數復雜網絡系統，矩陣中的元素參數通常并不可得知，因此矩陣W-T和矩陣H通常被視為結構矩陣[6]，即矩陣中的元素為0，或者是獨立的自由參數。如果存在一組非零元素賦給狀態矩陣W-T和輸入矩陣H后，系統滿足Kalman能控性判據，即此時可控性矩陣C滿秩，則稱該系統在結構上是可控的。

基于以上分析，對于由式（2）描述的動態系統，其系統可控性可依據結構能控性理論進行研究。假定矩陣W-T和矩陣H是結構矩陣，即其元素是零或獨立的自由參數，由線圖的性質可知，線圖L（G）中的節點對應原始圖G中的邊。因此，在結構能控性理論中，可以通過計算線圖L（G）中節點的最大匹配數來確定原始網絡G中的最小驅動邊數。根據精確能控性理論，具有相同對角元素的阻尼矩陣T，對式（2）所確定的系統可控性并沒有影響，這是被嚴格證明的[13]。阻尼矩陣T映射到拓撲圖中為自環，因此由阻尼矩陣T產生的所有自環，在分析邊動態系統能控性時可以被忽略。基于以上分析，邊動態系統能控性的關鍵是確定線圖L（G）中驅動邊的最小數目MD（原始圖G中驅動節點的最小數目ND）及最小驅動邊（驅動節點）的位置。

當輸入矩陣H未知時，找到一組能使系統完全能控的驅動邊尤為重要。Pang S P等人[15]通過將精確能控性理論引入邊動態系統，提出了一個邊動態的理論框架，即復雜網絡邊動態中任意節點的可控性完全由其對應的局部加權結構決定。雖然該框架為復雜網絡邊動態中驅動邊最小數目的確定提供了理論基礎，但該理論框架并不是對任意結構的網絡都適用。對于任意結構的復雜網絡，仍然缺乏一個廣泛通用的框架對其邊動態能控性進行分析。

2 主要結論

2.1 相關概念

雖然邊動態系統的能控性對復雜網絡能控性的研究非常重要，但對于邊動態中最小驅動邊的選取問題卻少有研究。受點動態系統中控制集中性[18]概念的啟發，為更深入的研究邊動態系統的能控性，本文引入邊控制力概念。

定義1 邊控制力。對于系統（2），C（xi）的值等于當僅有輸入信號ui被添加到邊緣xi時可控性矩陣C的秩。C（xi）的值表示邊xi對系統（2）的控制能力，稱為邊控制力。其中可控性矩陣C=＼[H，WH，…，WM-1H＼]，輸入矩陣H=＼[ui＼]。根據定義1，邊xi的控制力C（xi）的值越大，表明邊xi在系統能控性中起的作用越大。

定義2 被控邊。由輸入信號ui直接作用的狀態邊稱被控邊。

定義3 最小驅動邊和最小驅動邊集。在所有被控邊中選擇一個最大的集合，如果集合中的所有邊都不與其它邊共享相同的輸入，則該集合稱為最小驅動邊集，用MODS表示。該集合中的邊稱為最小驅動邊，驅動邊的數目記為MD。

定義4 無效邊。被控邊中，不能維持系統完全能控的邊稱為無效邊。

引理1[15] 網絡G中，驅動邊的最小數量MD為M-rank（W），矩陣W中的線性相關行所對應的邊，是系統完全可控所需的最小數目的驅動邊。外部輸入信號ui應該施加在驅動邊尾部節點上。

基于精確能控性理論和線圖性質，可以證明線圖L（G）中驅動節點（原圖G中的驅動邊）的最小數目為M-rank（W），其中M為網絡G中的邊數，最小驅動邊的數目MD等于矩陣W的秩虧，即MD=M-rank（W）。對于任意結構的有向網絡G，最小驅動邊數MD由系統矩陣中零特征值[19]對應的最大幾何重數決定，可用下式計算

MD=max{1，M-rank（W）}（3）

當M=rank（W）時，最小驅動邊的數量MD=1，此時至少需要一個輸入來控制網絡，在這種情況下，任意一條邊都可以被選為驅動邊。

利用引理1和式（3）可以求取維持系統能控的最小驅動邊的數量，并判斷系統（2）邊能控所需的所有驅動邊，但需要強調的是，引理1提到的最小驅動邊的選取方式不嚴格，并且只對大型稀疏網絡有效[19]。在研究復雜網絡邊動態能控性的過程中存在兩個關鍵問題，一是維持系統能控的驅動邊的最小數目，二是最小驅動邊的位置。事實上，后者比前者更復雜。關于第2個問題，現有理論（如引理1）并沒有提供一個有效的方法，因為在一些特殊的網絡中，引理1提到的方法不足以確保網絡完全能控。因此，確定具有任意結構的邊動態系統，完全可控所需的最小驅動邊非常重要。

2.2 最小驅動邊的算法實現

最小驅動邊的選取方法是從鄰接矩陣W中的線性相關行中進行選取，矩陣W中的線性相關行所對應的邊是維持系統邊動態能控所需的最小驅動邊。然而在有些網絡中，并非所有線性相關行所對應的邊都適合選作驅動邊，因為即使在有些邊上添加獨立的輸入信號后，系統依然不滿足Kalman能控性條件[20]。考慮到該問題，本文提出以下算法來選取能使系統邊能控的最小驅動邊。該算法根據邊控制力的大小來選取一組滿足Kalman秩判據的驅動邊，為有向復雜網絡最小驅動邊的選取提供有效工具。最小驅動邊的選取步驟如下：

與以往驅動邊的選取方法不同，新算法建立在Kalman秩判據的基礎上，使得該算法能避免無效邊的干擾，更加精確的找到一組滿足邊動態系統能控的最小數目的驅動邊，而且該算法對任意結構的有向復雜網絡都適用。

2.3 實例分析

本文給出實例，對所提出的理論結果進行驗證。考慮一個由6個狀態節點組成的有向無權重復雜網絡，6節點有向無權重網絡如圖1所示。

由以上步驟可知，滿足系統邊能控所需的最小驅動邊集為MODS={x1，x5}。即分別對邊x1和邊x5添加獨立的外部輸入，可使圖1所示網絡滿足邊動態能控。

由以上例子可以看出，與以往方法相比，新算法在Kalman秩判據基礎上引入邊控制力的概念，在邊動態中最小驅動邊的選取上更精確，能夠有效避免無效邊;同時，通過邊控制力的大小可以分析每條邊在系統能控性中占據的作用，從而有針對性的改善系統能控性。

3 結束語

本文從結構能控性和精確能控性兩方面，對有向無權重復雜網絡中的邊動態能控性進行分析，提出了邊控制力的概念，并對邊動態中最小驅動邊的選取問題設計了新算法。與以往最小驅動邊的選取方法相比，新算法可以更精確高效的實現有向復雜網絡的邊動態可控，但對于更為復雜的網絡，尤其是無向網絡，本文設計的算法在實現此類網絡最小驅動邊的選取上還存在一定的困難，需要后續研究來解決此問題。本文研究的邊動態中最小驅動邊的選取算法，為以后解決更復雜的邊動態能控性問題提供了新的方法和方向。

參考文獻：

[1] 汪小帆， 李翔， 陳關榮.網絡科學導論[M]. 北京： 高等教育出版社， 2012.

[2] 汪小帆， 李翔， 陳關榮. 復雜網絡理論及其應用[M]. 北京： 清華大學出版社， 2006.

[3] Newman M E J. The structure and function of complex networks[J]. SIAM Review， 2003， 45（2）： 167256.

[4] Albert R， Barabasi A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics， 2002， 74（1）： 4797.

[5] Kalman R E. Mathematical description of linear dynamical systems[J]. SIAM J Control， 1963， 1（2）： 152192.

[6] Lin C T. Structural controllability[J]. IEEE Transactions on Automatic Control， 1974， 19（3）： 201208.

[7] Qi Y Q， Zhang H S. Output feedback control and stabilization for multiplicative noise systems with intermittentobservations[J]. IEEE Transactions on Cybernetics， 2017， 48（8）： 21282138.

[8] Commault C， Jacob W， Boukhobza T. On the fixed controllable subspace in linear structured systems[J]. Systems & Control Letters， 2017， 102（7）： 4247.

[9] Ji Z J， Yu H S. A new perspective to graphical characterization of multiagent controllability[J]. IEEE Transactions on Cybernetics， 2016， 47（6）： 14711483.

[10] Shields R W， Pearson J B. Structural controllability of multiinputlinear systems[J]. IEEE Transactions on Automatic Control， 1976， 21（2）： 203212.

[11] Liu Y Y， Slotine J J， Barabsi A L. Controllability of complex networks[J]. Nature， 2011， 473（7346）： ?167173.

[12] Yuan Z Z， Zhao C， Di Z R， et al. Exact controllability of complex networks[J]. Nature Communications， 2013（4）： 24472455.

[13] Nepusz T， Vicsek T. Controlling edge dynamics in complex networks[J]. Nature Physics， 2012， 8（7）： 568573.

[14] Pang S P， Hao F. Controllable subspace of edge dynamics in complex networks[J]. Physica A： Statistical Mechanics and its Applications， 2017， 481：? 209223.

[15] Pang S P， Wang W X， Hao F， et al. Universal framework for edge controllability of complex networks[J]. Science Reports， 2017， 7（1）： 42244235.

[16] Gao J X， Liu Y Y， Souza D， et al. Target control of complex networks[J]. Nature Communications， 2014， 12（5）： 54155422.

[17] Hosoe S. Determination of Ggenericdimensions of controllable subspaces and its application[J]. IEEE Transactions on Automatic Control， 1980， 25（6）： 11921196.

[18] Liu Y Y， Slotine J J， Barabási A L. Control centrality and hierarchical structure in complex networks[J]. PLos One， 2012， 7（9）： e44459.

[19] Miller I. Probability， random variables， and stochastic processes[J]. IEEE Transactions on Acoustics Speech， 2003， 33（6）： 16371637.

[20] Poljak S. On the generic dimension of controllable subspaces[J]. IEEE Transactions on Automatic Control， 1990， 35（3）： 367369.