由動(dòng)態(tài)信號(hào)揭示社團(tuán)結(jié)構(gòu)

楊春林，張四平

（1.蘭州商學(xué)院信息工程學(xué)院計(jì)算機(jī)系，蘭州 730020；2.蘭州大學(xué)物理科學(xué)與技術(shù)學(xué)院，蘭州 730000）

由動(dòng)態(tài)信號(hào)揭示社團(tuán)結(jié)構(gòu)

楊春林1，張四平2

（1.蘭州商學(xué)院信息工程學(xué)院計(jì)算機(jī)系，蘭州 730020；2.蘭州大學(xué)物理科學(xué)與技術(shù)學(xué)院，蘭州 730000）

就一個(gè)社團(tuán)網(wǎng)絡(luò)系統(tǒng)，基于不同的鏈接，給出了觀察動(dòng)態(tài)信號(hào)及分析動(dòng)力學(xué)變量快照的方法。結(jié)果表明如果節(jié)點(diǎn)能夠正確排序，當(dāng)網(wǎng)絡(luò)體系處于退同步狀態(tài)時(shí)，通過(guò)幾張動(dòng)力學(xué)變量快照就足以確定社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)。此外，當(dāng)社團(tuán)結(jié)構(gòu)演變?yōu)橐?guī)則晶格時(shí)，動(dòng)力學(xué)變量將表現(xiàn)為某種正弦波形式，這將有助于進(jìn)一步揭示無(wú)序社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)。

社團(tuán)結(jié)構(gòu)；Rossler振子；快照；退同步

社團(tuán)結(jié)構(gòu)，也就是由諸多社團(tuán)組成的網(wǎng)絡(luò)結(jié)構(gòu)。在許多社會(huì)的［1-4］、生物的［5-6］、技術(shù)的［7-9］網(wǎng)絡(luò)中已經(jīng)發(fā)現(xiàn)，單個(gè)社團(tuán)內(nèi)節(jié)點(diǎn)鏈接濃密，而社團(tuán)之間鏈接稀疏。就一個(gè)社團(tuán)網(wǎng)絡(luò)體系，關(guān)鍵不在節(jié)點(diǎn)，而是鏈接。在全局范圍內(nèi)，連接不同社團(tuán)之間的鏈接對(duì)網(wǎng)絡(luò)的效率起著決定性的作用。因此僅從對(duì)動(dòng)態(tài)信號(hào)的觀察來(lái)識(shí)別網(wǎng)絡(luò)結(jié)構(gòu)很重要，也可以通過(guò)保護(hù)或者攻擊這些重要鏈接來(lái)防護(hù)或更有效地銷(xiāo)毀網(wǎng)絡(luò)。當(dāng)網(wǎng)絡(luò)連接是已知的，有許多途徑可以找出社團(tuán)結(jié)構(gòu)［10-12］。然而，在很多情形下，網(wǎng)絡(luò)鏈接并不已知，僅能通過(guò)一些動(dòng)態(tài)信號(hào)來(lái)觀察體系。這樣，從可能的觀察中找出社團(tuán)結(jié)構(gòu)對(duì)于某些任務(wù)是很關(guān)鍵的。此外，在可以使用相關(guān)性矩陣，因?yàn)閱蝹€(gè)社團(tuán)里面的節(jié)點(diǎn)之間比屬于不同社團(tuán)里的節(jié)點(diǎn)之間更有關(guān)聯(lián)性。而且，這種關(guān)聯(lián)性可以給出一種節(jié)點(diǎn)的劃分，這種劃分與該社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)相匹配。這種方法可以在一般情況下使用，此時(shí)體系并非完全同步。然而，在一定條件下，存在一種更快的方法：僅僅通過(guò)觀察動(dòng)態(tài)信號(hào)的幾張快照就可以找出社團(tuán)結(jié)構(gòu)。進(jìn)一步，通過(guò)這種快速方法還可以發(fā)現(xiàn)在每一個(gè)社團(tuán)里面是否有局部規(guī)則結(jié)構(gòu)。

為說(shuō)明這種快速方法，首先引進(jìn)一些預(yù)備數(shù)學(xué)知識(shí)從同步狀態(tài)的穩(wěn)定分析開(kāi)始［13-14］。假設(shè)每一個(gè)節(jié)點(diǎn)遵循非線性動(dòng)力學(xué)并且不同的節(jié)點(diǎn)通過(guò)網(wǎng)絡(luò)連接耦合。具體來(lái)說(shuō)，每個(gè)振子孤立時(shí)的行為可以描述為

其中，x是d維向量，F(xiàn)（x）是速度場(chǎng)。不失一般性，選擇標(biāo)準(zhǔn)振子模型Rossler振子：

其中，x=［x，y，z］T且

如此選定Rossler振子的參數(shù)，它表現(xiàn)為混沌振動(dòng)。網(wǎng)絡(luò)動(dòng)力學(xué)方程可寫(xiě)為

由于體系可以用方程（3）表述，因此，控制無(wú)窮小向量δxi（t）≡xi（t）-s（t）隨時(shí)間的演化變化方程為

其中，DF（s）與DH（s）是相應(yīng)于向量函數(shù)值s（t）的雅克比矩陣。對(duì)角化耦合矩陣G所產(chǎn)生的一組特征值為｛λi｝（i=1，…，N），相應(yīng)的歸一化特征向量用e1，e2，…，eN表示。在一般真實(shí)情況下特征值是非負(fù)的［15］，因此可以排序?yàn)?=λ1＜λ2≤…≤λN。比值λN/λ2越小，網(wǎng)絡(luò)的同步性就越強(qiáng)［16-17］。做變換δy=O-1·δx，其中，O為一矩陣，它的每一列為一組特征向量，因此可得方程（4）的分塊對(duì)角非耦合形式為

令K=ελi（i=2，…，N）是歸一化的耦合參數(shù)，進(jìn)而方程寫(xiě)為

對(duì)于方程（5）的最大李雅普諾夫指數(shù)是主要穩(wěn)定函數(shù)Ψ（K）［18］，如果Ψ（K）是負(fù)數(shù)，一個(gè)小的擾動(dòng)將以指數(shù)形式從同步狀態(tài)衰減，因此系統(tǒng)是穩(wěn)定同步的；如果Ψ（K）是正的，一個(gè)小的擾動(dòng)將被放大且系統(tǒng)不再同步。

在區(qū)域［K1，K2］中，函數(shù)Ψ（K）是負(fù)數(shù)，其中K1，K2完全依賴于節(jié)點(diǎn)動(dòng)力學(xué)控制函數(shù)F（x）和輸出函數(shù)H（x）。因此，對(duì)于K1＜K＜K2，所有的特征向量（本征模）是橫向穩(wěn)定的，并且網(wǎng)絡(luò)是同步的?？山o出同步區(qū)域邊界條件：

當(dāng)違反此條件時(shí)，網(wǎng)絡(luò)將變成退同步。如果條件（7）違背，體系將發(fā)散，因此僅關(guān)注條件（6）。從以前的研究中［19-22］可知，如果僅僅幾個(gè)模式跳出同步區(qū)域［K1，K2］，也就是說(shuō)ελi＜K1且K1＜ελi+1＜K2，i是個(gè)小整數(shù)，那么網(wǎng)絡(luò)將變?yōu)橥送角覄?dòng)力學(xué)變量的變化將有相應(yīng)于從e2到ei的特定形式。對(duì)于社團(tuán)結(jié)構(gòu)，如果它有M個(gè)社團(tuán)，那么λ1=0，λ2到λM互相靠得很近，卻與λM+1很好地分離（見(jiàn)圖1）。相應(yīng)于特征向量e2到eM都有一種社團(tuán)形式：在一個(gè)社團(tuán)里面的元素有一種相干形式（要么是連續(xù)不斷，要么表現(xiàn)為正弦波，這種形式依賴于社團(tuán)的網(wǎng)絡(luò)結(jié)構(gòu)）而且他們十分不同于屬于不同社團(tuán)里面的元素。因此如果i≤M，所有的不穩(wěn)定模式都有一種社團(tuán)結(jié)構(gòu)，動(dòng)力學(xué)變量的非相干性將表現(xiàn)出一種結(jié)構(gòu)的相似性，也就是說(shuō)如果節(jié)點(diǎn)被正確地分類，繪出可視信號(hào)將表現(xiàn)出明顯的社團(tuán)結(jié)構(gòu)，如圖2所示。進(jìn)一步，因?yàn)樘卣髦郸?到λM很好地偏離于λM+1到λN，所以有一個(gè)比較大的參數(shù)范圍可以觀察這種現(xiàn)象，即K1/λM+1＜ε＜K1/λ2。例如，對(duì)于Rossler體系，選擇a=b=0.2，c=9。

圖1 具有M個(gè)子網(wǎng)的社團(tuán)網(wǎng)絡(luò)特征譜圖Fig.1 A schematic show of eigenvalue spectra for clustered networks with Mrandom subnetworks

圖2 一個(gè)隨機(jī)社團(tuán)網(wǎng)絡(luò)的不同節(jié)點(diǎn)動(dòng)態(tài)變量xi的典型輪廓Fig.2 A typical of the dynamical variable xiof different nodes for a random clustered network

所對(duì)應(yīng)的雅克比矩陣為

其主穩(wěn)函數(shù)如圖3所示。此時(shí)K1≈0.2且K2≈4.62。如果社團(tuán)網(wǎng)絡(luò)有圖1所示的相同參數(shù)，那么可用于觀察這種現(xiàn)象的參數(shù)范圍是0.25＜ε＜1，與被λ2∶0＜ε＜1所引起的全局不同步區(qū)域相比這種現(xiàn)象是非常穩(wěn)定的。

作為例子，考慮如下社團(tuán)網(wǎng)絡(luò)模型；將N個(gè)節(jié)點(diǎn)分成M個(gè)社團(tuán)，每個(gè)社團(tuán)有n=N/M個(gè)節(jié)點(diǎn)，在單個(gè)社團(tuán)內(nèi)一對(duì)節(jié)點(diǎn)被連接的概率為ps，而屬于不同社團(tuán)的節(jié)點(diǎn)連接的概率為pl，這樣形成一個(gè)社團(tuán)隨機(jī)網(wǎng)絡(luò)。特別是社團(tuán)之間的鏈接數(shù)遠(yuǎn)遠(yuǎn)小于社團(tuán)內(nèi)部的鏈接數(shù)，結(jié)果發(fā)現(xiàn)與一個(gè)小的pl參數(shù)區(qū)更相關(guān)。

圖2表明一個(gè)典型的結(jié)果就是可以觀察到由于違背條件（6）所引起的退同步Rossler體系的動(dòng)態(tài)變量。作為人為網(wǎng)絡(luò)，社團(tuán)結(jié)構(gòu)已知且節(jié)點(diǎn)能夠被正確排序。在圖2中可以清楚地看到社團(tuán)結(jié)構(gòu)。對(duì)于真實(shí)的例子，一個(gè)簡(jiǎn)單的方法是通過(guò)動(dòng)力學(xué)變量的值去排序，因?yàn)樵谝粋€(gè)社團(tuán)里面的節(jié)點(diǎn)有相近的值。在排序以后，動(dòng)態(tài)變量將有一個(gè)階梯形式，每一階梯相應(yīng)于一個(gè)社團(tuán)。

圖3 對(duì)于Rossler振子網(wǎng)絡(luò)，方程5的主要穩(wěn)定函數(shù)Ψ（K）隨K的變化圖Fig.3 For the rossler oscillator network，an example of the mastor stabilty functionΨ（K）calculated form Eq.5

圖4 對(duì)于每個(gè)規(guī)則晶格社團(tuán)的一個(gè)社團(tuán)網(wǎng)絡(luò)不同節(jié)點(diǎn)動(dòng)態(tài)變量xi的典型輪廓Fig.4 A typical profile of the dynamical variable xiof different nodes for a clustered network

通常，觀察這種現(xiàn)象的參數(shù)范圍較大，而且很快，因?yàn)閮H通過(guò)幾個(gè)快照足以確定社團(tuán)結(jié)構(gòu)，所以這個(gè)方法很實(shí)用。但是，當(dāng)前的問(wèn)題是需要假定每個(gè)社團(tuán)是一個(gè)無(wú)序網(wǎng)絡(luò)，例如隨機(jī)、無(wú)標(biāo)度、小世界網(wǎng)絡(luò)，當(dāng)每一個(gè)社團(tuán)變成一個(gè)規(guī)則晶格時(shí)，每個(gè)社團(tuán)內(nèi)相應(yīng)于λ2到λM將有一個(gè)正弦波形式。因此，當(dāng)體系違背條件（6）變成退同步時(shí)，動(dòng)力學(xué)變量也可以有一個(gè)正弦波形式，如圖4所示。在這種情況下，如果節(jié)點(diǎn)的正確排序是未知的，那么對(duì)于找出階梯的排序方法將是無(wú)效的。因此，基于上述工作和其他學(xué)者所提出的各種算法［23-26］，我們希望通過(guò)適當(dāng)改變或增加一些算法準(zhǔn)則來(lái)推廣這種算法，找出正弦波形式，進(jìn)而揭示網(wǎng)絡(luò)結(jié)構(gòu)。以后的工作將主要集中對(duì)這個(gè)方法的推廣并且提供更多具體的解析基礎(chǔ)，或采取某種改進(jìn)使它適用于更多真實(shí)的動(dòng)力學(xué)系統(tǒng)。

綜上所述，對(duì)于社團(tuán)隨機(jī)網(wǎng)絡(luò)，如果節(jié)點(diǎn)能夠正確排序，當(dāng)網(wǎng)絡(luò)體系違背條件（6）而處于退同步狀態(tài)時(shí)，僅僅通過(guò)幾張動(dòng)力學(xué)變量快照就足以確定社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)。此外，還發(fā)現(xiàn)，當(dāng)社團(tuán)結(jié)構(gòu)演變?yōu)橐?guī)則晶格時(shí)，動(dòng)力學(xué)變量將表現(xiàn)為某種正弦波形式，這將有助于進(jìn)一步揭示無(wú)序社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)。

［1］Zachary W W.An information flow model for conflict and fission in small groups［J］.J Anthropol Res，1977，33（4）：452-473.

［2］Watts D J，Dodds P S，Newman M E J.Identity and search in social networks［J］.Science，2002，296：1302-1304.

［3］Girvan M，Newman M E J.Physical sciences-applied mathematics［J］.Proc Natl Acad Sci U S A，2002，99（12）：7821-7826.

［4］Motter A E，Nishikawa T，Lai Y-C.Large-scale structural organization of social networks［J］.Phys Rev E，2003，68（3）：036105.

［5］Ravasz E，Somera A L，Mongru D A ，et al.Hierarchical organization of modularity in metabolic networks［J］.Science，2002，297：1551-1554.

［6］Spirin V，Mirny L A，Protein complexes and functional modules inmolecular networks［J］.Proc Natl Acad Sci USA ，2003，100（21）：12123-12128.

［7］Milo R ，Shen-Orr S，Itzkovitz S，et al.Network motifs：simple building blocks of complex networks［J］.Science，2002，298：824-826.

［8］Vazquez A，Pastor-Satorras R，Vespignani A.Large-scale topological and dynamical properties of the internet［J］.Phys Rev E，2002，65（6）：066130.

［9］Eriksen K A，Simonsen I，Maslov S，et al.Modularity and extreme edges of the internet［J］.Phys Rev Lett，2003，90（14）：148701.

［10］Girvan M ，Newman M E J.Community structure in social and biological networks［J］.Proc Natl Acad Sci USA，2002，99（12）：7821-7826.

［11］Wildinson D M，Huberman B A.A method for finding communities of related genes［J］.Proc Natl Acad Sci USA，2004，101（suppl 1）：5241-5248.

［12］Palla G，Derenyi I，F(xiàn)arkas I，et al.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature，2005，435：814-818.

［13］陳娟，陸君安.復(fù)雜網(wǎng)絡(luò)中尺度研究揭開(kāi)網(wǎng)絡(luò)同步化過(guò)程［J］.電子科技大學(xué)學(xué)報(bào)，2012，41（1）：9-11.

Chen Juan，Lu Jun′an.Mesoscales reveal synchronization processes in complex networks［J］.Journal of University of E-lectronic Science and Technology of China，2012，41（1）：9-11.

［14］Huang L，Chen Q F，Lai Y Ch，et al.Generic behavior of master-stability functions in coupled nonlinear dynamical systems［J］.Phys Rev E，2009，80（3）：1-6.

［15］Jost Jand Joy M P.Spectral properties and synchronization in coupled map lattices［J］.Phys Rev E，2002，65（1）：016201.

［16］Nishikawa T，Motter A E，Lai Y Ch，et al.Heterogeneity in oscillator networks：are smaller worlds easier to synchronize［J］.Phys Rev Lett，2003，91（1）：014101.

［17］Motter A E，Zhou C S，Kurths J.Enhancing complex-network synchronization［J］.Europhys Lett，2005，69（3）：334-340.

［18］Pecora L M，Carroll T L.Master stability functions for synchronized coupled systems［J］.Phys Rev Lett.1998，80（10）：2109-2112.

［19］Huang L，Park K，Lai Y Ch，et al.Abnormal synchronization in complex clustered networks［J］.Phys Rev Lett，2006，97（16）：164101.

［20］Hunag L，Lai Y Ch，Robert A G.Alternatingsynchronizability of complex clusterednetworks with regular local structure［J］.Phys Rev E，2008，77（1）：016103.

［21］呂翎，鄒家蕊，楊明，等.大規(guī)模富社團(tuán)網(wǎng)絡(luò)的時(shí)空混沌同步［J］.物理學(xué)報(bào)，2010，59（10）：6864-6866.

LüLing，Zou Jiarui，Yang Ming，et al.Synchronization of spatiotemporal chaos in large scale rich club network［J］.Chin Phys Soc，2010，59（10）：6864-6866.

［22］楊浦，鄭志剛.基于動(dòng)力學(xué)的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)識(shí)別速度研究［J］.物理學(xué)報(bào)，2012，61（12）：1-2.

Yang Pu，Zheng Zhigang.Analysis the convergency speed of estimating the network topology based on the dynamical synchronization［J］.Chin Phys Soc，2012，61（12）：1-2.

［23］張聰，沈惠璋.網(wǎng)絡(luò)自然密度社團(tuán)結(jié)構(gòu)模塊度函數(shù)［J］.電子科技大學(xué)學(xué)報(bào)，2012，41（2）：186-187.

Zhang Cong，Shen Huizhang.Modularity function for community structure based on natural density of networks［J］.Journal of University of Electronic Science and Technology of China，2012，41（2）：186-187.

［24］鄧小龍，王柏，吳斌，等.基于信息熵的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分建模和驗(yàn)證［J］.計(jì)算機(jī)研究與發(fā)展，2012，49（4）：726-727.

Deng Xiaolong，Wang Bai，Wu Bin，et al.Modularity modeling and evaluation in community detecting of complex network based on information entropy［J］.Journal of Computer Research and Development，2012，49（4）：726-727.

Referring Clustered Structure from Dynamical Signals

YANG Chun-lin1，ZHANG Si-ping2
（1.School of Information Engineering，Lanzhou University of Finance and Economics，Lanzhou 730020，China；2.School of Physical science and Technology，Lanzhou University，Lanzhou 730000，China）

For a clustered network system，based on the different links，this paper presents the method that observed dynamical signals and analyzed the snapshot of the variation of the dynamical.It is show that a few snapshots are enough to determine thecluster structure when the system becomes desynchronizedafter nodes ordered.Moreover when each cluster becomesa regular lattice，the variation of the dynamicalcan have sine wave form in each cluster.This will help to refer clustered structure of the disordered network.

clustered structure；Rossler oscillator；snapshot；desynchronization

O415.6

A

1672-3813（2013）03-0020-05

2013-03-03

楊春林（1966-），男，甘肅酒泉人，學(xué)士，副教授，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)研究。

（責(zé)任編輯 耿金花）