第7卷第2-3期復雜系統(tǒng)與復雜性科學Vol. 7 No. 2-3010年9月COMPLEX SYSTEMS AND COMPLEXITY SCIENCESep.2010文章編號:1672-3813(2010)02-03-0033-05網(wǎng)絡(luò)傳播動力學李翔,劉宗華2,汪秉宏31.復旦大學,上海200433;2.華東師范大學,上海200241;3.中國科學技術(shù)大學,合肥230026摘要:病毒的流行、謠言的散布、觀點的傳遞都是在不同網(wǎng)絡(luò)上的形形色色的傳播現(xiàn)象,既存在著現(xiàn)象后的不同起因和特征,更存在著千絲萬縷的聯(lián)系和共通的演化機理。匯總了復旦大學、華東師范大學和中國科學技術(shù)大學的研究小組過去幾年里在網(wǎng)絡(luò)傳播動力學的研究成果。關(guān)鍵詞:復雜網(wǎng)絡(luò);傳播動力學;網(wǎng)絡(luò)中圖分類號:N941文獻標識碼:AOn Spreading Dynamics on NetworksLIhua2. WANG(1. Fudan University, Shanghai 200433, China; 2. East China Normal University, Shanghai 230026, China3. University of Science and Technology of China, Hefei 230026, CIAbstract: The prevalence of epidemics, rumors, and opinions are various spreading phenomena on dif-ferent categories of networks, which not only exhibit specific features and backgrounds, but also sharesome mechanisms and extensive interconnections. This paper is a brief collection including the work andhinking on this topic from the research groups of Fudan Univeristy, East China Normal University, andUniversity of Science and Technology of China.Key words: complex networks; spreading dynamics; network網(wǎng)絡(luò)傳播研究涉及疾病擴散、輿論傳播及其動力學等問題。(計算機或生物)病毒在網(wǎng)絡(luò)上的流行與傳播行為是復雜網(wǎng)絡(luò)理論的主要研究內(nèi)容之一,也是近年來人們在社會經(jīng)濟活動中最為密切關(guān)注的一個主題。SARS、禽流感、沖擊波、震蕩波、熊貓燒香、灰鴿子等生物和計算機病毒的肆虐給人們帶來了以千億美元計數(shù)的巨大經(jīng)濟損失,而且這一傳播過程通常極為迅速。以2004年的“震蕩波”蠕蟲病毒為例,在短短的十余天內(nèi)全球數(shù)千萬臺計算機遭受到它的攻擊,其傳播速度驚人。復雜網(wǎng)絡(luò)傳播動力學行為的研究還包括對謠言輿論、觀點等主體在網(wǎng)絡(luò)上擴散現(xiàn)象的探討。本文主要匯總了復旦大學、華東師范大學和中國科學技術(shù)大學這幾個研究小組在過去幾年里對上述問題的若干思考。歷史上流行病動力學的研究已經(jīng)提出了幾個代表性模型。伴隨復雜網(wǎng)絡(luò)研究的興起,復旦大學研究小組-間°通過數(shù)值計算和理論分析研究網(wǎng)絡(luò)上傳播動力學的若干模型,在探索復雜網(wǎng)絡(luò)的傳播臨界值理論基礎(chǔ)上,結(jié)合非線性動力學分析了傳播動態(tài)過程中存在的混沌、分叉等典型動力學行為特征,圍繞小世界、無標收稿日期:2010-06-14中國煤化工基金項目:園家自然科學基金項目(10635040,10975126,60874089,91024026CNMH校博士點基金項目(20093402110032);教育部新世紀優(yōu)秀人才計劃項目(NCET-09-031知-^目(09QH1400200)作者簡介:李(1975-),男,湖南人,教授博導,主要研究方向為復雜網(wǎng)絡(luò)系統(tǒng)理論與應(yīng)用。復雜系統(tǒng)與復雜性科學2010年9月度網(wǎng)絡(luò)等典型模型分析了拓撲結(jié)構(gòu)對于傳播動力學的影響等。值得特別指出的是,研究小組發(fā)現(xiàn)在時延環(huán)境下小世界特性是網(wǎng)絡(luò)系統(tǒng)中不可避免地存在震蕩傳播過程的特征結(jié)構(gòu)0。這一系列的研究結(jié)果有助于分析相應(yīng)控制策略的有效性,并提出抑制疾病在網(wǎng)上傳播的對策6。針對人們社會活動的網(wǎng)絡(luò)化特征,復旦大學研究小組還進一步分析人群與不同現(xiàn)實網(wǎng)絡(luò)交互影響下的網(wǎng)絡(luò)傳播動力學性能分析及其防控策略,圍繞人群的個體差異性,研究了在考慮不同類型的冪律和指數(shù)分布的易感性和傳染能力時,移動的人群中爆發(fā)流行病的臨界值條件,得到了個體差異性與病毒蔓延相關(guān)性等-24-。復雜網(wǎng)絡(luò)上流行病傳播可在更高級別上進行研究,比如一個節(jié)點對應(yīng)一個城市或一個地區(qū),因而單個節(jié)點上可以同時擁有大量的粒子或個體,以前的研究主要集中在個體擴散對流行病傳播的影響,近年來, Vespignani小組開始考慮一個節(jié)點可以同時被多個粒子占據(jù)的反應(yīng)-擴散模型。以此為契機,華東師范大學的研究小組探討了個體遷移模式對于無標度網(wǎng)絡(luò)上流行病傳播的影響,著重考慮了人類活動的兩個特點:目的性與集聚性對流行病傳播的影響:23)。因為人類的旅行活動具有目的性,是不能嚴格當做隨機擴散的;另外,人類的活動容易導致在公共場所的集聚現(xiàn)象,這種活動會加劇流行病的傳播。1華東師范大學課題組的研究目前復雜網(wǎng)絡(luò)上的流行病傳播模型與真實發(fā)生的過程還有相當大的距離,比如人類活動不能簡單等同于復雜網(wǎng)絡(luò)上的隨機行走,而是具有其自身的獨特特征,如社區(qū)性旅行目的性及對場所的時間段占據(jù)特性等。這些顯著的特征是如何影響流行病的傳播是一個亟待研究的問題。鑒于此,我們在以前工作的基礎(chǔ)上1-121,對復雜網(wǎng)絡(luò)上流行病的傳播做了較系統(tǒng)的研究?；谡鎸嵉纳鐣偸且陨鐓^(qū)為單位的,我們首先討論了社區(qū)結(jié)構(gòu)對流行病傳播帶來的影響構(gòu)造了一個社區(qū)網(wǎng)模型來研究其上的流行病傳播-1,并用主方程得到了解析解。一個社區(qū)模型的典型例子是曼谷與周圍72個省之間的登革熱傳播呈時間與空間的雙周期行為,其機制可通過一個分立的映像得到說明。社區(qū)特征也是疾病預防與控制中必須考慮的因數(shù)。由于城市依賴于外部的給養(yǎng)而生存,無法做到與外界的完全隔絕,因此貌似安全的城市間的接觸也存在著間接傳播疾病的隱患。我們發(fā)現(xiàn)人員的遷移可導致流行病的間接傳播,且社區(qū)結(jié)構(gòu)有利于病毒的存活。然后,考慮到人們?nèi)菀自诠矆鏊奂奶攸c側(cè)重研究了公共場所的人員聚集對流行病傳播的影響,并發(fā)現(xiàn)了加速傳播效應(yīng)。接著考慮到現(xiàn)實中人類的遷移活動往往是一個較長時間的旅行,且?guī)в写_定性傾向,比如我們國家的春運,在遷移過程中,病毒攜帶者可以與固定鄰居進行長時間接觸,也可以與不同站臺、不同車廂的人員進行依次接觸。這與隨機行走是根本不同的,隨機行走的下一個節(jié)點或下一站總是隨機選取的,而傾向性旅行者的下一站是預先選好的、是固定了的?？紤]到人類活動的這種目的性特征,我們首次討論了病毒攜帶者的非隨機行走如通過飛機火車等長途旅行帶來的加速傳播后果”2。此外,我們還考慮了真實情況下社會網(wǎng)的結(jié)構(gòu)總是動態(tài)變化的,一個人此時在甲處,下一時刻就可能在乙處;甲處此時有很多人,下一時刻可能是空的,如教室與食堂等;因此我們將固定的社會網(wǎng)絡(luò)結(jié)構(gòu)拓廣成更實際的動態(tài)社會網(wǎng),即討論了人們對場所的部分時間占據(jù)導致的移動效應(yīng)對流行病傳播的影響,發(fā)現(xiàn)了感染人數(shù)在某一最優(yōu)移動幾率處達到極大(。另一方面,由于流行病的擴散特征,如何從擴散方面進行刻畫2及將流行病模型用于研究謠言的傳播也是我們感興趣的問題。2中國科學技術(shù)大學課題組的研究2.1.疾病傳播1)以性行為為例,雖然科學家通過研究發(fā)現(xiàn)性關(guān)系網(wǎng)具有無標度性質(zhì)但是我們不能根據(jù)“無標度網(wǎng)絡(luò)上沒有疾病閾值”的結(jié)論肯定疾病一定會大范圍的爆發(fā)。由中國煤化工雖然有的個體有CNMHG或者感染別人的兀呼八誕山一個修正的流行病傳播模型,其中每一節(jié)點在每一時步被賦予相同的活躍接觸能力A。通過平均場論得到與以前研究不同的解第7卷第2-3期李翔,等:網(wǎng)絡(luò)傳播動力學析結(jié)果,發(fā)現(xiàn)非零閾值為1/A,這表明閾值與所研究的網(wǎng)絡(luò)的拓撲結(jié)構(gòu)無關(guān)。模擬與解析結(jié)果一致。進步,研究了流行病傳播的時間行為,發(fā)現(xiàn)一種具有3個平臺的級聯(lián)動力學。流行病感染一旦到達了高連接性的網(wǎng)絡(luò)中心結(jié)點,就會通過逐步向較小度類結(jié)點傳播的級連過程遍布幾乎整個網(wǎng)絡(luò)。于是,在以前感染的網(wǎng)絡(luò)中心結(jié)點得以恢復之后,疾病只能夠傳播到較小度類的結(jié)點,直至所感染的個體全部恢復。這一結(jié)果對于動力學控制策略的確立可能具有實際的重要性26-2)不同的傳播過程可以看作是接觸過程( contact process)的一個特例,如疾病傳播、信息傳播等。因此楊銳等人通過假定個體的接觸過程存在偏愛性,即W(k):A,當B>0表示個體偏向接觸度大的結(jié)點,反之表示接觸度小的結(jié)點,當B=0,表示無偏愛的接觸過程。通過數(shù)值模擬和理論證明發(fā)現(xiàn)存在一個最優(yōu)值B=-1,使傳播范圍達到最大化。這一結(jié)果和復雜網(wǎng)絡(luò)上的最優(yōu)同步能力的結(jié)論一致1。3)當某種傳染病爆發(fā)的時候,必然會引起一些外界因素的變化,如個體采取自我保護措施,政府采取預警機制等。張海峰等人研究自我接種機制對疾病傳播行為的影響。由于接種或不接種都面臨一定的風險和代價,因此個體通過比較自我被感染的風險和代價決定是否采取接種。研究發(fā)現(xiàn),之前的結(jié)果表明由于無標度網(wǎng)絡(luò)中有很多度大的結(jié)點,使疾病很容易爆發(fā);而在自我接種機制下度大結(jié)點同時面臨著更大的風險,因此他們更愿意采取接種行為。此結(jié)果表明在自我接種機制下,即使在無標度網(wǎng)絡(luò)上的疾病也很容易控制)。由于當前各種媒介的存在使人們可以很快地了解不同區(qū)域的發(fā)病情況,因而采取相應(yīng)的措施。當人們了解到某個區(qū)域的感染情況比較嚴重時,個體會采取斷開與高發(fā)區(qū)的聯(lián)系或者重新建立其他的聯(lián)系。韓筱璞通過引入預警機制,研究小世界網(wǎng)絡(luò)上的SI模型,發(fā)現(xiàn)預警機制可以降低疾病的傳播范圍。4)以前對網(wǎng)絡(luò)上的疾病控制策略往往考慮免疫結(jié)點,如隨機免疫、目標免疫、熟識者免疫等。雖然這些方法在特定的條件下證明是有效的,但是免疫結(jié)點的方式破壞了網(wǎng)絡(luò)的連通性,在有些條件下保證網(wǎng)絡(luò)的連通性是非常有必要的,比如 Internet網(wǎng)絡(luò)中,如果關(guān)閉那些度大的路由,會嚴重制約 Internet網(wǎng)絡(luò)的作用。所以張海峰等人提出了一種刪邊的控制策略:刪除兩端結(jié)點度都比較大的連線。通過模擬發(fā)現(xiàn),這種方法可以有效地控制疾病的傳播,并且可以很好地保證網(wǎng)絡(luò)的連通性。5)網(wǎng)絡(luò)上不同邊的權(quán)重往往不同,權(quán)重可能導致不同的傳播行為,因此嚴剛等人研究含權(quán)網(wǎng)絡(luò)上的疾病傳播行為,通過與無權(quán)網(wǎng)絡(luò)比較發(fā)現(xiàn),含權(quán)網(wǎng)絡(luò)上的疾病傳播速度首先增加到一個峰值,然后以冪率形式下降,同時,不同于無權(quán)網(wǎng)絡(luò),含權(quán)網(wǎng)絡(luò)上疾病傳播的分層現(xiàn)象不明顯。此外,他們發(fā)現(xiàn),權(quán)重分布越分散越不利于疾病的傳播。212.2輿論傳播1)姜羅羅等人研究了自我主張對于一個有向小世界社會網(wǎng)絡(luò)中的公眾奧論形成的影響。系統(tǒng)呈現(xiàn)出一個從公眾輿情一致狀態(tài)到多種觀點并存的無序狀態(tài)轉(zhuǎn)變的非平衡相變。在有向小世界網(wǎng)絡(luò)中,斷邊重連概率的大小表征了個體間有向長程聯(lián)系的強弱。研究表明奧情動力學行為對于長程有向相互作用之密度及自我肯定之強度非常敏感。當個體間的有向長程聯(lián)系很弱并且個體不堅持自己觀點的時候,體系呈現(xiàn)出連續(xù)相變;相反,當個體間的有向長程聯(lián)系和個體自我認同都很強的時候,體系不發(fā)生相變;當有向長程聯(lián)系和個體自我認同介于兩者之間的情況時,體系經(jīng)歷非連續(xù)相變2)在輿論傳播中,不同度的人對別人的影響可能不同,因此,楊涵新等人通過假定個體i的觀點被個體j接受的概率為式中,k,表示結(jié)點i的度。如果a>0,則度大的觀點更容易被接受,反之度小的觀點更容易被接受,通過研究發(fā)現(xiàn),存在適當?shù)腶>0,使收斂時間最短M。中國煤化工3)在輿論傳播過程中,如果兩個個體的觀點相差太大CNMHG基于此,郭強等人假定兩個個體如果觀點度差異大于一定的容忍度,個體就采灬栘啁。遇過及塊,心你度網(wǎng)絡(luò)上輿論傳播行為更容易達到一致,同時移動行為和增加個體密度可以提高收斂速度。復雜系統(tǒng)與復雜性科學2010年9月參考文獻:[1]李翔,王林復雜網(wǎng)絡(luò)病毒傳播動力學與控制——個體異質(zhì)與移動屬性的影響[C].2010年中國物理年會秋季會議天津,2010:17-1Li Xiang, Wang Lin. Epidemics dynamics and control on complex networks: roles of individual heterogeneity and mobility [C]Autumn Conference of Chinese Physics Society. Tianjin, 2010: 17-1[2] Li X, Cao L, Cao G. Epidemic prevalence on random mobile dynamical networks: individual heterogeneity and correlation[J]European Physical Journal B, 2010, 75:319-326[3]李期.復雜動態(tài)網(wǎng)絡(luò)傳播動力學[刀].力學進展,2008,38(6):723-732Li Xiang Spreading dynamics on complex dynamical networks[ J]. Advances in Mechanics, 2008, 38(6):723-732[4]曹崀曹桂芳李翔移動多智能體系統(tǒng)的病毒傳播研究[C].第七屆全球智能控制與自動化大會.重慶,2008:18801884Cao Lang, Cao Guifang, Li Xiang. The study of epidemic spreading in a mobile multi-agent system[ C]. Proceedings of the 7thWorld Congress on Intelligent Control and Automation. Chongqing, 2008: 1880-1884[5]曹桂芳,曹遴,李翔具有感染顯性率的移動多智能體系統(tǒng)病毒傳播及其控制策略[].中國控制與決策2008年會議論文Cao Guifang, Cao Lang, Li Xiang. The study of epidemic spreading on a mobile multi-agent system with infective expressivity andits control stralegy[ C]. Proceedings of Chinese Control and Decision Conference. Yantai, 2008: 4001-4004[6]Xu D, Li X, Wang X F. An investigation on local area control of virus spreading in complex networks[J]. Acta Physica Sinica2007,56(3):1313-1317[7] Li X, Wang X F. On the stability of epidemic spreading in small-world networks: how prompt the recovery should be? [J.International Journal of Systems Science, 2007, 38(5): 400-407.[8] Guo W P, Li X, Wang X F. Epidemics and immunization on euclidean distance preferred small-world networks[ J]. Physica A[9] Li X,Wang X F. Controlling the spreading in small-world evolving networks: stability, oscillation, and topology[J].IEEETransactions on Automatic Control, 2006, 51(3): 534-540[10] Li X, Chen G R. Models, dynamics and control of spreading in complex networks: a survey[ J]. Dynamics of Continuous, Dis-crete and Impulsive Systems-B, 2006, 13(c): 109-116[11] Liu Z H, Lai Y C, Ye N. Propagation and immunization of infection on general networks with both homogeneous and heterogeneous components[J]. Phys Rev E, 2003, 67: 031911[12] Lai Y C, Liu Z H, Ye N. Infection dynamics on growing networks[ J]. International Joumal of Modern Physics B, 2003, 174045-4061[13] Liu Z H, Hu B. Epidemic spreading in community networks[ J]. Europhys Lett, 2005,72: 315.[14]Zhou Y Z, Liu Z H, Zhou J. Periodic wave of epidemic spreading in community networks[ J]. Chin Phys Lett, 2007, 24: 581[15] Wu X Y, Liu Z H. How community structure influences epidemic spread in social networks[J]. Physica A, 2008,387:623[16] Zhou ], Liu Z H. Epidemic spreading in communities with mobile agents[J]. Physica A, 2009, 388: 1228[17]Zhang H, Liu Z H, Ma W C. Epidemic propagation and microscopic structure of complex networks[ J]. Chin Phys Lett, 200623:105[18 Tang M, Liu L, Liu Z H. Influence of dynamical condensation on epidemic spreading in scale- free networks[ J].PRE, 2009,79016108[19] Tang M, Liu Z H, Li B W. Epidemic spreading by objective traveling[ J]. Europhys Lett, 2009, 87: 18005[20]唐明個體遷移模式對于無標度網(wǎng)絡(luò)上流行病傳播的影響[,2009年第五屆全國復雜網(wǎng)絡(luò)學術(shù)會議青島,2009:14Tang Ming. Influence of individual mobility patterns on epidemic spreYH中國煤化工CNMHGConference on Complex Network. Qingdao, 2009: 14-17[21] Liu Z H. Effect of mobility in partially occupied complex networks[J]. Phys Rev E, 2010, 81: 016110第7卷第2-3期李翔,等:網(wǎng)絡(luò)傳播動力學37[22]wu X Y, Liu Z Hnie diffusion on complex networks[ J]. Chin Phys Lett, 2007, 24: 1118[ 23] Liu ZH, WuXYAn alternative approach to characterize the topology of complex networks and its application indemic spreading[ J]Comput Sci China, 2009(3): 324[24] Zhou J, Liu Z H. Epidemic spreading in complex networks[ J]. Front Phys China, 2008, (3): 331[25]Zhou J, Liu Z H, Li B W. Influence of network structure on rumor propagation[ J]. Phys Lett A, 2007, 368: 458[26] Zhou T, Liu J G, Bai W J, et al. Behaviors of susceptible-infected epidemics on scale-free networks with identical infective[27] Yang R, Wang B H, Ren J, et al. Epidemic spreading on heterogeneous networks with identical infectivity[ J]. Phys Lett A[28]Yang R, Zhou T, Xie Y B, et al. Optimal contact process on complex networks[ J]. Phys Rev E, 2008, 78: 06610929]Zhang H F, Zhang J, Zhou C S, et al. Hub nodes inhibit the outbreak of epidemic under voluntary vaccination[ J]. New JPhys,2010,12:023015[ 30] Han X P. Disease spreading with epidemic alert on small-world networks[ J]. Phys Lett A, 2007, 365:1[31] Zhang H F, Li K Z, Fu X C, et al. An efficient control strategy of epidemic spreading on scale-free networks[ J]. Chin PhysLett.2009,26:068901[32] Yan G, Zhou T, Wang J, et al. Epidemic spread in weighted scale-free networks[ J]. Chin Phys Lett, 2005, 22(2): 510[33]Jiang L L, Hua D Y, Zhu J F, et al. Opinion dynamics on directed small-world networks[ J]. EPJB, 2008, 65: 251[34] Yang H X, WuZ X, Zhou C S, et al. Effects of social diversity on the emergence of global consensus in opinion dyna-mics[ J]Phys Rev E,2009,80:046108[35] Guo Q, Liu JG, Wang B H, et al. Opinion spreading with mobility on scale-free networks[ J]. Chin Phys Lett, 2008, 25(2)中國煤化工CNMHG