仇建平，陳立潮，潘理虎（太原科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，山西太原030024）

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

仇建平，陳立潮，潘理虎
（太原科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，山西太原030024）

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

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

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

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

1 網(wǎng)絡(luò)模型

1.1 模型示例

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

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

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

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

近年來，許多實證研究證明，社會系統(tǒng)中的許多網(wǎng)絡(luò)，都滿足冪律分布［7－9］，即少數(shù)主導(dǎo)節(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)絡(luò)一共有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)測了重大流量的鏈接結(jié)構(gòu)，相當(dāng)于互聯(lián)網(wǎng)里的rich club，也就是說網(wǎng)絡(luò)中的鏈接是更不平等的。

圖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ì)通過復(fù)雜網(wǎng)絡(luò)中的少數(shù)節(jié)點影響網(wǎng)絡(luò)中的其他節(jié)點，從而實現(xiàn)整個網(wǎng)絡(luò)的同步，所需解決的問題包括：

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

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

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

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

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

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

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

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

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

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

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

此時，式（2）可簡化為

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

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

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

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

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

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

設(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ǎo)得

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

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

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

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

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

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

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

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

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

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

－根據(jù)式（17），節(jié)點必須通過Dj進(jìn)行控制，轉(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(luò)＋1，轉(zhuǎn)到2），否則終止。

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

圖5 運行界面Fig.5 Running interface

2 實驗結(jié)果及分析

包含10個節(jié)點的網(wǎng)絡(luò)拓?fù)淙鐖D5所示，可分解為5個部分，其中s為群體領(lǐng)袖，實心圓點為被驅(qū)動節(jié)點，用于牽制其余部分，空心圓點通過節(jié)點間的耦合連接關(guān)系被間接地控制。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)絡(luò)可同步。如圖6所示，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，驅(qū)動節(jié)點的比例減小，即越是稀疏的網(wǎng)絡(luò)需要越多比例的驅(qū)動節(jié)點才能實現(xiàn)完全能控。

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

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

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

3 結(jié)束語

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

［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］汪小帆，李翔，陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論［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］柳亭，楮衍東，張建剛，等.復(fù)雜動態(tài)網(wǎng)絡(luò)的牽制同步控制［J］.燕山大學(xué)學(xué)報，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年生，講師，主要研究方向為復(fù)雜網(wǎng)絡(luò)、人工智能，承擔(dān)山西省回國留學(xué)人員科研資助項目、山西省自然科學(xué)基金、山西省重大科技專項基金等項目多項。發(fā)表學(xué)術(shù)論文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

仇建平，陳立潮，潘理虎.牽制控制下復(fù)雜網(wǎng)絡(luò)的同步性研究［J］.智能系統(tǒng)學(xué)報，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.

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

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