復雜網絡稀疏性的統計物理研究綜述

朱陳平, 張永梅, 劉小廷, 王榮芳, 王新光

(南京航空航天大學應用物理系,南京 210016)

復雜網絡稀疏性的統計物理研究綜述

朱陳平, 張永梅, 劉小廷, 王榮芳, 王新光

(南京航空航天大學應用物理系,南京 210016)

大多數實際存在的復雜網絡是稀疏的,即網絡平均度遠小于節點數:k—?N.到目前為止,關于這一性質的起源,它對于網絡功能與網絡上動力學過程的影響,可能的應用價值的研究還都遠遠不足.實際上,稀疏性與網絡的其它拓撲性質密切相關.近幾年來,人們對復雜網絡稀疏性的相關效應從理論和實驗兩個方面都做了深入的研究,但是,還缺乏原理性的探討.從統計物理的視角出發,稀疏性應當被看作復雜系統中個體之間相互作用的涌現性質,而不應當是現有模型中先驗的前提.本文擬就復雜網絡稀疏性的統計物理研究作一綜述.

復雜網絡;稀疏性;統計物理

1 大多數實際存在的大型網絡都具有稀疏性[5-8］

大多數實際存在的大型網絡都具有稀疏性[5-8],滿足k—?ln N?N,或者k—～ln N的網絡就是稀疏網絡,其中k—為平均度,它是平均每個節點連邊數目的兩倍.在系統生物學[9]中,也常常定義在一對給定的節點之間在給定方向上的連邊概率p= E/N2,E為總邊數.當p?1時,網絡就是稀疏的.

絕大多數生物網絡都是稀疏的,這一性質已經引起生物界(特別是新近興起的系統生物學界)的廣泛重視.基因調控網絡(GRN)[9-10]是典型的稀疏網絡.已被詳細研究過的一些典型GRN的平均每基因連邊數(平均度的一半)在(2,10)的范圍.其入度大致為泊松型的,出度近似為冪律分布,Kundu[11]將單一蛋白質的結構信息分親水和疏水兩種類型記錄在氨基酸殘基之間相互作用的網絡中,把這兩種氨基酸網絡分開來分析.結果表明,兩種網絡都具有小世界性質,平均度大致介于(2.72,7.58)的范圍,兩個網絡的長程相互作用的度分布都是有指數截斷的冪律形式,疏水網絡具有比親水網絡更大的平均度.

一些技術網絡也具有稀疏性,電力網[12]是其中的典型例子.Krapivski等[13]在給出描寫Internet和WWW的拓撲性質的log網絡模型時指出,Internet 和WWW展示出與log網絡的某種相似性.例如:在WWW網中,邊的總數超過節點總數一個數量級,與Internet(尤其是自治系統的AS圖)相似,每個節點的平均邊數也系統地隨時間緩慢增長.但是,它們也是比較稀疏的.在下一代綜合通訊系統的熱點課題—-移動ad hoc通訊網絡(MANET)的研究中,實驗和理論都表明,MANET可以工作在稀疏連通的狀態[14-16].最近,筆者的研究發現,工作在臨界滲流狀態附近的納米碳管網絡是相當稀疏的[17].這種網絡獨特的電導、熱導與透明性質正在成為熱點研究課題.

一批交叉科學研究者們發現,語言的概念網絡也是稀疏的[18],它具有小世界性質,同時還有指數開頭的冪律度分布.Krapivski等[13]對《Physical Review》系列雜志引文網的實證統計也表明,從1997年到2001年,對于PR的長期出版數據,平均每篇文章參考文獻的數目,出度隨總的文獻規模緩慢增長,與他們模型預測的對數增長相吻合.

2 稀疏性與網絡的其它拓撲性質密切相關[4］

3 復雜網絡稀疏性的統計物理研究新進展

Watts[21]很早就指出:由于搜集信息和建立關系都是耗費精力的操作,連邊需要付出代價,所以相互作用和影響的網絡都傾向于是稀疏的.這是一個出現在真實網絡中的一般的性質,所以僅考慮具有?N的系統的網絡.當人與人之間互相影響的網絡足夠稀疏,級聯作用的傳播會受限于網絡的全局連通率；而當它足夠密集時,級聯作用的傳播則決定于個體節點的穩定性.Bogu?á和Pastor-Satorras[7]認為,必須考慮兩種不同類型網絡的可能性:具有準確定義的平均度的熱力學極限的稀疏網絡,與平均度隨網絡尺寸發散的非稀疏網絡.在稀疏網絡情況下,邊的數目隨著系統尺寸線性增長,聯合分布是一個精確描寫的與尺寸無關的量.在相反的情況下,非稀疏網絡的連邊數目比線性更快地增長,這會引起熱力學極限的破壞而且會有邊凝聚現象的涌現.為了區分稀疏和非稀疏網絡,必須考慮平均度的數值.如果密度r(h)與系統尺寸無關,唯一得到稀疏網絡的可能性由連接概率的一個標度關系來刻畫.這個標度行為會具有很強的應用價值.Reichardt 等[22]則發現,網絡的群落(community)結構,可以解釋為自旋玻璃的能量最小化自旋位形,其中自旋態就是群落的指標.他們在大規模ER隨機圖上的數值實驗還表明,稀疏網絡中群落的數目傾向于隨平均度的降低而增加.Ehrhardt等[23]在研究自主體的相互作用網絡與知識的擴散和積累的耦合演化過程中發現,大數目N的稀疏網絡比小數目的網絡更加穩定,更能夠承受大的漲落.他們用特征量ξ描寫系統的成網作用.只要ξ小,只有稀疏網絡的穩態是可能的,隨著成網效應ξ的增長,全局的形勢沒有多大改善,因為由于技術水平的差別太大,大多數企圖產生新連邊的努力還是歸于失敗.然而,當ξ變得足夠大,這種情形變得不穩定,密集網絡以一種突然的方式形成,網絡的形成是一個隨機事件,而且它會對稍微不同的ξ值發生.在具有大數目N自主體的典型的社會中,稀疏網絡比具有小的N的社會中更加穩定.這是因為,從稀疏相到密集網絡相的翻轉是由大的漲落引發的.這在小的系統中相對容易地發生,當成網作用ξ掉到閾值ξ1以下的時候,密集網絡翻轉回到稀疏網絡.Bornholdt[24-25]等人提出了自組織臨界性與網絡稀疏性的模型,采用活躍點失去連邊,惰性點得到連邊的規則,使得網絡能夠自組織演化到平均度小于3的稀疏網絡.Meisel 等[26]分別采用HSP(體內平衡的突觸可塑性)和STDP(與放電時間相關的突觸可塑性)兩種規則,根據節點之間的狀態關聯,決定加邊或者去邊,同樣得到了自組織臨界性下網絡稀疏性的結果.2008年, Vazquez等[27]總結前人的選舉人模型結果,給出了復雜網絡上耦合演化的選舉人模型；通過建立主方程,結合平均場近似求出解析解；發現了與平均度相關的破碎相變,劃分出凍結相與活躍相兩種網絡狀態.Nowak小組[28]在網絡中的幾種博弈中發現,稀疏的網絡上的演化穩定性并不意味著在比較均勻的網絡上的穩定性.在實驗方面,值得注意的是,一個高度精巧的腦磁圖實驗揭示了大腦功能區之間的稀疏網絡連接與動力學態的關系.Bassett等[29]利用對腦磁圖時間序列的小波分解,來描寫大腦功能網絡中在具體頻率下同步的拓撲結構,他們報告的網絡在靜息和運動兩個狀態都是稀疏地連接的,其平均連接密度為0.095.此外,在所有尺度上和狀態中的網絡同步性是接近于閾值0.01,這給出在耦合振子系統中,從全局的有序到無序行為的轉變區的下界.

我國學者對稀疏網絡的研究也作出了突出貢獻.中科院自動化所的劉勇(Liu Yong)等[30]在權威雜志《Brain》上報道說,人類大腦已經被描述為一個大型的稀疏的由高效的小世界性質刻畫的復雜網絡,這些性質確保大腦以較高的效率產生和整合信息.以前的許多神經成像研究,提供了在精神分裂癥的大腦區域之間功能失調連接的牢固證據.然而,人們并不知道功能失調連接會引起大腦功能網絡拓撲性質的破壞.為此,他們通過靜息狀態下的功能核磁成像,研究了人類大腦功能網絡的拓撲性質.他們獲取了31個病人和31個健康對象的數據,由部分關聯分析和閾值估計得到90個皮層區及亞皮層區之間的功能連接,從而建立了一組無向圖.他們的發現表明,健康對象的大腦功能網絡具有高效的小世界性質,而精神分裂病人大腦的這些性質已被破壞.大腦功能網絡的高效小世界性質能夠以相對低的代價確保高效的信息傳輸,更重要的是,精神病人的大腦中前額、顳葉等地方的小世界性質被顯著的改變了.這些發現,與這種病的大腦中功能失調整合的假說相吻合.特別地,他們發現,這些改變的拓撲測度與精神分裂癥的病程相關聯.探測與估計這些改變,有助于理解病理學機制和度量精神病嚴重性的程度.小的連通度(即稀疏性)和低的功能連接強度,不僅表明稀疏的連接,也指明了精神分裂癥的功能關聯腦區之間同步性的降低.這不僅具有明顯的實用價值,還在實驗上支持了前人[6]的理論結果,即連邊密集的振子的集合比連邊稀疏的集合更加容易同步化.

中科院章祥蓀小組[31-36]系統地研究了一些生物網絡與稀疏性相關聯的性質.復旦大學章忠志小組[37-38]解析研究了一批偽分形圖形的稀疏拓撲性質.楊孔慶[39]研究組對與地理距離有關的復雜網絡曾進行系統性地概述.中科大謝彥波等[40]在綜合考慮節點度和節點之間幾何距離的綜合效應的模型中,找到了無標度網絡新的生成機制.陳力軍小組[41]提出了平均度約束的傳感器網絡控制策略.最近,呂凌媛等[8]定義了一個用于網絡鏈路預測的局部路徑指標,并指出,對于巨大而稀疏的網絡,也就是有大的N和小的平均度k—的網絡,這一指標的優越性是突出的.北京大學的Jiang Mi和Ma Ping[42]指出,在稀疏的神經元網絡中比較容易維持由重連誘導的相干共振.方錦清[43]負責的重點項目組提出了部分同步判據,并且把它運用到具有稀疏連接的同步時空系統中.最近,中科大姜羅羅等[44]在具有去邊的博弈模型中發現,當網絡變得稀疏,合作的小團體會以孤立島群的方式形成.戴俊與何大韌[45]報導了對BA(barabasi-albert)網絡中與距離相關的I-sing模型的研究結果,節點間相互作用的強度隨著幾何距離指數衰減,數值模擬求出了鐵磁-順磁的相變點.李翔[46]分別研究了小世界和無標度網絡中長程衰減耦合邊對隨機稀疏網絡的相同步的影響,指出它與網絡的一致性相關.當耦合指數小于臨界值,長程邊的密度增加會改善同步性能.

4 網絡稀疏性研究中的兩個熱點問題

當前,對網絡稀疏性探討最多的問題之一是基因調控網絡的稀疏重建算法.

一個生物組織的信息儲存在它的基因組中,所有復雜器官的基因組由長的DNA分子組成,這些DNA具有雙螺旋的核苷酸結構.基因組的基本功能單位就是基因.分子生物學的中心法則指出,信息儲存于DNA中,存儲在DNA中給定基因的信息被轉錄成為mRNA,然后再被翻譯成為蛋白質.蛋白質是細胞中基本的結構和功能單元.每個蛋白質專門承擔許多不同重要角色中的一個,例如一個結構單元,酶催化劑或者抗體.蛋白質組的一個大的子集就是起調控作用的轉錄因子(TF),它們決定什么時候、在什么地方、以多大數量將特定的基因表達為蛋白質.因為調控蛋白質自身也是基因表達的產物,它們自身也受到調控,這就產生了相互作用基因之間的復雜網絡.轉錄基因調節是細胞發育和分化的基礎,它們構成從蛋白質水平到基因向mRNA的轉錄的重要反饋機制；而且,能夠產生從同樣的遺傳信息出發實現分化的基因表達方式,即同樣的基因型可以產生不同的表現型.轉錄因子最簡單的作用就是對基因表達的抑制或者激活,即作為阻遏蛋白,或者作為激活蛋白.轉錄因子的作用,也受到其它轉錄因子的調節.所有基因相互作用的集合被稱為基因調控網絡(GRN),這是復雜系統的一個典型的例子.GRN具有以下的一般性質:a.它是稀疏的.與細胞中大的基因數目相比,每個基因只受到有限數量的其它基因的調控,遠小于所有基因的總數目.b.基因網絡是單向的.c.基因受到集體活動機制的調節,一個基因的表達水平經常依賴于不同調控蛋白質的集體活動.

目前,根據實驗數據進行分析處理來確定GRN是極為復雜的.這一工作受到以下幾個方面的制約: a.表達模式的數目M一般是遠小于測量到的基因的數目N,可得到的信息是不完整的.b.數據包含噪聲.c.微陣列(microarray,生物芯片)實驗不是測量單個細胞的表達形貌,而是一群相似的細胞的形貌,這樣的平均過程會掩蓋單一細胞的調節過程的細節特征.d.非調控機制不能被考慮到基于表達的算法上.目前,研究者們設計了各種各樣的預測算法,如迭代貪婪算法[47]、貝葉斯推斷[48]、核-重加權的邏輯斯蒂遞歸[49],進行GRN的稀疏重建.系統生物學、數學、計算機、物理、自動控制領域的研究人員花費了大量的人力物力來建立模型[50]與設計算法,取得了豐富的成果.但是,這類方法本身要精確推斷出GRN的結構乃至具體的單向邊調控關系,本質上是非常困難的.統計物理學應當能夠發揮基本作用,尤其是理解不涉及具體調控細節的共同的基本性質,如稀疏性的來源以及入度和出度分布,集群系數等.另一個值得關注的課題是移動ad hoc通訊網絡(MANET).它是各國通信、計算機、自動控制與系統科學研究者開發下一代綜合通訊系統的共同課題.MANET可以以手提電腦、手機、傳感器等作為無線通訊節點.它不設置基站,每個節點通過多跳無線連接,以確定的通訊半徑平等地同時擔負發射、接

收和轉發控制等功能,特別適用于搶險救災、沙漠、草原、戰場等惡劣環境的群體通訊.當前,一系列新問題有待解決:可變拓撲結構的連通性、媒體接入控制(MAC)機制(當一個節點正在向外發送信息,在它的通訊半徑內的其它節點不能同時發出信息)、節能策略、路由策略和保密性等.近年來,物理學界開始在統計物理的思路下建立MANET的復雜網絡模型[51],尋求新的算法、策略、原理與技術.

5 網絡稀疏性的研究具有突出的統計物理意義

網絡的平均度與系統的有效維數直接關聯[52],而維度是統計物理中確定相變普適類的關鍵參數之一.此外,自組織臨界性也與平均度即稀疏性密切相關.在同時存在拓撲無序(如復雜網絡)與節點狀態無序的系統中,小的稀疏的網絡不大能夠耐受較大的漲落,容易發生動力學的失穩及轉變.稀疏性普遍存在于絕大數生物系統以及其它領域的真實網絡中,平均場理論在這里的適用性是值得檢驗的,因為它對于較高的維度才是準確的.另外,由于網絡中不存在平移對稱性和旋轉對稱性,以往常用于大塊均勻物質系統的方法一般就不能照搬使用,這是對傳統統計物理的挑戰.所以,研究網絡的稀疏性有希望探索出新的方法、技術乃至原理.

在前人的經典復雜網絡模型[1-3]中,平均度經常是作為給定的條件出現的,即事先假定每個節點必須和給定數量的其他節點相連,如WS(wattsstrogatz)小世界網絡和BA網絡,而不去探討為什么這樣.在BA模型中,新加點具有相同的出度.在NW(newman-watts)小世界模型中,加邊過程是隨機選擇兩點,不涉及加邊的原因,即與節點的性質或者狀態有什么關系.后來的一些改進模型,特別是耦合演化網絡模型[25,53-69],逐漸有意識地克服這一缺陷.但是,完全由局域信息、近鄰的相互作用確定最終穩態網絡平均度的模型仍然不多,特別是,能夠同時再現無標度性質和大的集群系數[70],又能自組織再現稀疏性質的模型為數更少.這就使人不得不思考稀疏性的來源問題.筆者認為,它不應當是先驗的、作為前提給出的,而應當是由個體相互作用的機制導出的,或者是由耦合演化過程自發涌現的.統計物理思想和方法對于理解這類涌現性質具有天然的優勢.

網絡稀疏性相關效應的分析已經有豐富的結果,但是,大多數是非物理領域的研究者的貢獻.根據目前對scholar.google.com網站的檢索,有關網絡稀疏性的論文數目已達約4 460篇.但是APS (The American Physical Society)期刊至今所發表的8 920多篇復雜網絡論文中,只有93篇是與稀疏網絡相關的,而權威期刊《Phys.Rev.Lett.》上只發表了8篇[71-78].雖然已經有重要進展,但是,一般分別側重于個別問題,原理性的探討和總結還不多見.從2002年到現在,國家自然科學基金委已經資助與復雜網絡相關的項目約219個,極大地推動了我國科技界在網絡模型和網絡動力學等方面的研究進展.但是,到目前為止,還沒有發現一個基金課題是明確表明針對網絡稀疏性開展研究的.顯然,從本文的綜述可見,稀疏性問題貌似簡單,也被許多人忽視,然而,其重要性無疑是不容小覷的.可以預期,對網絡稀疏性起源與效應的深入探討,會拓展人們認識復雜系統的視角,導出更具有統計物理色彩的新的研究范式.

參考文獻:

[1] ALBERT R,BARABáSI A.Statistical mechanics of complex networks[J].Reviews of Modern Physics, 2002,74(1):47-97.

[2] BARABáSI A,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439): 509-512.

[3] WATTSD J,STROGATZ S H.Collective dynamics of small-world networks[J].Nature,1998,393(6684): 440-442.

[4] 何大韌,劉宗華,汪秉宏.復雜系統與復雜網絡[M].北京:高等教育出版社,2009.

[5] ANDRECUT M,HUANGS,KAUFFMANSA.Heuristic approach to sparse approximation of gene regulatory networks[J].Journal of Computational Biology,2008, 15(9):1173-1186.

[6] ARENASA,DIAZ-GUILERA A,PEREZ-VICENTECJ. Synchronization reveals topological scales in complex networks[J].Physical Review Letters,2006,96 (11):114102.

[7] BOGU?áM,PASTOR-SATORRASR.Class of correlated random networks with hidden variables[J].Physical Review E,2003,68(3):36112.

[8] LüL Y,JIN C H,ZHOU T.Similarity index based on local paths for link prediction of complex networks [J].Physical Review E,2009,80(2):46122.

[9] ALON U.An Introduction to Systems Biology:Design Principles of Biological Circuits[M].Boca Raton:CRC Press,2007.

[10] HEARD E,TISHKOFF S,TODD J A,et al.Ten years of genetics and genomics:What have we achieved and where are we heading[J].Nature Reviews Genetics, 2010,11(10):723-733.

[11] KUNDU S.Amino acid network within protein[J]. Physica A:Statistical Mechanics and its Applications, 2005,346(1/2):104-109.

[12] OVERBYE T J,WEBER J D.Visualizing the electric grid[J].IEEE Spectrum,2002,38(2):52-58.

[13] KRAPIVSKY P L,REDNER S.Network growth by copying[J].Physical Review E,2005,71(3):36118.

[14] CABREROS,PA?EDA X G,PLAGEMANN T,et al.O-verlay solution for multimedia data over sparse MANETs[C]∥Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing:Connecting the World Wirelessly.New York:Association for Computing Machinery,2009: 1056-1061.

[15] LI Zhuo-qun,SUN Ling-fen,IFEACHOR E C.Rangebased relative velocity estimations for networked mobile devices[J].IEEE Transactions on Vehicular Technology,2009,58(4):2095-2099.

[16] WANG Li,ZHU Chen-ping,GU Zhi-ming,et al.Modeling mobile ad hoc communication networks on two-dimensional square lattice[J].Frontiers of Physics in China,2009,4(4):556-560.

[17] 賈龍濤,朱陳平,陳昌東.隨機納米碳管網絡及其滲流性質[J].復雜網絡與復雜性科學,2011,8(3):13-18.

[18] MOTTER A E,DE MOURA A P,LAI Ying-cheng,et al.Topology of the conceptual network of language [J].Physical Review E,2002,65(6):65102.

[19] LIU Zong-hua,LAI Ying-cheng,YE Nong,et al.Connectivity distribution and attack tolerance of general networks with both preferential and random attachments[J].Physics Letters A,2002,303(5/6): 337-344.

[20] WU Xiao-yan,LIU Zong-hua.How community structure influences epidemic spread in social networks[J]. Physica A:Statistical Mechanics and its Applications, 2008,387(2/3):623-630.

[21] WATTS D J.A simple model of global cascades on random networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002, 99(9):5766-5771.

[22] REICHARDT J,BORNHOLDT S.Statistical mechanics of community detection[J].Physical Review E,2006, 74(1):16110.

[23] EHRHARDT G,MARSILI M,VEGA-REDONDO F.Diffusion and growth in an evolving network[J].International Journal of Game Theory,2006,34(3): 383-397.

[24] BORNHOLDT S,R?HL T.Self-organized critical neural networks[J].Physical Review E,2003,67 (2):66118.

[25] BORNHOLDT S,R?HL T.Topological evolution of dynamical networks:Global criticality from local dynamics[J].Physical Review Letters,2000,84(26): 6114-6117.

[26] MEISEL C,GROSS T.Adaptive self-organization in a realistic neural network model[J].Physical Review E, 2009,80(6):61917.

[27] VAZQUEZ F,EGUíLUZ V M,MIQUEL M S.Generic absorbing transition in coevolution dynamics[J].Physical Review Letters,2008,100(10):108702.

[28] OHTSUKI H,NOWAK M A.Evolutionary stability on graphs[J].Journal of Theoretical Biology,2008,251(4):698-707.

[29] BASSETT D S,MEYER-LINDENBERG A,ACHARD S,et al.Adaptive reconfiguration of fractal small-world human brain functional networks[J].Proceedings of the National Academy of Sciences,2006,103(51): 19518-19523.

[30] LIU Yong,LIANG Meng,ZHOU Yuan,et al.Disrupted small-world networks in schizophrenia[J].Brain, 2008,131(4):945-961.

[31] ZHANGShi-hua,JIN Guang-xu,ZHANG Xiang-sun,et al.Discovering functions and revealing mechanisms at molecular level from biological networks[J].Proteomics,2007,7(16):2856-2869.

[32] ZHANGShi-hua,LIU Hong-wei,NING Xue-mei,et al. A graph-theoretic method for mining functional modules in large aparse protein interaction networks[C]∥Proceedings of the Sixth IEEE International Conference on Data Mining-Workshops,2007:130-135.

[33] ZHANGShi-hua,LIU Hong-wei,NING Xue-mei,et al. A hybrid graph-theoretic method for mining overlapping functional modules in large sparse protein interaction networks[J].International Journal of Data Mining and Bioinformatics,2009,3(1):68-84.

[34] ZHANGShi-hua,NING Xue-mei,DING Chris,et al. Determining modular organization of protein interaction networks by maximizing modularity density[J]. BMCSystems Biology,2010,4(2):S10.

[35] ZHANGShi-hua,NING Xue-mei,ZHANG Xiang-sun,et al.Graph kernels,hierarchical clustering,network community structure:Experiment and comparative analysis[J].The European Physical Journal B,2007,57 (1):67-74.

[36] ZHANGShi-hua,WANG Rui-sheng,ZHANG Xiang-sun. Uncovering fuzzy community structure in complex networks[J].Physical Review E,2007,76(4):46103.

[37] ZHANGZhong-zhi,COMELLAS F,FERTIN G,et al. High-dimensional apollonian networks[J].Journal of Physics A:Mathematical and General,2006,39 (8):1811.

[38] ZHANG Zhong-zhi,ZHOU Shui-geng,FANG Lu-jun,et al.Maximal planar scale-free sier pinski networks with small-world effect and power law strength-degree correlation[J].Europhysics Letters,2007,79(3):38007.

[39] YANG Kong-qing,YANG Lei,GONGBai-hua,et al.Geographical networks:Geographical effects on network properties[J].Frontiers of Physics in China,2008,3 (1):105-111.

[40] HU Bo,JIANG Xin-yu,DING Jun-feng,et al.A model of weighted network:The student relationships in a class[DB/OL].[2004-08-06].http:∥arxiv.org/ abs/cond-MAT/0408125

[41] 陳力軍,毛鶯池,陳道蓄,等.平均度約束的無線傳感器網絡拓撲控制[J].計算機學報,2007,30(9): 1544-1550.

[42] JIANG Mi,MA Ping.Coherence resonance induced by rewiring in complex networks[J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2009,19 (1):013115.

[43] 方錦清,汪小帆,鄭志剛.非線性網絡的動力學復雜性研究[J].物理學進展,2009,29(1):1-74.

[44] JIANG Luo-luo,MATJA?P,WANG Wen-xu,et al.Impact of link deletions on public cooperation in scalefree networks[J].Europhysics Letters,2011,93 (4):40001.

[45] DAI Jun,HE Da-ren.Phase transition of a distance-dependent ising model on the barabasi-albert network [J].Chinese Physics Letters,2007,24(12):3355.

[46] LI Xiang.Phase synchronization in complex networks with decayed long-range interactions[J].Physica D: Nonlinear Phenomena,2006,223(2):242-247.

[47] ANDRECUT M,KAUFFMAN S A.On the sparse reconstruction of gene networks[J].Journal of Computational Biology,2008,15(1):21-30.

[48] HUSMEIER Dirk.Sensitivity and specificity of inferring genetic regulatory interactions from microarray experiments with dynamic bayesian networks[J]. Bioinformatics,2003,19(17):2271-2282.

[49] AHMED A,XING E P.Recovering time-varying networks of dependencies in social and biological studies [J].Proceedings of the National Academy of Sciences, 2009,106(29):11878.

[50] SONG L,KOLAR M,XING E P.KELLER:estimating time-varying interactions between genes[J].Bioinformatics,2009,25(12):128-136.

[51] WANG Li,ZHU Chen-ping,GU Zhi-ming.Scaling of critical connectivity of mobile ad hoc networks[J]. Physical Review E,2008,78(6):066107.

[52] NEWMAN M.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America, 2002,99(12):7821-7826.

[53] BARRAT A,BARTHELMY M,VESPIGNANI A.Weighted evolving networks:Coupling topology and weight dynamics[J].Physical Review Letters,2004,92 (22):228701.

[54] CASTELLANOC,FORTUNATOS,LORETO V.Statis-tical physics of social dynamics[J].Reviews of Modern Physics,2009,81(2):591-646.

[55] EGUILUZ V M,ZIMMERMANN M G.Transmission of information and herd behavior:An application to financial markets[J].Physical Review Letters,2000,85 (26):5659-5662.

[56] EHRHARDT G C,MARSILI A,VEGA-REDONDO F. Phenomenological models of socioeconomic network dynamics[J].Physical Review E,2006,74 (3):036106.

[57] FRONCZAK P,FRONCZAK A,HOLYST J A.Self-organized criticality and coevolution of network structure and dynamics[J].Physical Review E,2006, 73:046117.

[58] GROSS T,SAYAMA H.Understanding Complex Systems[M].Berlin:Springer,2009:73-106.

[59] HOLME P,NEWMAN M.Nonequilibrium phase transition in the coevolution of networks and opinions[J]. Physical Review E,2006,74(5):056108.

[60] ITOJ,KANEKO K.Spontaneous structure formation in a network of chaotic units with variable connection strengths[J].Physical Review Letters,2001,88 (2):028701.

[61] ITOJ,KANEKO K.Spontaneous structure formation in a network of dynamic elements[J].Physical Review E,2003,67(4):046226.

[62] LIU M,BASSLER K E.Emergent criticality from coevolution in random Boolean networks[J].Physical Review E,2006,74(4):041910.

[63] PACHECOJ M,TRAULSEN A,NOWAK M A.Coevolution of strategy and structure in complex networks with dynamical linking[J].Physical Review Letters, 2006,97(25):254103.

[64] WANG Ru,CAI Xu.The strong consensus opinion dynamics on adaptive networks[J].International Journal of Modern Physics C,2008,19(12):1939-1947.

[65] XIE Yan-bo,WANG Wen-xu,WANG Bing-hong.Modeling the coevolution of topology and traffic on weighted technological networks[J].Physical Review E, 2007,75(2):026111.

[66] ZHOU C,KURTH J.Dynamical weights and enhanced synchronization in adaptive complex networks[J]. Physical Review Letters,2006,96(16):164102.

[67] ZHU Chen-ping,XIONG Shi-jie,TIAN Ying-jie,et al. Scaling of directed dynamical small-world networks with random responses[J].Physical Review Letters, 2004,92(21):218702.

[68] ZIMMERMANN M,EGUILUZ V,MIGUEL S M.Cooperation,adaptation and the emergence of leadership [M]∥KIRMAN A,ZIMMERMANN J B.Economics with Heterogeneous Interacting Agents.Berlin: Springer,2001:73-86.

[69] ZIMMERMANN M,EGUILUZ V,MIGUEL S M.Coevolution of dynamical states and interactions in dynamic network[J].Physics Review E,2004,69(6):065102.

[70] ZHU Chen-ping,LIU Xiao-ting,GU Zhi-ming.Flathead power-law,size-independent clustering,and scaling of coevolutionary scale-free networks[J].Frontiers of Physics,2011,6(3):337-341.

[71] DAS M,MACKINGTOSH F,LEVINE AJ.Effective medium theory of semiflexible filamentous networks[J].Physical Review Letters,2007,99(3):038101.

[72] DOROGOVTSEV S N,GOLTSEV A,MENDES J F F. K-core organization of complex networks[J].Physical Review Letters,2006,96(4):040601.

[73] GALLOS L K,ARGYRAKIS P.Absence of kinetic effects in reaction-diffusion processes in scale-free network[J].Physical Review Letters,2004,92 (13):138301.

[74] JAHNKE S,MEMMEISHEIMER R M,TIMME M.Stable irregular dynamics in complex neural networks [J].Physical Review Letters,2008,100(4):048102.

[75] LUCCOLI S,POLITI A.Irregular collective behavior of heterogeneous neural networks[J].Physical Review Letters,2010,105(15):158104.

[76] PEIXOTO T P.Redundancy and error resilience in boolean networks[J].Physical Review Letters,2010, 104(4):048101.

[77] RANGAN A V.Three-dimensional visualization of a human chromosome using coherent x-ray diffraction [J].Physical Review Letters,2009,102(1):018101.

[78] REICHARDT J,LEONE M.(Un)detectable cluster structure in sparse networks[J].Physical Review Letters,2008,101(7):078701.

A review on statistical physics for the sparsity of complex networks

ZHUChen-ping, ZHANGYong-mei, LIU Xiao-ting, WANGRong-fang, WANGXin-guang
(Departmemt of Applied Physics,Namjimg Umiversity of Aeromautics amd Astromautics,Namjimg 210016,Chima)

Most practically existing complex networks are sparsely connected,namely,the average degrees of them are much smaller than their total numbers of nodes:k—?N.Up till now,the research on the origin of this property,its effects on functions of networks and dynamic processes on networks,and its possible applications have been still far less than adequate.Actually,sparsity is closely related with other topological properties.In recent years,much progress has been made on sparseness of complex networks from both theoretic and experimental aspects.However,principle conclusion is still anticipated.From the view point of statistical physics,it is believed that the sparsity of networks should be accounted as an emergent property of interactions between individuals in complex systems,instead of a priori prerequisite for existing models.In the present paper,we attempt to review previous investigations with statistical physics on the sparseness of complex networks.

complex metwork；sparsity；statistical physics

N 94文獻標示碼：A

1007-6735(2011)05-0425-08

2011-09-12

朱陳平(1958-),男,副教授.研究方向:統計物理與復雜性科學.E-mail:chenpingzhu@yahoo.com.cn