仇建平，陳立潮，潘理虎（太原科技大學計算機科學與技術學院，山西太原030024）

牽制控制下復雜網(wǎng)絡的同步性研究

仇建平，陳立潮，潘理虎
（太原科技大學計算機科學與技術學院，山西太原030024）

復雜網(wǎng)絡是由數(shù)量巨大的節(jié)點組成，任何人都無法控制所有節(jié)點.只有通過控制少數(shù)節(jié)點，對復雜網(wǎng)絡進行牽制控制，才能達到網(wǎng)絡同步的目的.為此分析了一般網(wǎng)絡和含有生成樹的網(wǎng)絡同步的條件，給出了實現(xiàn)算法及運行界面.仿真結果表明，隨著網(wǎng)絡規(guī)模的擴大，驅(qū)動節(jié)點的比例減小，驅(qū)動節(jié)點常常都是入度低的節(jié)點.

復雜網(wǎng)絡；耦合；牽制；生成樹；同步

社會系統(tǒng)本質(zhì)上是一個復雜系統(tǒng)，特別是隨著現(xiàn)代社會的飛速發(fā)展，對資源的需求也越來越大。單項資源已無法支撐整個社會的全面發(fā)展，且只有各單項資源互相耦合、互相牽制，才能形成強大的支撐合力。一旦某種或幾種資源缺失或失效，社會系統(tǒng)的內(nèi)在結構及功能會遭到極大的破壞。例如，2003年9月28日發(fā)生在意大利的大面積停電事件，最初由于一個供電站的失效致使眾多供電站與整個供電網(wǎng)的脫離，隨后又致使眾多Internet網(wǎng)絡節(jié)點失效，最終致使整個電力調(diào)度系統(tǒng)無法調(diào)控，導致了更大規(guī)模的停電［1?2］。

隨著通信網(wǎng)、電力網(wǎng)、交通網(wǎng)、供水網(wǎng)等復雜動態(tài)網(wǎng)絡的發(fā)展，以及大型高速計算機、巨型數(shù)據(jù)庫以及GPS和基于大數(shù)據(jù)的社會計算的普及，復雜動態(tài)網(wǎng)絡特別是多節(jié)點不規(guī)則連接的有向網(wǎng)絡的牽制控制越來越受到關注。如劉彧［3］研究了復雜動態(tài)網(wǎng)絡節(jié)點從任意初態(tài)控制到任意終態(tài)的完全能控性問題；王文旭［4］提出了一種減少控制節(jié)點的方法；Ne?pusz［5］研究了運用點邊互換的思想對網(wǎng)絡的邊的狀態(tài)進行控制的問題；嚴鋼［6］研究了控制復雜網(wǎng)絡的能量代價問題。

1 網(wǎng)絡模型

1.1 模型示例

一個復雜動態(tài)網(wǎng)絡是具有相互耦合和牽制關系的點或網(wǎng)絡所組成的網(wǎng)絡系統(tǒng)。一般用被線連接起來的點來代表網(wǎng)絡。這些點被稱為節(jié)點，是網(wǎng)絡的參與者；線則被稱為鏈路，代表參與者之間的聯(lián)系。

如圖1所示，電網(wǎng)互相傳輸電力，通信網(wǎng)之間互相傳輸數(shù)據(jù)，交通網(wǎng)之間互相運輸，供水網(wǎng)之間互相供水，同時電網(wǎng)進行電力傳輸需要通信網(wǎng)進行控制，通信網(wǎng)之間互相通訊又依賴于電網(wǎng)的供電等。如果這些網(wǎng)絡中的一個節(jié)點受到攻擊而失效，這些牽制關系能使故障在網(wǎng)絡之間傳播。如圖2所示，一個節(jié)點受到攻擊后，最初有12個運行節(jié)點的網(wǎng)絡最后只剩下4個有效節(jié)點。

圖1 網(wǎng)絡示例Fig.1 A network exam ple

圖2 失效的傳播Fig.2 A propagation of the failure

近年來，許多實證研究證明，社會系統(tǒng)中的許多網(wǎng)絡，都滿足冪律分布［7－9］，即少數(shù)主導節(jié)點具有非常大的連接數(shù)，大多數(shù)節(jié)點的連接數(shù)甚小，以互聯(lián)網(wǎng)為例，如圖3所示。

圖3 全球排名前1 000網(wǎng)站Fig.3 The 1 000 most?visited sites on the web

圖3 勾勒了全球排名前1 000的網(wǎng)站，這個網(wǎng)絡一共有1 000個網(wǎng)站和2萬條有向鏈接，全球的網(wǎng)站分成了兩大陣營。左邊這一塊的核心是google、youtube、facebook等，右邊的核心是百度、優(yōu)酷、人人網(wǎng)等。

如圖4所示，這1 000個網(wǎng)站度分布是個長尾分布，但有一個明顯的截斷。這是因為只考慮了排名靠前的網(wǎng)站，這個排名范圍以外的網(wǎng)站數(shù)據(jù)是極度不全的。從分布來看，是一個類冪律分布，斜率大概是0.8，而Barabasi等［2］估計的互聯(lián)網(wǎng)鏈接冪律分布指數(shù)是2.1。這有2種原因：1）近年來互聯(lián)網(wǎng)變得更不平等；2）只監(jiān)測了重大流量的鏈接結構，相當于互聯(lián)網(wǎng)里的rich club，也就是說網(wǎng)絡中的鏈接是更不平等的。

圖4 全球排名前1 000網(wǎng)站的度分布及冪律分布［10］Fig.4 Degree and pow er?law distribution of the 1 000 most?visited sites on the web［10］

基于這些實證，牽制控制［11］的本質(zhì)通過復雜網(wǎng)絡中的少數(shù)節(jié)點影響網(wǎng)絡中的其他節(jié)點，從而實現(xiàn)整個網(wǎng)絡的同步，所需解決的問題包括：

1）可行性問題：當網(wǎng)絡規(guī)模很大時，控制理論中已有的判據(jù)和算法的計算復雜度往往難以承受，因此需要尋找新的有效算法；

2）經(jīng)濟性問題：選取受控節(jié)點代價的最小化；

3）魯棒性問題：大規(guī)模復雜網(wǎng)絡往往面臨由于隨機故障或者有意攻擊而導致的節(jié)點或鏈路失效。因此，有必要研究控制系統(tǒng)對于隨機故障和有意攻擊的魯棒性。特別地，需要能夠給出判別大規(guī)模網(wǎng)絡控制系統(tǒng)中的關鍵節(jié)點和鏈路的有效算法；

4）演化性問題：很多實際網(wǎng)絡的結構和參數(shù)往往是隨時間演化的，這給系統(tǒng)的有效分析與控制帶來新問題，需要有適合演化網(wǎng)絡的判斷依據(jù)與有效算法。

面對這些問題，很重要的一點就是對網(wǎng)絡進行牽制［12］，使得其網(wǎng)絡的最終狀態(tài)滿足一定要求。但對于大規(guī)模的網(wǎng)絡，不可能控制其每個節(jié)點，僅能對網(wǎng)絡中的少數(shù)關鍵節(jié)點進行控制，通過節(jié)點間的相互耦合，從而達到控制整個網(wǎng)絡的目的。

1.2 復雜網(wǎng)絡的牽制模型［13］

給定時間t和狀態(tài)空間中的一點x（t），復雜網(wǎng)絡動態(tài)變化過程可表示為

式中：輸入u（t），t時刻的狀態(tài)與輸出惟一確定。

考慮一個由N個節(jié)點構成的連續(xù)動力系統(tǒng)，其中第i個狀態(tài)節(jié)點的線性耦合常微分方程［14］如式（2）所示。

式中：N＞1為網(wǎng)絡節(jié)點個數(shù)；xi（t）＝[xi1（t）xi2（t）…xin（t）]T∈Rn表示i節(jié)點的狀態(tài)向量；常數(shù)c＞0表示耦合強度；?！蔙n×n表示外部耦合矩陣，由于f的線形性，Γ為正定；G＝（Gij）N×N表示網(wǎng)絡的拓撲結構，其中若存在節(jié)點j到節(jié)點i（i≠j）的連接，則Gij＞0，若存在節(jié)點i到節(jié)點j（j≠i）的連接，則Gji＞0，否則Gij＝0。G對角元素定義為式（3）。

從而滿足了耗散耦合條件，如式（4）所示。

此時，式（2）可簡化為

設不動點s是系統(tǒng)的解，如式（5）所示。

式中：s（t）可以是一個平衡點、周期軌、擬周期軌、混沌軌道，或者是多agent動態(tài)網(wǎng)絡的虛擬領袖。假設在網(wǎng)絡中僅前面l個節(jié)點（q1，q2，…，ql）為驅(qū)動節(jié)點，網(wǎng)絡能被描述為式（6）、（7）。

式中：l＝?δN」，0＜δ＜1，其中dqi＞0為反饋控制增益，uqi是n維線性反饋控制器。

牽制控制的目標是發(fā)現(xiàn)一些合適的uqi以使網(wǎng)絡能夠達到某個同步狀態(tài)，其中同步可表示為式（8）。

1.2.1 一般復雜網(wǎng)絡的同步化

為了獲得式（10）、（11）的收斂條件，選擇Lya?punov函數(shù)為

設存在K使得（x－y）T（f（x，t）－f（y，t））≤（x－y）TKΓ（x－y）?x，y∈Rn［15］成立，即滿足Lip?schitz條件。根據(jù)式（8）求導得

當D＝0，表明來自外部的入度很高，無需控制便能達到同步，?為kronecker積，

設θ＝λmax（K＋KT）／2，由于θ與K的可互換性得：

若V≤0，誤差逐漸趨向于零，則網(wǎng)絡同步，可得式（16）。

1.2.2 包含生成樹的復雜網(wǎng)絡的同步化

隨著移動技術與社會化媒體的迅速發(fā)展，人們越來越多地參與到網(wǎng)絡上豐富的社會活動中。人們在享受前所未有的便捷的同時，也擁有了網(wǎng)絡這一公共話語平臺，但同時個性會自覺的消失而群體的共性便隨之顯現(xiàn)出來，形成所謂的“網(wǎng)民群體”。網(wǎng)民群體常常表現(xiàn)為非常煩躁、多變和沖動，將選擇、判斷和處理的權利交給群體領袖。群體領袖對事件的傾向性解讀，在暗示和相互傳染的推波助瀾下，立刻會被網(wǎng)民接受。

給合式（6）～（8），將群體領袖作為生成樹的根節(jié)點，可得式（17）。

1.3 算法及系統(tǒng)運行界面

牽制控制算法具體步驟如下：

2）根據(jù)式（17）計算，如果j＝0，則網(wǎng)絡無需控制便可同步，轉(zhuǎn)到6），否則轉(zhuǎn)到3）；

3）如果節(jié)點來自外部的入度為零，比如Cj＝0，

－根據(jù)式（17），節(jié)點必須通過Dj進行控制，轉(zhuǎn)到4），否則轉(zhuǎn)到6）；

4）對于通過j鏈路連接的i節(jié)點，根據(jù)式（15），如果入度kirnj－1＋i≤θ／c，則節(jié)點必須被控制，轉(zhuǎn)到5），否則轉(zhuǎn)到6）

5）篩選根節(jié)點，轉(zhuǎn)到6）

6）如果j＜m，則j＝j＋1，轉(zhuǎn)到2），否則終止。

系統(tǒng)運行界面如圖5所示。

圖5 運行界面Fig.5 Running interface

2 實驗結果及分析

包含10個節(jié)點的網(wǎng)絡拓撲如圖5所示，可分解為5個部分，其中s為群體領袖，實心圓點為被驅(qū)動節(jié)點，用于牽制其余部分，空心圓點通過節(jié)點間的耦合連接關系被間接地控制。2，1），c＝12，N＝10，θ＝31。子網(wǎng)2和3子網(wǎng)的外部入度均為0，必須加以控制。

對于子網(wǎng)2，C2＝A－2＝0，根據(jù)式（17）如果d1＞≈2.583 3，子網(wǎng)2能同步；

對于子網(wǎng)3，C3＝0，＝diag（8，1，3，4）

根據(jù)式（17）如果d2＜18.266 7，控制子網(wǎng)3中的節(jié)點2，子網(wǎng)3能同步；

對于子網(wǎng)5，C5＝diag（2，0，3），＝diag（2，3，

2.665 ，控制子網(wǎng)5中的節(jié)點9，子網(wǎng)5能同步。

綜上所述，實心節(jié)點1，2，9的d1＞2.583 3，d2＞18.266 7，d9＞2.665，圖中的網(wǎng)絡可同步。如圖6所示，隨著網(wǎng)絡規(guī)模的擴大，驅(qū)動節(jié)點的比例減小，即越是稀疏的網(wǎng)絡需要越多比例的驅(qū)動節(jié)點才能實現(xiàn)完全能控。

圖6 驅(qū)動節(jié)點比例與網(wǎng)絡規(guī)模N的關系Fig.6 Relation betweenδand N

如圖7所示，分別以ER網(wǎng)絡和Scale?free網(wǎng)絡為例，驅(qū)動節(jié)點常常都是入度低的節(jié)點，這與式（14）、（15）一致，也與現(xiàn)實情況一致，即入度低的網(wǎng)絡控制起來比較困難，入度高的網(wǎng)絡可通過驅(qū)動少數(shù)節(jié)點來加以控制。

圖7 驅(qū)動節(jié)點比例與其入度的關系Fig.7 Relation betweenδand in?degree

3 結束語

本文針對一般復雜網(wǎng)絡和包含生成樹的復雜網(wǎng)絡的優(yōu)化牽制控制，給出了此2種情況下復雜網(wǎng)絡同步的條件，最后通過系統(tǒng)仿真，發(fā)現(xiàn)越是稀疏的網(wǎng)絡需要越多比例的驅(qū)動節(jié)點才能實現(xiàn)完全能控，且入度低的節(jié)點應首先加以控制。

［1］WATTS D J，STROGATZ S H.Collective dynamics of small?world networks［J］.Nature，1998，393（6684）：440?442.

［2］BARABASIA L，ALBERT R.Emergence of scaling in ran?dom networks［J］.Science，1999，286（5439）：509?512.

［3］LIU Y Y，SLOTINE J J，BARABáSA L.Controllability of complex networks［J］.Nature，2011，473：167?173.

［4］WANGW X，NIX，LAIY C.Optim izing controllability of complex networks by minimum structural perturbations［J］.Phys Rev E，2012，85（026115）：1?5.

［5］NEPUSZ T，VICSEK T.Controlling edge dynamics in com?plex networks［J］.Nature Physics，2012（8）：568?573.

［6］YAN G，REN J，LAI Y C.Controlling complex networks：how much energy is needed？［J］.Phys Rev Lett，2012，108（218703）：1?9.

［7］NEWMAN M E J.Networks：an introduction［M］.Oxford：Oxford University Press，2010：1?20.

［8］CHEN G R，WANG X F，LI X.Introduction to complex networks：models，structures and dynam ics［M］.Beijing：High Education Press，2012：1?10.

［9］ZHOU T，WANG B H.Catastrophes in scale?free networks［J］.Chin Phys Lett，2005，22：1072?1075.

［10］Google.The 1000 most?visited sites on the web［EB／OL］.USA：Google（2011?07?19）［2012?10?25］.http：／／www.google.com／adplanner／static／top1000.

［11］RAJAPAKSE I，GROUDINE M，MESBAHIM.Dynamics and control of state?dependent networks for probing genom?ic organization［J］.PNAS，2011，108：257?262.

［12］汪小帆，李翔，陳關榮.網(wǎng)絡科學導論［M］.北京：高等教育出版社，2012：1?15.WANG Xiaofan，LIXiang，CHEN Guanrong.Introduction of network science［M］.Beijing：Higher Education Press，2012：1?15.

［13］CHEN G R，WANG X F，LI X.Introduction to complex networks：models，structures and dynamics［M］.Beijing：High Education Press，2012：167?256.

［14］YUW，CAO J，LIU J.Global synchronization of linearly hybrid coup led networkswith time?varying delay［J］.SIAM JAppl Dyn Syst，2008（7）：108?133.

［15］柳亭，楮衍東，張建剛，等.復雜動態(tài)網(wǎng)絡的牽制同步控制［J］.燕山大學學報，2010，34（5）：459?470.LIU Ting，CHU Yandong，ZHANG Jiangang，et al.Pin?ning controlled synchronization of a complex dynamical net?work［J］.Journal of Yanshan University，2010，34（5）：459?470.

仇建平，男，1973年生，講師，主要研究方向為復雜網(wǎng)絡、人工智能，承擔山西省回國留學人員科研資助項目、山西省自然科學基金、山西省重大科技專項基金等項目多項。發(fā)表學術論文9篇，其中5篇被EI檢索。

陳立潮，男，1961年生，教授，主要研究方向為人工智能，發(fā)表論文數(shù)十篇。

潘理虎，男，1974年生，副教授，博士，主要研究方向為煤礦安全、人工智能。

Synchronization in comp lex networks via pinning control

QIU Jianping，CHEN Lichao，PAN Lihu
（Institute of Computer Science and Technology，Taiyuan University of Science and Technology，Taiyuan 030024，China）

For the tremendous amount of nodes in complex networks，no one can control all the vertices.Only by controllingminor vertices and spinning the complex network can the synchronization of the network be achieved.The conditions for synchronization of common network and the network with spanning tree are analyzed.The algo?rithm to achieve itand the operation interface are given in this paper.The system simulation results showed that the percentage for the pinning controlled vertices becomes smaller as the network size becomes larger and the vertices with very small in?degrees should be pinned.

complex network；coupling；pinning control；spanning tree；synchronization

TP393.4

A

1673?4785（2014）06?0734?06

仇建平，陳立潮，潘理虎.牽制控制下復雜網(wǎng)絡的同步性研究［J］.智能系統(tǒng)學報，2014，9（6）：734?739.

英文引用格式：QIU Jianping，CHEN Lichao，PAN Lihu.Synchronization in complex networks via pinning control［J］.CAAI Transactions on Intelligent Systems，2014，9（6）：734?739.

10.3969／j.issn.1673?4785.201311014

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1673?4785.201311014.htm l

2013?11?07.

日期：2014?09?30.

山西省回國留學人員科研基金資助項目（2013?097）.

仇建平.E?mail：920868329＠qq.com.