潘玉劍，李 翔

（復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院電子工程系自適應(yīng)網(wǎng)絡(luò)與控制研究室，上海200433）

0 引言

現(xiàn)實(shí)世界中存在著各式各樣的由相互關(guān)聯(lián)和相互作用的若干組成部分按一定規(guī)律連接而成的整體系統(tǒng)，如工程系統(tǒng)、生物系統(tǒng)、經(jīng)濟(jì)系統(tǒng)、社會(huì)系統(tǒng)等。人們?cè)谘芯窟@些系統(tǒng)的理論表述中，常常將它們抽去具體的物理或社會(huì)含義而抽象化為一般意義下的系統(tǒng)，這種處理方法有助于揭示系統(tǒng)的一般特性。代表性地，卡爾曼將狀態(tài)空間法引入到對(duì)于系統(tǒng)的狀態(tài)描述。在此基礎(chǔ)之上，卡爾曼進(jìn)一步提出了能控性和能觀測(cè)性這兩個(gè)表征系統(tǒng)特性的重要概念，它們是線性系統(tǒng)理論中兩個(gè)最基本的概念［1－2］。網(wǎng)絡(luò)和系統(tǒng)一樣無(wú)時(shí)不在、無(wú)處不在［3］，網(wǎng)絡(luò)的科學(xué)研究是從圖論開(kāi)始的。1736年，歐拉通過(guò)證明Koningsberg七橋問(wèn)題的無(wú)解從而建立了現(xiàn)代數(shù)學(xué)意義下的圖論。1960年前后Erdos和Renyi關(guān)于隨機(jī)網(wǎng)絡(luò)的生成及演化的奠基性工作形成了后來(lái)半個(gè)世紀(jì)數(shù)學(xué)圖論的核心［4－5］。

從圖論來(lái)研究以有向圖表征的線性時(shí)不變動(dòng)力系統(tǒng)的能控性始于20世紀(jì)70年代，作者們把這樣的可控性研究稱(chēng)為結(jié)構(gòu)可控性［6－8］。傳統(tǒng)的控制理論側(cè)重于單個(gè)高維系統(tǒng)內(nèi)部的控制，對(duì)以圖表征的節(jié)點(diǎn)之間存在的規(guī)則（不規(guī)則）結(jié)構(gòu)沒(méi)有給予充分的關(guān)注。融合圖論的結(jié)構(gòu)可控性更傾向于研究節(jié)點(diǎn)間拓?fù)潢P(guān)系對(duì)可控性的影響。換句話(huà)說(shuō)，經(jīng)典控制理論中的可控性強(qiáng)調(diào)單個(gè)個(gè)體內(nèi)在動(dòng)力學(xué)特性的研究，而結(jié)構(gòu)可控性則從節(jié)點(diǎn)子系統(tǒng)之間存在的相互影響出發(fā)，著重研究節(jié)點(diǎn)子系統(tǒng)之間的關(guān)系對(duì)動(dòng)力學(xué)的影響。前者對(duì)應(yīng)的是微觀個(gè)體動(dòng)力學(xué)特性，而后者對(duì)應(yīng)的是宏觀群體的集群動(dòng)力學(xué)行為。

信息技術(shù)的迅猛發(fā)展為人們?cè)诤暧^層面上研究大規(guī)模和高維度的復(fù)雜網(wǎng)絡(luò)提供了有力支持。1998年—1999年先后在《Nature》和《Science》雜志上刊發(fā)了兩篇開(kāi)創(chuàng)性文章：一篇是當(dāng)時(shí)的博士生 Watts與其導(dǎo)師Strogatz教授的小世界網(wǎng)絡(luò)研究論文［9］，另一篇是Barabasi教授及其當(dāng)時(shí)的博士生Albert對(duì)于無(wú)標(biāo)度網(wǎng)絡(luò)的研究論文［10］。從此，復(fù)雜網(wǎng)絡(luò)研究熱潮在21世紀(jì)初迅速展開(kāi)，大量的相關(guān)研究工作為我們揭示了復(fù)雜網(wǎng)絡(luò)中存在的各種基本特征和群體現(xiàn)象。結(jié)合結(jié)構(gòu)可控性的提出［6－8］和大規(guī)模復(fù)雜網(wǎng)絡(luò)研究的興起［9－10］，近年來(lái)網(wǎng)絡(luò)結(jié)構(gòu)可控性領(lǐng)域的研究此起彼伏、方興未艾，有關(guān)網(wǎng)絡(luò)結(jié)構(gòu)可控性的研究工作和成果大量涌現(xiàn)［11－20，27－29］。本文圍繞結(jié)構(gòu)可控性對(duì)當(dāng)前從靜態(tài)網(wǎng)絡(luò)到時(shí)效網(wǎng)絡(luò)的研究現(xiàn)狀進(jìn)行綜述。

1 經(jīng)典控制理論、結(jié)構(gòu)可控性及其延伸

1.1 線性系統(tǒng)的可控性

一個(gè)線性時(shí)不變（也稱(chēng)定常）系統(tǒng)可以用微分方程˙x（t）＝Sx（t）＋Bu（t）來(lái)表示，其中x（t）＝（x1（t），x2（t），…，xN（t））T∈RN為狀態(tài)變量，S∈RN×N為系統(tǒng)矩陣，B∈RN×M為輸入矩陣，u（t）＝（u1（t），u2（t），…，uN（t））T∈RM為輸入控制變量。對(duì)于上述線性定常系統(tǒng)，如果存在一個(gè)分段連續(xù)的輸入u（t）能在有限的時(shí)間區(qū)間［t0，t1］內(nèi)使得系統(tǒng)由某一初始狀態(tài)x（t）轉(zhuǎn)移到任一指定的終端狀態(tài)x（tf）（t0≤t＜tf≤t1），則稱(chēng)此狀態(tài)是能控的。若系統(tǒng)的所有狀態(tài)都是能控的，則稱(chēng)此系統(tǒng)是狀態(tài)完全能控的，或簡(jiǎn)稱(chēng)系統(tǒng)是完全能控的。該系統(tǒng)完全能控的充分必要條件為：rank［B SB … SN－1B］＝N，其中N 為系統(tǒng)矩陣S的維數(shù)；矩陣Wc＝［B SB … SN－1B］稱(chēng)為系統(tǒng)的卡爾曼能控性判別矩陣［5，34］。通常，將上述線性定常系統(tǒng)簡(jiǎn)略表示為（S，B）。

相應(yīng)地，一個(gè)線性時(shí)變系統(tǒng)可以用微分方程˙x（t）＝S（t）x（t）＋B（t）u（t）來(lái)表示。時(shí)變系統(tǒng)能控性的定義與定常系統(tǒng)的類(lèi)似，只不過(guò)在這里S（t）、B（t）是時(shí)變矩陣而非常系數(shù)矩陣。對(duì)于上述線性時(shí)變系統(tǒng)，如果存在一個(gè)分段連續(xù)的輸入u（t）能在有限的時(shí)間區(qū)間［t0，t1］內(nèi)使得系統(tǒng)由時(shí)間t0的某一初始狀態(tài)x（t0）轉(zhuǎn)移到指定時(shí)間點(diǎn)tf的任一終端狀態(tài)x（tf）（t0＜tf≤t1），則稱(chēng)此狀態(tài)是在t0時(shí)刻能控的。若系統(tǒng)所有的狀態(tài)在t0時(shí)刻都是能控的，則稱(chēng)此系統(tǒng)在t0時(shí)刻是狀態(tài)完全能控的，或簡(jiǎn)稱(chēng)系統(tǒng)在t0時(shí)刻是完全能控的。由于系統(tǒng)矩陣S（t）是時(shí)變的，通常無(wú)法給出類(lèi)似線性定常系統(tǒng)的緊湊型可控性判別矩陣的數(shù)學(xué)表達(dá)式。類(lèi)似地，通常將線性時(shí)變系統(tǒng)簡(jiǎn)略表示為（S（t），B（t））。

1.2 靜態(tài)網(wǎng)絡(luò)的結(jié)構(gòu)可控性

若將線性定常系統(tǒng)的系統(tǒng)矩陣S換成由一個(gè)表示網(wǎng)絡(luò)拓?fù)潢P(guān)系的鄰接矩陣A，方程可改寫(xiě)為（t）＝A′x（t）＋Bu（t），其中A′為網(wǎng)絡(luò)鄰接矩陣A的轉(zhuǎn)置。從數(shù)學(xué)形式上比較改寫(xiě)前后兩種表達(dá)形式，它們本質(zhì)上并無(wú)多大區(qū)別，都是一個(gè)一階線性常微分方程（組），但從物理意義上比較，兩者意義相去甚遠(yuǎn)：1）前者的矩陣S為系統(tǒng)矩陣，整個(gè)表達(dá)式描述的是系統(tǒng)自身參數(shù)之間的相互影響和變化關(guān)系，這樣的x（t）被稱(chēng)為參數(shù)空間；2）后者的矩陣A為鄰接矩陣，整個(gè)表達(dá)式描述的是網(wǎng)絡(luò)群體中各個(gè)個(gè)體之間的相互影響關(guān)系，這樣的x（t）被稱(chēng)為網(wǎng)絡(luò)空間。

在這里，后者描述的正是網(wǎng)絡(luò)結(jié)構(gòu)可控性的問(wèn)題，可進(jìn)一步分為兩大類(lèi)：第一類(lèi)為判定問(wèn)題，即給定輸入位置信息（輸入矩陣B）和輸入控制器數(shù)目（輸入向量u（t）），判定網(wǎng)絡(luò)是否結(jié)構(gòu)可控；第二類(lèi)為優(yōu)化問(wèn)題，可細(xì)分為：1）在網(wǎng)絡(luò)結(jié)構(gòu)可控的前提下，給定適當(dāng)?shù)妮斎胛恢眯畔ⅲㄝ斎刖仃嘊）來(lái)最小化輸入控制器數(shù)目（輸入向量u（t））。2）在網(wǎng)絡(luò)結(jié)構(gòu)可控的前提下，給定適當(dāng)?shù)妮斎肟刂破鲾?shù)目（輸入向量u（t））來(lái)簡(jiǎn)化輸入位置信息（輸入矩陣B）。

為更好地闡述結(jié)構(gòu)可控性相關(guān)概念及其條件，首先給出如下幾個(gè)定義［2，6］：

定義1 對(duì)于一個(gè)矩陣A＊，若它的元素要么是零，要么是一個(gè)自由參量，則稱(chēng)矩陣A＊為結(jié)構(gòu)矩陣。

定義4 對(duì)于一個(gè)由結(jié)構(gòu)矩陣組成的系統(tǒng)（A＊，B＊），如果存在一個(gè)完全可控的定值系統(tǒng)），并且（，）∈（A＊，B＊），則稱(chēng)系統(tǒng)（A＊，B＊）是結(jié)構(gòu)可控的。

結(jié)合上述LTI系統(tǒng)可控性和結(jié)構(gòu)矩陣的定義，Lin［6］給出了由系統(tǒng)（A′，B）表示的有向網(wǎng)絡(luò)結(jié)構(gòu)可控的充要條件［6］：1）網(wǎng)絡(luò)結(jié)構(gòu)不變，即矩陣A是一個(gè)固定的結(jié)構(gòu)矩陣。2）網(wǎng)絡(luò)中不存在不可達(dá)節(jié)點(diǎn)，即以任一輸入為起點(diǎn)都至少存在一條有向路徑到達(dá)網(wǎng)絡(luò)中任意其他節(jié)點(diǎn)。3）具有這樣一種外部輸入的網(wǎng)絡(luò)中不存在擴(kuò)張。若用V和U分別表示該網(wǎng)絡(luò)本身的節(jié)點(diǎn)集合以及外部輸入控制器集合，E和E′分別表示網(wǎng)絡(luò)本身的邊集以及存在于控制器與網(wǎng)絡(luò)節(jié)點(diǎn)之間的邊集，則擴(kuò)張?jiān)跀?shù)學(xué)上可表示為：存在一個(gè)子集Sb?V以及與之對(duì)應(yīng)的鄰集T（Sb）＝｛vj｜（vj→vi）∈（E∪E′），vj∈（V∪U），vi∈Sb｝，并且｜T（sb）｜＜｜Sb｜。

對(duì)應(yīng)于上述充要條件，Lin給出了判定結(jié)構(gòu)可控的圖論判據(jù)，即掌狀結(jié)構(gòu)，它由干、枝、芽、圈以及U根因子連接等一些基本結(jié)構(gòu)組成。通過(guò)直觀的圖論映射方式，作者把原本需要用復(fù)雜數(shù)學(xué)計(jì)算來(lái)確定的矩陣秩大小問(wèn)題轉(zhuǎn)化為一個(gè)純圖論問(wèn)題：只要給出輸入控制的數(shù)目（輸入向量u（t））和位置（輸入矩陣B），就能通過(guò)嘗試找出網(wǎng)絡(luò)中的掌狀結(jié)構(gòu)來(lái)判斷該系統(tǒng)是否是結(jié)構(gòu)可控的。

隨著大規(guī)模的系統(tǒng)網(wǎng)絡(luò)研究成為社會(huì)、經(jīng)濟(jì)、工程、生物等諸多領(lǐng)域的熱點(diǎn)，人們關(guān)注的問(wèn)題和焦點(diǎn)不僅僅是根據(jù)給定輸入位置信息（輸入矩陣B）和輸入控制器數(shù)目（輸入向量u（t））來(lái)機(jī)械式地判定網(wǎng)絡(luò)是否結(jié)構(gòu)可控（即結(jié)構(gòu)可控的第一類(lèi)問(wèn)題），一個(gè)更為迫切的問(wèn)題是如何深入理解結(jié)構(gòu)可控和網(wǎng)絡(luò)結(jié)構(gòu)之間的關(guān)系，即在保證可控的前提下如何優(yōu)化控制器數(shù)目（即結(jié)構(gòu)可控的第二類(lèi)問(wèn)題）。Lombadi等［21］首次將結(jié)構(gòu)可控的概念應(yīng)用到物理和系統(tǒng)生物網(wǎng)絡(luò)。他們發(fā)現(xiàn)結(jié)構(gòu)可控所展示和表達(dá)的不僅僅是節(jié)點(diǎn)間的上下游或隸屬關(guān)系，它與內(nèi)在的網(wǎng)絡(luò)結(jié)構(gòu)之間存在著彼此交錯(cuò)且復(fù)雜微妙的關(guān)系。結(jié)合結(jié)構(gòu)可控性和有向網(wǎng)絡(luò)的匹配，Liu等［11］對(duì)上述問(wèn)題給出了一個(gè)相對(duì)完整的回答。

根據(jù)文獻(xiàn)［11，21］，首先闡述幾個(gè)與有向圖匹配相關(guān)的定義：

定義5 對(duì)有向圖G（V，E），設(shè)M∈E。如果M中任意兩條邊都沒(méi)有共同的起點(diǎn)（有向邊的頭）或者終點(diǎn)（有向邊的尾），那么稱(chēng)M為有向圖G（V，E）的一個(gè)匹配。

定義6 所有作為匹配M中邊終點(diǎn)（有向邊的尾）的節(jié)點(diǎn)稱(chēng)為網(wǎng)絡(luò)的匹配節(jié)點(diǎn)，網(wǎng)絡(luò)中其他節(jié)點(diǎn)均為不匹配節(jié)點(diǎn)。對(duì)于有向圖的任一匹配M，它的匹配節(jié)點(diǎn)數(shù)目一定為｜M｜。

定義7 圖G（V，E）尺度所有匹配中匹配節(jié)點(diǎn)數(shù)目最多的那些匹配稱(chēng)為最大匹配，本文中均用M＊表示，且｜M＊｜為常數(shù)。

圖1 由有向網(wǎng)絡(luò)匹配中的邊和節(jié)點(diǎn)組成的基本網(wǎng)路結(jié)構(gòu)Fig.1 The basic structures consisted of nodes and edges in a matching of a directed network

根據(jù)上述匹配的定義，網(wǎng)絡(luò)某個(gè)匹配中所有的邊和節(jié)點(diǎn)可組成兩種基本結(jié)構(gòu)：有向路徑和有向圈，如圖1所示。利用Lin給出的充要條件，分別對(duì)有向路徑和有向圈進(jìn)行判定。首先對(duì)于有向路徑，它明顯存在擴(kuò)張。如圖1a所示，設(shè)S＝｛1，2，3，4，5｝，若不對(duì)節(jié)點(diǎn)1施加控制（即去掉節(jié)點(diǎn)I），則T（S）＝｛1，2，3，4｝，明顯｜T（S）｜＜｜S｜，因此有向路徑中存在擴(kuò)張，結(jié)構(gòu)不可控；若對(duì)節(jié)點(diǎn)1施加控制，此時(shí)T（S）＝｛1，2，3，4，I｝，｜T（S）｜＝｜S｜，路徑中沒(méi)有擴(kuò)張和不可達(dá)節(jié)點(diǎn)，因此該有向路徑結(jié)構(gòu)可控。其次，有向圈不存在擴(kuò)張。如圖1b所示，每個(gè)節(jié)點(diǎn)有且僅有一個(gè)節(jié)點(diǎn)指向它，顯然這樣的結(jié)構(gòu)中不存在擴(kuò)張，若能保證節(jié)點(diǎn)可達(dá)，就能確保其結(jié)構(gòu)可控。綜上所述，若能保證每個(gè)不匹配節(jié)點(diǎn)（即有向路徑的起點(diǎn)）都有一個(gè)獨(dú)有的控制器來(lái)控制它，就可以保證網(wǎng)絡(luò)中不存在擴(kuò)張；對(duì)于有向圈，只需要從任意控制器引出一條邊使得節(jié)點(diǎn)可達(dá)，就能保證網(wǎng)絡(luò)中沒(méi)有不可達(dá)節(jié)點(diǎn)。因此網(wǎng)絡(luò)結(jié)構(gòu)可控所需最小控制器數(shù)目即為網(wǎng)絡(luò)某個(gè)最大匹配所對(duì)應(yīng)的最小不匹配節(jié)點(diǎn)數(shù)目。

基于上述分析，Liu等［11］給出了最小輸入定理：

定理1 當(dāng)有向網(wǎng)絡(luò)是一個(gè)完美匹配時(shí)（網(wǎng)絡(luò)中所有節(jié)點(diǎn)均為匹配節(jié)點(diǎn)），需要施加的最小控制器數(shù)目為1；當(dāng)網(wǎng)絡(luò)不是一個(gè)完美匹配時(shí)，需要施加的最小控制器數(shù)目為N－｜M＊｜。數(shù)學(xué)式表達(dá)為NI＝max｛N－｜M＊｜，1｝，其中NI為最小輸入控制器數(shù)目，N為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目，M＊為有向網(wǎng)絡(luò)的某個(gè)最大匹配。

在Liu等人工作的啟發(fā)下，一系列與網(wǎng)絡(luò)結(jié)構(gòu)可控性相關(guān)的工作陸續(xù)展開(kāi)：Wang等［14］通過(guò)適當(dāng)改變網(wǎng)絡(luò)結(jié)構(gòu)來(lái)達(dá)到最優(yōu)控制的目的；Liu等［15］進(jìn)一步地提出控制中心性來(lái)衡量單個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的控制能力大小；Nepusz等［16］在結(jié)構(gòu)可控的基礎(chǔ)上提出了網(wǎng)絡(luò)的邊控制動(dòng)力學(xué)；Yan等［17］從所耗費(fèi)的能量角度提出了一種衡量網(wǎng)絡(luò)完全可控難易程度的指標(biāo)，并給出了相應(yīng)的范圍——能量耗費(fèi)大小的上下界；Sun等［18］指出在實(shí)際應(yīng)用中增加控制器數(shù)目是一種確保網(wǎng)絡(luò)結(jié)構(gòu)完全可控的有效方法；Yuan等［19］在無(wú)向網(wǎng)絡(luò)的可控性研究的基礎(chǔ)上，從PHB判據(jù)出發(fā)，以乘數(shù)為基準(zhǔn)提出了研究網(wǎng)絡(luò)結(jié)構(gòu)可控性的一般化模型；Ruths等［20］針對(duì)網(wǎng)絡(luò)結(jié)構(gòu)可控的模式問(wèn)題，提出了將網(wǎng)絡(luò)控制器根據(jù)其作用分為3類(lèi)并進(jìn)一步將實(shí)際網(wǎng)絡(luò)劃分為與之相對(duì)應(yīng)的3種類(lèi)型等等。

1.3 強(qiáng)結(jié)構(gòu)可控性

值得一提的是，早在結(jié)構(gòu)可控性研究初期，一些學(xué)者對(duì)結(jié)構(gòu)矩陣中的自由參數(shù)假設(shè)提出了異議。他們從工程及實(shí)際應(yīng)用出發(fā)，認(rèn)為一個(gè)系統(tǒng)的很多參數(shù)是相互關(guān)聯(lián)的，因此很多理論上結(jié)構(gòu)可控的系統(tǒng)在實(shí)際中是不可控的?；谶@樣的出發(fā)點(diǎn)，學(xué)者們提出了強(qiáng)結(jié)構(gòu)可控的概念［23－26］：

定義8 對(duì)于一個(gè)由結(jié)構(gòu)矩陣組成的系統(tǒng)（A＊，B＊），無(wú)論其中的非零參數(shù)如何取值，系統(tǒng)（A＊，B＊）都是結(jié)構(gòu)可控的，則系統(tǒng)（A＊，B＊）是強(qiáng)結(jié)構(gòu)可控的。

在單輸入情形下，強(qiáng)結(jié)構(gòu)可控的圖論判定條件最早由 Mayeda等［23］給出，后來(lái)經(jīng)過(guò)Reinschke、Jarczyk及Chapman等的更正、補(bǔ)充和發(fā)展，逐漸形成了兩大類(lèi)方法來(lái)判定網(wǎng)絡(luò)是否強(qiáng)結(jié)構(gòu)可控［24－26］：

2）將一個(gè)網(wǎng)絡(luò)映射成一個(gè)二分圖，如果某個(gè)匹配是節(jié)點(diǎn)集I＋和I－之間唯一存在的匹配，那么把這樣的匹配叫做約束匹配；如果匹配中不包含自環(huán)｛vi＋，vi－｝，那么這樣的匹配叫做無(wú)自環(huán)匹配。對(duì)于網(wǎng)絡(luò)A來(lái)說(shuō)，通過(guò)將其非零元素用自由參數(shù)（一般用叉號(hào)）表示就可以得到結(jié)構(gòu)矩陣A＊。若將結(jié)構(gòu)矩陣A＊的對(duì)角元素都用自由參數(shù)（一般用叉號(hào)）替代，就可以得到修正后的結(jié)構(gòu)矩陣假設(shè)B是一個(gè)n×m的輸入矩陣，當(dāng)且僅當(dāng)網(wǎng)絡(luò)（A B）存在一個(gè)基數(shù)為（n－m）的約束匹配同時(shí)網(wǎng)絡(luò)（B＊）存在一個(gè)基數(shù)為（n－m）的無(wú)自環(huán)匹配時(shí)，網(wǎng)絡(luò)（A B）強(qiáng)結(jié)構(gòu)可控。

由此可見(jiàn)，強(qiáng)結(jié)構(gòu)可控是結(jié)構(gòu)可控的一種特殊情形，它所要求的條件比結(jié)構(gòu)可控更為苛刻和嚴(yán)格。在文章［26］中，作者還用約束匹配的方法深入探討了強(qiáng)結(jié)構(gòu)可控的最小輸入問(wèn)題，同時(shí)作者給出了兩種特例：一是無(wú)向的帶自阻尼的路徑狀網(wǎng)絡(luò)僅需要一個(gè)控制器即可保證強(qiáng)結(jié)構(gòu)可控；二是無(wú)向的帶自阻尼的完全圖需要個(gè)控制器才能保證網(wǎng)絡(luò)強(qiáng)結(jié)構(gòu)可控。

2 時(shí)效網(wǎng)絡(luò)結(jié)構(gòu)可控性

2.1 時(shí)效網(wǎng)絡(luò)及其時(shí)序特征

定義9 節(jié)點(diǎn)（個(gè)體）的交互影響不是持續(xù)存在，時(shí)間是網(wǎng)絡(luò)的一個(gè)基本組成元素并且使得節(jié)點(diǎn)（個(gè)體）的交互作用具有時(shí)間上的先后次序性和不可逆性，具有這樣一些特性的網(wǎng)絡(luò)統(tǒng)稱(chēng)為時(shí)效網(wǎng)絡(luò)。

時(shí)效網(wǎng)絡(luò)中節(jié)點(diǎn)（個(gè)體）數(shù)目和交互影響均隨時(shí)間而發(fā)生變化，節(jié)點(diǎn)（個(gè)體）間的交互明顯帶有時(shí)間先后順序特征。由此可見(jiàn)，時(shí)效網(wǎng)絡(luò)更強(qiáng)調(diào)網(wǎng)絡(luò)連邊關(guān)系的時(shí)效性，即網(wǎng)絡(luò)連邊的時(shí)間先后順序、時(shí)延、持續(xù)時(shí)間等屬性［30－34］，此外，時(shí)間維度的不可逆轉(zhuǎn)的方向性也使得時(shí)效網(wǎng)絡(luò)與傳統(tǒng)靜態(tài)網(wǎng)絡(luò)是完全不同的。通過(guò)圖2可以看到，由于網(wǎng)絡(luò)連邊時(shí)效的影響，信息傳播路徑具有了時(shí)效特征，即信息的傳播必須遵循網(wǎng)絡(luò)時(shí)效性這個(gè)客觀因素。圖2中，a、b、c、d分別表示在不同時(shí)間點(diǎn)上的時(shí)效網(wǎng)絡(luò)。紅色（灰色）的時(shí)間點(diǎn)表示過(guò)去的時(shí)間點(diǎn)，黑色（暗色）的時(shí)間點(diǎn)表示即將到來(lái)的時(shí)間點(diǎn)。由于網(wǎng)絡(luò)時(shí)效性的影響，信息最終只能從節(jié)點(diǎn)A傳播到節(jié)點(diǎn)B，C和F。

圖2 時(shí)效網(wǎng)絡(luò)上的信息傳播Fig.2 The illustration of information propagation on a temporal network

復(fù)旦大學(xué)自適應(yīng)網(wǎng)絡(luò)與控制研究室利用高校的WIFI上網(wǎng)數(shù)據(jù)建立時(shí)效網(wǎng)絡(luò)，并研究了網(wǎng)絡(luò)的可達(dá)性、路徑長(zhǎng)度（時(shí)間長(zhǎng)度和物理長(zhǎng)度）和持續(xù)時(shí)間之間的關(guān)系、時(shí)效出入度之間的關(guān)系等，作者試圖通過(guò)時(shí)效特征挖掘出網(wǎng)絡(luò)中的超級(jí)傳播者［33］。更進(jìn)一步地，Zhang等［34］構(gòu)建轉(zhuǎn)移網(wǎng)絡(luò)，該網(wǎng)絡(luò)上的每個(gè)節(jié)點(diǎn)代表一個(gè)事件，而不是通常意義上的個(gè)體，研究了同時(shí)刻發(fā)生的事件的持續(xù)時(shí)間分布狀況及其時(shí)效特征模體所刻畫(huà)的交互行為模式。在這樣的一種轉(zhuǎn)移網(wǎng)絡(luò)上，可以清楚地看到事件是如何按時(shí)序發(fā)生和展開(kāi)的。更多相關(guān)內(nèi)容可以參考Holme等［30，37］對(duì)時(shí)效網(wǎng)絡(luò)研究現(xiàn)狀所做出的綜述。因此當(dāng)研究對(duì)象為時(shí)效網(wǎng)絡(luò)時(shí)，必須格外謹(jǐn)慎地考慮到網(wǎng)絡(luò)時(shí)間流的不可逆性（即時(shí)間的有序性），需要從時(shí)效網(wǎng)絡(luò)與靜態(tài)網(wǎng)絡(luò)的本質(zhì)區(qū)別出發(fā)，重新思考網(wǎng)絡(luò)的結(jié)構(gòu)可控性以及其他一系列相關(guān)的網(wǎng)絡(luò)動(dòng)力學(xué)行為特征。

2.2 結(jié)構(gòu)可控性——從時(shí)效網(wǎng)絡(luò)到特征子圖

研究時(shí)效網(wǎng)絡(luò)結(jié)構(gòu)可控性不能從原有的思路出發(fā)，必須有新的方向和方法?；诖耍疚南忍岢隽俗畲髢?yōu)先匹配方法（PMM）［27］。對(duì)任一時(shí)效網(wǎng)絡(luò)，給出了兩個(gè)定義：

定義10 網(wǎng)絡(luò)中所有接觸序列活躍時(shí)間點(diǎn)的集合稱(chēng)為時(shí)效網(wǎng)絡(luò)的特征時(shí)間，它衡量時(shí)效網(wǎng)絡(luò)的時(shí)間尺度特征，記為T(mén)C＝｛t1，t2，…，tk｝，其中ti＜ti＋1，i＝1，2，…，k－1。

定義11 相鄰兩個(gè)特征時(shí)間之間的間隔稱(chēng)為為特征片刻，它衡量某個(gè)特定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在時(shí)效網(wǎng)絡(luò)中持續(xù)時(shí)間的長(zhǎng)短，記為IC＝｛I1，I2，…，Ik－1｝，其中Ii＝ti＋1－ti，i＝1，2，…，k－1。

基于上述定義，將一個(gè)時(shí)效網(wǎng)絡(luò)分割成一系列的特征子圖，然后從中提取出最大特征子圖，最后利用這些最大特征子圖來(lái)研究時(shí)效網(wǎng)絡(luò)的結(jié)構(gòu)可控性問(wèn)題，具體描述為3個(gè)步驟：1）根據(jù)時(shí)效網(wǎng)絡(luò)的特征時(shí)間TC將其劃分為一個(gè)個(gè)特征片刻IC（特征片刻中網(wǎng)絡(luò)的拓?fù)涫庆o態(tài)的），在每個(gè)特征片刻中提取出網(wǎng)絡(luò)的特征子圖，然后從這些特征子圖集合中提取出所需要的最大特征子圖。2）將所有的節(jié)點(diǎn)按照一定的優(yōu)先級(jí)進(jìn)行排序得到優(yōu)先序列VP＝｛v1，v2，…，vN｝，這里的N為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目。在文中作者給出3種具有代表性及可比性的優(yōu)先級(jí)排序法：節(jié)點(diǎn)出現(xiàn)頻率排序，這是根據(jù)局部信息來(lái)進(jìn)行的排序；節(jié)點(diǎn)影響力排序，這是根據(jù)全局信息來(lái)進(jìn)行的排序；完全隨機(jī)排序。3）根據(jù)最大匹配的方法從優(yōu)先序列VP由左向右逐個(gè)選取節(jié)點(diǎn)，以保證最大特征子圖的結(jié)構(gòu)可控性。

在上述操作的基礎(chǔ)上，本文給出了一個(gè)重要的定義以及相應(yīng)的定理。

定義12 通過(guò)刪除一些邊，把一個(gè)無(wú)向網(wǎng)絡(luò)轉(zhuǎn)換成一系列有向圈和孤立節(jié)點(diǎn)的操作稱(chēng)為圖的退化，包含最少孤立節(jié)點(diǎn)的退化稱(chēng)之為完美退化。

定理2 為了使一個(gè)無(wú)向的特征子圖完全結(jié)構(gòu)可控，外部所需施加的最少控制器數(shù)目ND＝max（｜Visolated｜，1），其中｜Visolated｜為任意一個(gè)完美退化中所包含的孤立節(jié)點(diǎn)的數(shù)目。

通過(guò)這樣一種轉(zhuǎn)換，將原來(lái)需要在時(shí)效網(wǎng)絡(luò)上直接研究的問(wèn)題轉(zhuǎn)換到一系列靜態(tài)子圖上來(lái)研究，使得時(shí)效網(wǎng)絡(luò)結(jié)構(gòu)可控性的研究簡(jiǎn)單直觀，且不需要在方法上做出較大的變動(dòng)，仿真結(jié)果也說(shuō)明PMM方法很好地保留下原時(shí)效網(wǎng)絡(luò)的時(shí)效特征。

2.3 結(jié)構(gòu)可控性——從時(shí)效網(wǎng)絡(luò)到線性時(shí)變系統(tǒng)

本文根據(jù)線性時(shí)變系統(tǒng)給出了研究時(shí)效網(wǎng)絡(luò)結(jié)構(gòu)可控性的標(biāo)準(zhǔn)化模型［28－29］。類(lèi)似于將靜態(tài)網(wǎng)絡(luò)映射到一個(gè)線性時(shí)不變（LTI）系統(tǒng)的思路，將時(shí)效網(wǎng)絡(luò)對(duì)映射到一個(gè)線性時(shí)變（LTV）系統(tǒng)x（t）＝A′（t）x（t）＋B（t）u（t）上去。從單控制器出發(fā)，輸入矩陣B（t）此刻退化成一個(gè)輸入向量b（o），給出了單個(gè)節(jié)點(diǎn)控制能力大小的衡量指標(biāo)——節(jié)點(diǎn)的控制中心性的定義。

定義13 定義SM（o）＝rank（Wc）＝rank（［GT…G2H1…GTHT－1HT］）為時(shí)效網(wǎng)絡(luò)節(jié)點(diǎn)的控制中心性，其中Gk＋1＝I＋Tk＋1A′k＋1，Hk＋1＝Tk＋1b（o），Gk＋1中的I為單位矩陣，Tk＋1為對(duì)線性系統(tǒng)的采樣間隔，A′k＋1為k＋1時(shí)刻時(shí)效網(wǎng)絡(luò)的鄰接矩陣，Hk＋1中的b（o）為單輸入控制下的輸入向量，o為直接施加控制器的網(wǎng)絡(luò)節(jié)點(diǎn)。

由定義13可知，當(dāng)SM（o）＜N時(shí)，施加在節(jié)點(diǎn)o處的單個(gè)控制器可以完全控制整個(gè)時(shí)效網(wǎng)絡(luò)；當(dāng)SM（o）＜N時(shí)，SM（o）給出了施加在節(jié)點(diǎn)o處的單個(gè)控制器在整個(gè)時(shí)效網(wǎng)絡(luò)中的最大可控子空間。為了從圖論的角度來(lái)理解矩陣Wc所表達(dá)的含義，將時(shí)效網(wǎng)絡(luò)中所有節(jié)點(diǎn)（包括控制器節(jié)點(diǎn)）復(fù)制T＋1次得到TOG模型，即一個(gè)規(guī)模更大但無(wú)回路的靜態(tài)網(wǎng)絡(luò)。如圖3所示，所有的時(shí)間流向都用有向路徑表示，這樣的做法是以空間的代價(jià)換取時(shí)序特征給問(wèn)題分析所帶來(lái)的不便。圖3中的紅色虛線，黑色（暗色）實(shí)線以及藍(lán)色（灰色）實(shí)線分別代表時(shí)間流方向，與單個(gè)控制器之間的連邊以及網(wǎng)絡(luò)中節(jié)點(diǎn)之間的接觸連邊。

在此TOG模型的基礎(chǔ)上，進(jìn)一步給出了時(shí)效網(wǎng)絡(luò)中輸入可達(dá)以及時(shí)效樹(shù)的定義。

定義14 對(duì)于時(shí)效網(wǎng)絡(luò)中的輸入控制器，如果它與網(wǎng)絡(luò)中任一節(jié)點(diǎn)之間都至少存在一條遵循時(shí)間先后次序路徑（簡(jiǎn)稱(chēng)時(shí)效路徑），那么就稱(chēng)該時(shí)效網(wǎng)絡(luò)是輸入可達(dá)的。

定義15 時(shí)效網(wǎng)絡(luò)的一個(gè)時(shí)效樹(shù)，記為T(mén)Tt，即為T(mén)OG模型中的廣度優(yōu)先搜索生成樹(shù)，記為STt，兩者之間為一一對(duì)應(yīng)關(guān)系。

根據(jù)廣度優(yōu)先搜索算法，可以在TOG模型中找出廣度優(yōu)先搜索生成樹(shù)，同時(shí)在時(shí)效網(wǎng)絡(luò)中找出與之對(duì)應(yīng)的時(shí)效樹(shù)。上述TOG模型的可控矩陣可表示為為t時(shí)刻的通信矩陣，｛Qt｝o，?為矩陣Qt的第o行，通信矩陣Qt中At＊＝而由時(shí)效樹(shù)可達(dá)向量所組成的矩陣WR＝［RTTRTT… RTT］，其中12TRTTt為t時(shí)刻時(shí)效樹(shù)的可達(dá)向量。

引理1 對(duì)于單一控制其輸入情形下的任一時(shí)效網(wǎng)絡(luò)，可得rank（Wc）＝rank（W＊）＝rank（WR），其中Wc為原時(shí)效網(wǎng)絡(luò)的可控矩陣，W＊為T(mén)OG模型的可控矩陣，WR為時(shí)效樹(shù)形式的可控矩陣。

圖3 將時(shí)效網(wǎng)絡(luò)轉(zhuǎn)換為靜態(tài)網(wǎng)絡(luò)方法示例Fig.3 The illustration of transformation of a temporal network to a static one

上述引理意味著只需要對(duì)簡(jiǎn)化后的時(shí)效樹(shù)進(jìn)行判定研究而不必在原有的時(shí)效網(wǎng)絡(luò)上直接進(jìn)行結(jié)構(gòu)可控性的判定，這在數(shù)學(xué)上很大程度簡(jiǎn)化了判斷矩陣Wc秩的計(jì)算量和計(jì)算復(fù)雜度。根據(jù)時(shí)效樹(shù)鄰接矩陣是否為同結(jié)構(gòu)，將其分為兩大類(lèi)：第一類(lèi)是鄰接矩陣同結(jié)構(gòu)的，稱(chēng)為同質(zhì)結(jié)構(gòu)時(shí)效樹(shù)，用WS表示，第二類(lèi)是鄰接矩陣不是同結(jié)構(gòu)的，稱(chēng)為異質(zhì)結(jié)構(gòu)時(shí)效樹(shù)，用WD表示。進(jìn)一步，對(duì)于同質(zhì)結(jié)構(gòu)時(shí)效樹(shù)將其分為互相獨(dú)立的時(shí)效樹(shù)（對(duì)應(yīng)的結(jié)構(gòu)矩陣相互獨(dú)立，用表示）和互相依存的時(shí)效樹(shù)（對(duì)應(yīng)的結(jié)構(gòu)矩陣相互關(guān)聯(lián)，用表示），對(duì)于異質(zhì)結(jié)構(gòu)時(shí)效樹(shù)將其分為含有相同節(jié)點(diǎn)的時(shí)效樹(shù)（節(jié)點(diǎn)相同但連接拓?fù)洳煌?，用表示）和含有不同?jié)點(diǎn)的時(shí)效樹(shù)（節(jié)點(diǎn)不同連接拓?fù)浔囟ú煌?，用表示）?/p>

對(duì)上述4種時(shí)效樹(shù)，分別給出4個(gè)引理、1個(gè)推論以及3個(gè)定理。

定理5 結(jié)合推論1和定理4，時(shí)效網(wǎng)絡(luò)在單節(jié)點(diǎn)控制器輸入情形下最大可控子空間SM（o）的上下界為：max

通過(guò)對(duì)上述兩大類(lèi)4種時(shí)效樹(shù)中的每一種分別進(jìn)行理論推導(dǎo)分析并給出各自所代表的最大可控子空間，結(jié)合時(shí)效樹(shù)和TOG模型以及廣度優(yōu)先搜索生成樹(shù)和時(shí)效樹(shù)之間的等價(jià)性，最終給出了單節(jié)點(diǎn)控制器下的時(shí)效網(wǎng)絡(luò)結(jié)構(gòu)可控性——控制中心性，即單個(gè)節(jié)點(diǎn)的最大可控子空間，如定理5所示。利用ER模型構(gòu)建了4個(gè)人工隨機(jī)時(shí)效網(wǎng)絡(luò)，每個(gè)網(wǎng)絡(luò)均以0.002的概率在每對(duì)節(jié)點(diǎn)之間于每一特征時(shí)間生成一個(gè)時(shí)間接觸，網(wǎng)絡(luò)的特征時(shí)間為t＝1，2，…，100。從圖4可以看到，對(duì)于這些不同網(wǎng)絡(luò)規(guī)模的隨機(jī)時(shí)效網(wǎng)絡(luò)，控制中心性的上下界理論值之間的差值（絕對(duì)值）都相當(dāng)小，這很好地說(shuō)明我們的理論結(jié)論是可靠有效的。圖4中控制中心性的真實(shí)值（用“Calculated”表示）是通過(guò)直接計(jì)算可控矩陣得到的，理論上下界（分別用“Upper Bound”和“Lower Bound”表示）是根據(jù)理論分析結(jié)果得到的。

圖4 ER隨機(jī)網(wǎng)絡(luò)的控制中心性Fig.4 Controlling centrality of ER random networks

此外，本文還采用3組實(shí)際數(shù)據(jù)（HT09來(lái)自2009年超文本會(huì)議采集到的與會(huì)人員之間面對(duì)面的交流信息，SG－Infectious來(lái)自于在愛(ài)爾蘭都柏林的科學(xué)走廊舉行的名叫“感染：保持距離”藝術(shù)科學(xué)展覽會(huì)，這組數(shù)據(jù)記錄下了參與展覽的人之間日常的無(wú)序和動(dòng)態(tài)的接觸，F(xiàn)udanWIFI是在2009—2010年秋季學(xué)期（3個(gè)多月）復(fù)旦校園中采集到的師生無(wú)線上網(wǎng)的信息）生成了8個(gè)時(shí)效網(wǎng)絡(luò)，網(wǎng)絡(luò)規(guī)模分別為：HT09：113節(jié)點(diǎn)、9 856接觸，73節(jié)點(diǎn)、3 679接觸，SG－Infectious：1 321節(jié)點(diǎn)、20 343接觸，868節(jié)點(diǎn)、13 401接觸，2 189節(jié)點(diǎn)、33 744接觸，F(xiàn)udan WIFI：1 120節(jié)點(diǎn)、12 822接觸，2 250節(jié)點(diǎn)、25 772接觸，1 838節(jié)點(diǎn)、27 810接觸?？刂浦行男越馕鼋獾纳舷陆缬晌闹薪馕鼋饨o出，上下界之間的差值由上下界之間的差（絕對(duì)值）給出。節(jié)點(diǎn)的集聚度代表的是在相應(yīng)的時(shí)效網(wǎng)絡(luò)中與該節(jié)點(diǎn)有過(guò)直接接觸的節(jié)點(diǎn)的數(shù)目。與時(shí)效網(wǎng)絡(luò)的規(guī)模（從73到2 250個(gè)節(jié)點(diǎn)）相比較，上下界之間的差值相對(duì)很小。圖5a表示HT09數(shù)據(jù)生成的兩個(gè)網(wǎng)絡(luò)（分別用all range和removed表示）的仿真結(jié)果，圖5b表示SGInfectious數(shù)據(jù)生成的3個(gè)網(wǎng)絡(luò)（分別用Week 1、Week 2和Week 1＆2表示）的仿真結(jié)果，圖5c表示Fudan WIFI數(shù)據(jù)生成的3個(gè)網(wǎng)絡(luò)（分別用Day 1、Day 2和713point表示）的仿真結(jié)果。盡管研究的時(shí)效網(wǎng)絡(luò)的規(guī)模是大小不等的（小到73節(jié)點(diǎn)、3 679接觸，大到2 250節(jié)點(diǎn)、27 810接觸），上下界之間的差值（絕對(duì)值）仍然保持在相當(dāng)小的范圍，如圖5中所示。這進(jìn)一步從實(shí)際數(shù)據(jù)方面證實(shí)了我們理論分析結(jié)論的可行性和可靠性。當(dāng)我們從時(shí)效網(wǎng)絡(luò)中移除某些重要節(jié)點(diǎn)（圖5a中移除了時(shí)效網(wǎng)絡(luò)中心性最大的40個(gè)節(jié)點(diǎn)），或者考慮同一數(shù)據(jù)中不同時(shí)間段的以及不同數(shù)據(jù)的時(shí)效網(wǎng)絡(luò)（圖5b和c中，考慮了同一數(shù)據(jù)中不同時(shí)間段所對(duì)應(yīng)的時(shí)效網(wǎng)絡(luò)以及不同數(shù)據(jù)所形成的不同類(lèi)型的時(shí)效網(wǎng)絡(luò)）時(shí)，發(fā)現(xiàn)節(jié)點(diǎn)集聚度和它的控制中心性之間的正相關(guān)關(guān)系并沒(méi)有隨著數(shù)據(jù)集的不同、時(shí)間段選取的不同或者網(wǎng)絡(luò)結(jié)構(gòu)的變化而發(fā)生統(tǒng)計(jì)上的變化。

圖5 節(jié)點(diǎn)控制中心性上下界之間的差值（絕對(duì)值）Fig.5 The gap（absolute value）between upper and lower bounds of controlling centrality

3 結(jié)語(yǔ)

計(jì)算機(jī)通信和電子科學(xué)技術(shù)的發(fā)展使得我們能夠記錄下許許多多社交信息，例如在線實(shí)時(shí)互動(dòng)數(shù)據(jù)、通過(guò)電子郵箱和手機(jī)短信的通訊數(shù)據(jù)，這些數(shù)據(jù)信息擴(kuò)大了我們的對(duì)象研究范圍，也突破了原有的對(duì)象研究方法。隨著社會(huì)科學(xué)技術(shù)的進(jìn)一步發(fā)展，人們將越來(lái)越關(guān)注由上述數(shù)據(jù)生成的時(shí)效網(wǎng)絡(luò)——一類(lèi)特征明顯且更為貼近實(shí)際情形的網(wǎng)絡(luò)模型——的研究，其中有關(guān)網(wǎng)絡(luò)的結(jié)構(gòu)可控性的研究更是人們迫切希望能夠深入理解并期望最終能夠加以利用的一個(gè)重要方面。盡管有關(guān)網(wǎng)絡(luò)結(jié)構(gòu)可控性的工作已經(jīng)在靜態(tài)體系下迅猛發(fā)展并且日趨成熟，但對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)，尤其是時(shí)效網(wǎng)絡(luò)上的結(jié)構(gòu)可控性研究還處于起步階段，現(xiàn)有的部分工作也只是初步提出了研究規(guī)范框架和模型，大量的相關(guān)性工作還有待學(xué)者們進(jìn)一步的探討和研究。就目前來(lái)看，至少仍存在兩大方面的工作有待展開(kāi)：多輸入控制下時(shí)效網(wǎng)絡(luò)結(jié)構(gòu)可控性問(wèn)題?，F(xiàn)實(shí)中人們往往更關(guān)注于如何設(shè)計(jì)出一個(gè)最優(yōu)的控制方案或者策略，以使得整個(gè)時(shí)效網(wǎng)絡(luò)完全結(jié)構(gòu)可控，這也是我們理解和研究時(shí)效網(wǎng)絡(luò)結(jié)構(gòu)可控理論上的目標(biāo)；網(wǎng)絡(luò)可控性的對(duì)偶面——可觀性。當(dāng)網(wǎng)絡(luò)的規(guī)模大到人們無(wú)法完全了解和掌握時(shí)，是否可以通過(guò)網(wǎng)絡(luò)的可觀性來(lái)反推出網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。信息論中也面臨著一個(gè)相似問(wèn)題：當(dāng)網(wǎng)絡(luò)中存在一個(gè)或多個(gè)源頭（信息源、污染源或干擾源等）時(shí)，能否通過(guò)有限的信息量來(lái)反推出信源的位置。這部分的工作具有十分重大的現(xiàn)實(shí)指導(dǎo)意義［35－36］。

［1］ Kalman R E.Mathematical description of linear dynamical systems［J］.Journal of the Society for Industrial ＆ Applied Mathematics，Series A：Control，1963，1（2）：152－192.

［2］Siljak D.Decentralized Control of Complex Systems［M］.New York：Academic Press，1991.

［3］ 陳關(guān)榮.漫談系統(tǒng)與網(wǎng)絡(luò)［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2010，7（2）：1－4.Chen Guanrong.A talk about systems and networks［J］.Complex systems and complexity science，2010，7（2）：1－4.

［4］ Erd?s P，Rényi A.On random graphs I［J］.Publ Math Debrecen，1959，6：290－297.

［5］ Erd?s P，Rényi A.On the evolution of random graphs［J］.Selected Papers of Alfréd Rényi，1976，2：482－525.

［6］ Lin C T.Structural controllability［J］.Automatic Control，IEEE Transactions on，1974，19（3）：201－208.

［7］ Shields R W，Pearson J B.Structural controllability of multiinput linear systems［J］.IEEE Trans on AC，1976，21（2）：203－212.

［8］ Mayeda H.On structural controllability theorem［J］.Automatic Control，IEEE Transactions on，1981，26（3）：795－798.

［9］ Watts D J，Strogatz S H.Collective dynamics of‘small－world′networks［J］.Nature，1998，393（6684）：440－442.

［10］Barabási A L，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509－512.

［11］Liu Y Y，Slotine J J，Barabási A L.Controllability of complex networks［J］.Nature，2011，473（7346）：167－173.

［12］陳關(guān)榮.復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境下控制理論遇到的問(wèn)題與挑戰(zhàn)［J］.自動(dòng)化學(xué)報(bào)，2013，39（4）：312－321.Chen Guanrong.Problems and challenges in control theory under complex network environments［J］.Acta Automatica Sinica，2013，39（4）：312－321.

［13］席裕庚.大系統(tǒng)控制理論與復(fù)雜網(wǎng)絡(luò)——探索與思考［J］.自動(dòng)化學(xué)報(bào)，2013，39（11）：1758－1768.Xi Yugeng.Large－scale systems control and complex networks－exploration and thinking［J］.Acta Automatica Sinica，2013，39（11）：1758－1768.

［14］Wang W X，Ni X，Lai Y C，et al.Optimizing controllability of complex networks by minimum structural perturbations［J］.Physical Review E，2012，85（2）：026115.

［15］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.

［16］Nepusz T，Vicsek T.Controlling edge dynamics in complex networks［J］.Nature Physics，2012，8（7）：568－573.

［17］Yan G，Ren J，Lai Y C，et al.Controlling complex networks：How much energy is needed？［J］.Physical Review Letters，2012，108（21）：218703.

［18］Sun J，Motter A E.Controllability transition and nonlocality in network control［J］.Physical Review Letters，2013，110（20）：208701.

［19］Yuan Z，Zhao C，Di Z，et al.Exact controllability of complex networks［J］.Nature Communications，2013，4：2447.

［20］Ruths J，Ruths D.Control profiles of complex networks［J］.Science，2014，343（6177）：1373－1376.

［21］Lombardi A，H?rnquist M.Controllability analysis of networks［J］.Physical Review E，2007，75（5）：056110.

［22］Hopcroft J E，Karp R M.An n5／2algorithm for maximum matchings in bipartite graphs［J］.SIAM Journal on Computing，1973，2（4）：225－231.

［23］Mayeda H，Yamada T.Strong structural controllability［J］.SIAM Journal on Control and Optimization，1979，17（1）：123－138.

［24］Reinschke K J，Svaricek F，Wend H D.On strong structural controllability of linear systems［C］／／Proceedings of the 31st IEEE Conference on Decision and Control.IEEE，1992：203－208.

［25］Jarczyk J C，Svaricek F，Alt B.Strong structural controllability of linear systems revisited［C］／／CDC－ECE，2011：1213－1218.

［26］Chapman A，Mesbahi M.On strong structural controllability of networked systems：a constrained matching approach［C］／／American Control Conference（ACC），IEEE，2013：6126－6131.

［27］Pan Y，Li X，Zhan J.On the priority maximum matching of structural controllability of temporal networks［C］／／Control Conference（CCC），2013 32nd Chinese，IEEE，2013：1164－1169.

［28］Pan Y，Li X.Towards a graphic tool of the structural controllability of temporal networks［C］／／International Symposium on Circuits and Systems（ISCAS），Australia IEEE，2014.

［29］Pan Y，Li X.Structural controllability and controlling centrality of temporal networks［J］.PloS one，2014，9（4）：e94998.

［30］Holme P，Saram?ki J.Temporal networks［J］.Physics Reports，2012，519（3）：97－125.

［31］Kim H，Anderson R.Temporal node centrality in complex networks［J］.Physical Review E，2012，85（2）：026107.

［32］Isella L，StehléJ，Barrat A，et al.What′s in a crowd？Analysis of face－to－face behavioral networks［J］.Journal of Theoretical Biology，2011，271（1）：166－180.

［33］Zhang Y，Wang L，Zhang Y Q，et al.Towards a temporal network analysis of interactive WiFi users［J］.EPL（Europhysics Letters），2012，98（6）：68002.

［34］Zhang Y Q，Li X.Temporal dynamics and impact of event interactions in cyber－social populations［J］.Chaos：An Interdisciplinary Journal of Nonlinear Science，2013，23（1）：013131.

［35］Shah D，Zaman T.Rumors in a network：who′s the culprit？［J］.IEEE Transactions on Information Theory，2011，57（8）：5163－5181.

［36］Pinto P C，Thiran P，Vetterli M.Locating the source of diffusion in large－scale networks［J］.Physical Review Letters，2012，109（6）：068702.

［37］Li X，Zhang Y Q，Vasilakos A V.Discovering and Predicting Temporal Patterns of WiFi－Interactive Social Populations［M］／／Wu J，Wang Y S.Opportunistic Social Mobile Networks，CRC Press，2014.