邊轉換與增加對有向網絡能控性的影響

張虎林　李成鐵　王立夫

摘要： 復雜網絡的不同類型邊轉換（方向改變）和在不同節點間增加邊對網絡能控性有不同影響，為了更好地了解有向網絡邊轉換和增加對網絡能控性影響，提出一種邊分類方法，把邊根據節點類別和匹配關系分成12種類型，并給出辨識算法?；诖朔诸惤o出網絡邊轉換和增加時網絡能控性（驅動節點數目）的變化規律。通過模型網絡和實際網絡分析了每種邊在網絡中的比例，并分析了邊轉換和增加時驅動節點數目變化。結果驗證了定理的正確性。

關鍵詞： 網絡能控性;驅動節點;最大匹配;轉換邊;增加邊

中圖分類號： N94文獻標識碼： A

Influence of Alteration and Addition of Edges on Directed Network Controllability

ZHANG Hulin， LI Chengtie， WANG Lifu

Abstract：The alternation of different types of edges （direction changed） and the addition of edges between different nodes in complex networks will have different effect on the controllability of the network. In order to better understand the influence of altering different edges and adding different edges on network controllability in directed networks， this paper proposes a classification method of edges. According to the node category and matching relationship， the directed edges are divided into twelve types， and the algorithm of identification is given. Based on the classification， the change law of network controllability （the number of driving nodes） is given when the edges of networks are altered and added. Through the simulation experiment of the model networks and the actual networks， the proportion of different types of edges is analyzed. When edges are altered and added， the changes in the number of driven nodes are analyzed in the model networks and the actual networks. The correctness of the theorems of this article are verified.

Key words： network controllability; driver node; maximum matching; alteration of edges; addition of edges

0 引言

近些年來，隨著網絡科學的發展，人們發現各種復雜系統（相互作用和依賴的各部分組成的具有特定功能的整體）可以由節點和連邊組成的網絡來表示，其中網絡中各節點表示系統的各個組成部分，節點間的邊表示各組成部分的相互作用和依賴關系。例如，計算機網絡［1］可以看成由很多獨立工作的計算機通過傳輸介質相連而成的網絡［1］，其中獨立工作的計算機看作節點，傳輸介質看作節點間的連邊；電力網絡［2-3］可以看作由各個變電站通過電纜連接而成的網絡，其中變電站看作節點，電纜看作連接節點間的連邊。類似的還有交通網絡［4］和生物網絡［5］等。

研究復雜網絡［6-7］的最終目的是尋找有效的控制手段控制網絡行為。從經典控制理論可知，控制網絡行為的前提是該網絡必須是完全能控的，因此研究復雜網絡能控性具有重要的理論意義。此外，復雜網絡能控性的研究也具有重要的現實意義。例如，在基因調控網絡［8］中，選擇哪些基因作為藥物靶點，能使整個生物網絡達到預期狀態；在社交網絡里［9］，選擇哪些平臺發布信息，能使信息的傳播達到期望結果。很多實際網絡都涉及復雜網絡能控性問題。

為使復雜網絡完全能控，將線性系統能控性理論應用到復雜網絡。2011年，Liu等［10］提出一種求解復雜網絡能控性所需的最少驅動節點數目的方法，該方法采用圖論的匹配定理［11-12］，將復雜網絡的能控性問題轉換為有向網絡的最大匹配問題，從而建立關于復雜網絡可控性的理論研究框架。然而對于無向網絡的能控性問題該方法并不適用。因此，Yuan等［13］通過采用PBH能控性判據提出復雜網絡精確能控性的理論框架，可求解有邊權重和任意結構網絡的能控性。基于這兩個框架，許多學者對時變網絡能控性［14］，多層網絡能控性［15］，對稱網絡結構能控性［16］等方面進行了深入研究。

隨著研究的深入，人們發現網絡拓撲結構對復雜網絡的能控性有重要影響。網絡拓撲結構變化分為節點或邊的變化，其中節點的變化會造成邊數目的變化，邊的變化不會造成節點數目的變化。因此邊的變化對網絡能控性的變化更易判斷，而目前邊變化的研究包括邊變換對網絡能控性優化和邊的失效。對于邊變換對網絡能控性優化主要從以下3種方法考慮［17］：增加邊［18-22］、交換邊［23］、轉換邊（改變邊的方向）［24-26］。Zhang等［21］提出了一種增加邊的算法，利用給出的最小生成森林使網絡加邊的成本最小，該算法使網絡增加邊的數目最少并實現網絡的結構能控。Wang等［22］給出一種網絡加邊的優化算法，該算法將介數中心性作為網絡加邊的成本，使加邊成本最小且實現網絡結構能控。Rong等［23］提出一種在保持度分布不變的約束下重新布線的算法，該算法可改變網絡能控性并提高網絡的魯棒性。Hou等［24］提出一種基于匹配邊的節點和邊的分類方法，在此基礎上提出一種轉換邊的算法，該算法通過局部信息來改變網絡的能控性，而且網絡的優化成本大幅度降低，比如電力網絡［27］。對于邊的失效，Hao等［28］根據節點和無標度網絡的特征，提出了14種基于兩條邊重要性函數的邊攻擊策略，使網絡能控性降低。Lou等［29］給出一種邊的分類方法，根據該邊的分類對網絡的邊進行攻擊，從而實現網絡能控性改變。此外，還有許多研究通過邊的變化改變網絡拓撲結構，從而對網絡能控性造成影響。

綜上所述，發現當前通過邊的變化實現對網絡能控性影響的研究主要集中在邊失效對網絡能控性影響和邊變換對網絡能控性優化上，并未從理論層面出發，給出轉換邊和增加邊對網絡能控性的影響。對于整個復雜網絡，哪些邊轉換或在哪些節點間增加邊能改變網絡能控性，哪些邊轉換對網絡能控性沒有影響，至今沒有明確的結論。因此，本文為了對此問題進行研究，將網絡中邊進行分類，并從理論層面給出不同邊變換對網絡能控性影響的確切結論。首先根據節點類型和邊的匹配關系提出一種有向網絡的邊分類方式，給出邊辨識算法，然后研究了有向網絡中邊轉換和節點間增加邊對網絡能控性的影響，最后通過模型網絡和實際網絡仿真，分析了不同類型邊在網絡中的占比并驗證了轉換邊和增加邊定理的有效性。

1 復雜網絡能控性

考慮一個N個節點的復雜網絡，其動力學方程表示為

（1）

其中，x（t）=［x1，x2，…，xN］T表示網絡中節點的狀態，xj（t）表示第j個節點在t時刻時的狀態，A=［aij］∈RN×N為網絡的鄰接矩陣，其中aij代表節點j作用到節點i的強度，aij＞0表示積極作用，aij＜0表示消極作用，aij=0表示節點j與節點i無連接關系，即節點j不作用到節點i；u（t）=［u1，u2，…，uM］T表示M個輸入控制信號在t時刻的輸入量；B∈RN×M稱為輸入矩陣，B表示外部輸入節點與內部節點的耦合關系，bij表示輸入信號uj（t）與節點i之間的耦合關系。

對于復雜網絡系統（1），若存在一個分段連續的u（t），可在有限的時間［t0，tf］內從任意初始狀態x（t0）驅動到任何期望的最終狀態x（tf），則稱此系統的狀態是完全能控的。在控制理論中，通過卡爾曼判據判斷系統是否完全能控，系統（1）完全能控當且僅當能控性矩陣C=［B，AB，…，AN-1B］是滿秩的，即rank（C）=N。因此要使一個給定網絡能控，則需要尋找一個輸入矩陣B使得能控性矩陣C滿秩。當復雜網絡節點間不考慮連接強度時，即不考慮矩陣A與B具體權值，僅考慮矩陣中的元素是零或獨立自由參數，這時矩陣A與B稱為結構化矩陣。如果存在A與B中一組非零值，使得網絡是能控的，則稱系統（1）為結構能控，也可記為（A，B）結構能控。根據有向邊的方向，在下文中將邊的起始節點稱為頭節點，邊的結束節點稱為尾節點。

對于有向復雜網絡G=（V，E），其中V和E為網絡的節點集和邊集。如果網絡邊集E的一個子集M中沒有兩條邊共享一個公共的頭節點或尾節點，則M稱為G的一個匹配。G中邊數最多的匹配稱為G的最大匹配。最大匹配一般是非唯一的，可由Hopcroft-Karp算法［30］得到。如果一個節點是匹配中某條邊的尾節點，則該節點為匹配節點，否則為非匹配節點。對于網絡節點i，從網絡中其他節點指向節點i的邊數目是節點i的入度，節點i指向其他節點的邊數目是節點i的出度。

Liu等［10］把圖論中匹配理論與結構能控性相結合，給出一種求解最小驅動節點集分析復雜網絡能控性的理論框架，并給出最小輸入定理，證明了實現網絡結構能控所需獨立控制的節點集合等于非最大匹配的節點集合，其中需要被不共享輸入信號控制的節點稱為網絡的驅動節點，驅動節點數目用ND表示，使得網絡結構能控所需的最小驅動節點集合為最小驅動節點集（Minimum Driven Node Set，簡稱MDS），通過對MDS中節點施加外部輸入控制信號可使控制信息傳達到網絡中每一個節點，實現整個網絡的完全能控。

引理1 最小輸入定理［10］：控制有向網絡G的最小輸入節點數NI與最小驅動節點數目ND等價。若有向網絡G存在完全匹配，NI等于1并且網絡中任意一個節點可作驅動節點；否則，NI等于網絡中最大匹配后沒有被匹配的節點數。用式（2）表示：

（2）

其中，N為有向網絡中節點數目，|M|為網絡中最大匹配節點數目。

網絡的能控性nD的大小由網絡所需的最小驅動節點數與網絡節點總數的比值來計算，即nD=ND/N，nD的大小表示該網絡被控的難易程度，nD越小，網絡越易被控制，nD越大，網絡越難被控制。

有向網絡中，若實現網絡完全能控，需對個數固定的未匹配節點進行控制。但是由于一個網絡存在多組不同最大匹配，使網絡有很多不同的MDS。根據節點參與MDS的程度，將節點分為三類，定義［31］如下：

定義1 如果一個節點參與全部的MDS，則這個節點為關鍵節點；如果一個節點不全參與全部的MDS，則這個節點為間歇節點；如果一個節點不參與任何一個MDS，則這個節點為冗余節點。

對于圖1d網絡，存在3組最大匹配和MDS，如圖1a、1b和1c所示。其中節點1參與全部MDS，故為關鍵節點；節點2不參與任何一個MDS，故為冗余節點；節點3，4，5參與部分MDS，故為間歇節點。

2 邊分類及類型辨識

2.1 邊的分類方式

有向網絡中，節點的類型有所不同，節點間通過有向邊連接，網絡中邊的最大匹配也是非唯一的，故參與最大匹配的邊也存在不同。根據邊匹配關系與邊兩端節點的類型將邊進行分類。

類型1 關鍵輸出完全匹配和冗余輸入完全匹配邊：如果該邊的頭節點為關鍵節點，尾節點為冗余節點，并且該邊參與全部最大匹配，則這個邊稱為關鍵輸出完全匹配和冗余輸入完全匹配邊（Critical Output Matching and Redundant Input Matching，簡稱COM-RIM）。

類型2 間歇輸出完全匹配和冗余輸入完全匹配邊：如果該邊的頭節點為間歇節點，尾節點為冗余節點，并且該邊參與全部最大匹配，則這個邊稱為間歇輸出完全匹配和冗余輸入完全匹配邊（Intermittent Output Matching and Redundant Input Matching，簡稱IOM-RIM）。

類型3 冗余輸出完全匹配和冗余輸入完全匹配邊：如果該邊的頭節點為冗余節點，尾節點為冗余節點，并且該邊參與全部最大匹配，則這個邊稱為冗余輸出完全匹配和冗余輸入完全匹配邊（Redundant Output Matching and Redundant Input Matching，簡稱ROM-RIM）。

類型4 關鍵輸出不完全匹配和冗余輸入不完全匹配邊：如果該邊的頭節點為關鍵節點，尾節點為冗余節點，并且該邊參與部分最大匹配，則這個邊稱為關鍵輸出不完全匹配和冗余輸入不完全匹配邊（Critical Output No Perfect Matching and Redundant Input No Perfect Matching，簡稱COOPM-RIOPM）。

類型5 間歇輸出不完全匹配和冗余輸入不完全匹配邊：如果該邊的頭節點為間歇節點，尾節點為冗余節點，并且該邊參與部分最大匹配，則這個邊稱為間歇輸出不完全匹配和冗余輸入不完全匹配邊（Intermittent Output No Perfect Matching and Redundant Input No Perfect Matching，簡稱IOOPM-RIOPM）。

類型6 冗余輸出不完全匹配和冗余輸入不完全匹配邊：如果該邊的頭節點為冗余節點，尾節點為冗余節點，并且該邊參與部分最大匹配，則這個邊稱為冗余輸出不完全匹配和冗余輸入不完全匹配邊（Redundant Output No Perfect Matching and Redundant Input No Perfect Matching，簡稱ROOPM-RIOPM）。

類型7 關鍵輸出不完全匹配和間歇輸入不完全匹配邊：如果該邊的頭節點為關鍵節點，尾節點為間歇節點，并且該邊參與部分最大匹配，則這個邊稱為關鍵輸出不完全匹配和間歇輸入不完全匹配邊（Critical Output No Perfect Matching and Intermittent Input No Perfect Matching，簡稱COOPM-IIOPM）。

類型8 間歇輸出不完全匹配和間歇輸入不完全匹配邊：如果該邊的頭節點為間歇節點，尾節點為間歇節點，并且該邊參與部分最大匹配，則這個邊稱為間歇輸出不完全匹配和間歇輸入不完全匹配邊（Intermittent Output No Perfect Matching and Intermittent Input No Perfect Matching，簡稱IOOPM-IIOPM）。

類型9 冗余輸出不完全匹配和間歇輸入不完全匹配邊：如果該邊的頭節點為冗余節點，尾節點為間歇節點，并且該邊參與部分最大匹配，則這個邊稱為冗余輸出不完全匹配和間歇輸入不完全匹配邊（Redundant Output No Perfect Matching and Intermittent Input No Perfect Matching，簡稱ROOPM-IIOPM）。

類型10 關鍵輸出不匹配和冗余輸入不匹配邊：如果該邊的頭節點為關鍵節點，尾節點為冗余節點，并且該邊不參與任意一個最大匹配，則這個邊稱為關鍵輸出不匹配和冗余不完全匹配邊（Critical Output No Matching and Redundant Input No Matching，簡稱COOM-RIOM）。

類型11 間歇輸出不匹配和冗余輸入不匹配邊：如果該邊的頭節點為間歇節點，尾節點為冗余節點，并且該邊不參與任意一個最大匹配，則這個邊稱為間歇輸出不匹配和冗余輸入不匹配邊（Intermittent Output No Matching and Redundant Input No Matching，簡稱IOOM-RIOM）。

類型12 冗余輸出不匹配和冗余輸入不匹配邊：如果該邊的頭節點為冗余節點，尾節點為冗余節點，并且該邊不參與任意一個最大匹配，則這個邊稱為冗余輸出不匹配和冗余輸入不匹配邊（Redundant Output No Matching and Redundant Input No Matching，簡稱ROOM-RIOM）。

對于圖2a和2b網絡，對應二分網絡如圖3a和3b所示，根據邊分類可知，邊（1→2）參與全部最大匹配，且節點1為關鍵節點，節點2為冗余節點，所以邊（1→2）為COM-RIM邊。同理邊（1→3）為COOM-RIOM邊，邊（2→3）、（6→7）、（16→18）和（18→17）為ROM-RIM邊，邊（3→4）和（3→5）為ROOPM-IIOPM邊，邊（4→8）、（5→6）和（20→19）為IOM-RIM邊，邊（5→7）為IOOM-RIOM邊，邊（8→9）為ROOPM-RIOPM邊，邊（10→9）為COOPM-RIOPM邊，邊（11→12）和（11→20）為IOOPM-IIOPM邊，邊（13→11）和（13→14）為COOPM-IIOPM邊，邊（14→16）為IOOPM-RIOPM邊，邊（15→16）為COOPM-RIOPM邊，邊（16→17）為ROOM-RIOM邊。

2.2 邊辨識算法

為研究轉換邊和增加邊對網絡能控性的影響，需先對網絡邊類型進行辨識。本節給出辨識網絡邊類型的算法，流程圖如圖4所示。具體步驟為：

步驟1：識別網絡的最大匹配邊數m和網絡總邊數L，并令參數a=0。

步驟2：將網絡節點編號，記為y1，y2，…yN（N為網絡節點數目）。選擇網絡中一條邊（yi→yj），去除該邊后，識別新網絡最大匹配邊數m1，判斷是否滿足m1=m-1，若不滿足，則跳至步驟3；否則跳至步驟4。

步驟3：去除節點yi的輸入邊和節點yj的輸出邊后，識別新網絡的最大匹配邊數m2，判斷是否滿足m2=m-1，若不滿足，則跳至步驟6；否則跳至步驟5。

步驟4：邊（yi→yj）為完全匹配邊。判斷節點yi是否存在輸入邊，若節點yi不存在輸入邊，則該邊為COM-RIM邊；若存在，則去掉節點yi的輸入邊，識別新網絡最大匹配邊數m3，若滿足m3=m-1，則該邊為ROM-RIM邊；否則為IOM-RIM邊。

步驟5：邊（yi→yj）為不匹配邊。判斷節點是否存在輸入邊，若節點yi不存在輸入邊，則該邊為COOM-RIOM邊；若存在，則去除節點yi的輸入邊，識別新網絡的最大匹配邊數m4，若滿足m4=m-1，則該邊為ROOM-RIOM邊；否則為IOOM-RIOM邊。

步驟6：邊（yi→yj）為不完全匹配邊。判斷節點yi是否存在輸入邊，若不存在輸入邊，則跳至步驟7；若存在輸入邊，則跳至步驟8。

步驟7：節點yi為關鍵節點，去除節點yj的輸入邊，識別新網絡的最大匹配邊數m5，若滿足m5=m-1，則節點yj為冗余節點，而邊（yi→yj）為COOPM-RIOPM邊；若不滿足m5=m-1，則節點為間歇節點，邊（yi→yj）為COOPM-IIOPM邊。

步驟8：去除節點yi的輸入邊，識別新網絡的最大匹配邊數m6，若滿足m6=m-1，則跳至步驟9；若不滿足m6=m-1，則跳至步驟10。

步驟9：節點yi為冗余節點，然后去除節點yj的輸入邊，并識別新網絡的最大匹配邊數m7，若滿足m7=m-1，則節點yj為冗余節點，邊（yi→yj）為ROOPM-RIOPM邊；若不滿足m7=m-1，則節點為間歇節點，而邊（yi→yj）為ROOPM-IIOPM邊。

步驟10：節點yi為間歇節點，然后去除節點yj的輸入邊，識別新網絡的最大匹配邊數m8，若滿足m8=m-1，則節點yj為冗余節點，邊（yi→yj）為IOOPM-RIOPM邊；若不滿足m8=m-1，則節點yj為間歇節點，邊（yi→yj）為IOOPM-IIOPM邊。

步驟11：若a＜L，則a=a+1，返回步驟2；否則結束操作。

3 轉換邊與增加邊對網絡能控性的影響

3.1 轉換邊對網絡能控性的影響

對于有向網絡，轉換不同的邊對網絡能控性有不同的影響?？紤]到轉換邊的現實意義，本節給出邊轉換使網絡驅動節點數目減少和不變的變化規律。

定理1 對于N個節點的有向網絡，轉換一條邊類型為COOM-RIOM、IOOM-RIOM、COOPM-RIOPM、IOOPM-RIOPM，如果該邊尾節點出度為0；或轉換一條邊類型為COOPM-IIOPM、IOOPM-IIOPM，如果該邊尾節點出度為0且入度為1，則網絡中的最大匹配數增加1，驅動節點數減少1。

證明：設網絡有N個節點，最大匹配邊為L，由二分圖得到最大匹配中被匹配的節點個數為M，最小驅動節點數目為ND=N-M，轉換邊后的最小驅動節點數目為ND′。對于COOPM-RIOPM邊或COOM-RIOM邊，原頭節點是關鍵節點，轉換邊后，被原尾節點匹配，變為冗余節點。原尾節點為冗余節點，轉換邊后，被其它節點匹配，故被匹配節點數目為M+1，驅動節點數目變為ND′=N-（M+1）=N-M-1=ND-1，驅動節點數目減少1。對于IOOM-RIOM邊或IOOPM-RIOPM邊，原頭節點是間歇節點，轉換邊后，被原冗余節點匹配，變為冗余節點。原尾節點為冗余節點，轉換邊后，仍被其他節點匹配，故被匹配的節點數目為M+1，驅動節點數目變為ND′=N-（M+1）=N-M-1=ND-1，驅動節點數目減少1。對于COOPM-IIOPM邊或IOOPM-IIOPM邊，原頭節點為關鍵節點或間歇節點，轉換邊后，被原尾節點匹配，變為冗余節點。原尾節點為間歇節點且出度為0，轉換邊后，變為關鍵節點，而同頭節點下的其他間歇節點必會有一個被匹配，故被匹配節點數目為M+1，驅動節點數目為ND′=N-（M+1）=N-M-1=ND-1，驅動節點數目減少1。

定理2 對于N個節點有向網絡，轉換一條邊類型為COM-RIM、ROOM-RIOM、ROOPM-RIOPM、IOM-RIM，如果該邊尾節點出度為0；或轉換一條ROOPM-IIOPM邊，如果該邊尾節點出度為0且入度為1；或轉換一條ROM-RIM邊，如果該邊尾節點出度為0且入度為2，則網絡中最大匹配數不增加，驅動節點數也不改變。

證明：設網絡有N個節點，最大匹配邊為L，由二分圖得到最大匹配中被匹配的節點個數為M，驅動節點個數為ND=N-M，轉換邊后的最小驅動節點數目為ND′。對于ROM-RIM邊、ROOM-RIOM邊或ROOPM-RIOPM邊，原頭節點為冗余節點，轉換邊后，被原尾節點匹配。原尾節點為冗余節點，存在其他節點匹配該尾節點，轉換邊后，仍被其他節點匹配，故網絡中被匹配節點數目為M，驅動節點數目為ND′=N-M=ND，驅動節點的數目不變。對于COM-RIM邊、IOM-RIM邊或ROOPM-IIOPM邊，原頭節點為關鍵節點、間歇節點或冗余節點，轉換邊后，被原尾節點匹配。原尾節點為間歇節點或冗余節點且出度為0，轉換邊后，不被匹配，變為關鍵節點，故網絡中被匹配節點數目為M，驅動節點數目為ND′=N-M=ND，驅動節點數目保持不變。

3.2 增加邊對網絡能控性的影響

對于有向網絡，在不同節點間增加邊對網絡能控性有不同的影響?？紤]到增加邊的現實意義，本節將給出增加邊使網絡驅動節點數目減少的變化規律。

定理3 對于N個節點的有向網絡，考慮以下情況時，網絡最大匹配數增加1，驅動節點數減少1。1）在COOPM-IIOPM邊、IOOPM-IIOPM邊、ROOPM-IIOPM邊的尾節點之間增加一條邊l1，如果l1的頭節點出度為1；2）在COOPM-RIOPM邊、IOOPM-RIOPM邊的頭節點與COOPM-RIOPM邊、IOOPM-RIOPM邊、ROOPM-RIOPM邊的頭節點之間增加一條邊l2，如果l2的尾節點為關鍵節點或間歇節點；3）在出度為0的邊尾節點與邊類型為COM-RIM、COOM-RIOM、COOPM-IIOPM或COOPM-RIOPM的頭節點間增加一條邊l3。