樊潔茹，孫向東，戴 琪，靳 禎，4

（1．中北大學 理學院，山西 太原030051；2．動物衛(wèi)生與流行病學中心，山東 青島266114；3．阿爾山市農(nóng)畜產(chǎn)品質(zhì)量安全監(jiān)督檢測站，內(nèi)蒙古 興安盟137800；4．山西大學 復雜系統(tǒng)研究所，山西 太原030006）

0 引 言

小反芻獸疫俗稱羊瘟，是由小反芻獸疫病毒引起的一種急性病毒性傳染病，屬我國規(guī)定的一類動物疫?。静≈饕腥旧窖?、綿羊等小反芻動物，發(fā)病率高達100%，在嚴重暴發(fā)時，死亡率為100%．2014年春季，全國多個省份突然爆發(fā)小反芻獸疫疫情，且傳播速度快，空間分布廣，疫情呈現(xiàn)全國性擴散趨勢，全國羊群高度易感．據(jù)初步調(diào)查，疫情傳播以活羊的長途調(diào)運為主，了解活羊調(diào)運網(wǎng)絡(luò)對研究小反芻獸疫的傳播至關(guān)重要．然而大規(guī)模的流調(diào)需要耗費大量的人力、物力、財力，短時間內(nèi)不可能實現(xiàn)．現(xiàn)實中只得到活羊調(diào)運的部分信息，因此，尋找真實的活羊調(diào)運網(wǎng)絡(luò)，是我們迫切需要解決的問題．得到真實完整網(wǎng)絡(luò)的方法之一就是鏈路預測［1－5］，其目的是網(wǎng)絡(luò)重構(gòu)［6－8］，即通過重新構(gòu)建網(wǎng)絡(luò)來恢復真實網(wǎng)絡(luò)的面貌［9－10］．網(wǎng) 絡(luò) 重 構(gòu) 問 題 最 早 由Guimera 和Sales－Pardo提出，他們基于隨機分塊模型來進行網(wǎng)絡(luò)重構(gòu)［11］．此后，Zhang，Wang等人對隨機分塊模型及其可靠性進行了分析［12］．本文根據(jù)所獲得的活羊調(diào)運部分信息，利用地理信息系統(tǒng)（ArcGIS軟件）得到了全國活羊調(diào)運觀測圖，并利用鏈路預測的方法，重構(gòu)了全國活羊調(diào)運網(wǎng)絡(luò)．經(jīng)過多次實驗和市場調(diào)查，初步驗證了所得結(jié)果的可靠性和真實性．根據(jù)本文所得到的重構(gòu)網(wǎng)絡(luò)，可預測每個節(jié)點的感染途徑，感染時間和染病概率，從而有效地切斷主要風險路徑，將疫病控制在一個有限的范圍內(nèi)．

1 小反芻獸疫流行的觀測網(wǎng)絡(luò)

我國2007年首次在西藏自治區(qū)發(fā)現(xiàn)小反芻獸疫疫情，雖在2010年復發(fā)，但一直局限在西藏境內(nèi)．2013年12月，該病疫情再次發(fā)生于新疆自治區(qū)，隨后甘肅、內(nèi)蒙古、寧夏等地先后發(fā)生疫情．經(jīng)采取撲殺消毒、關(guān)閉市場、暫停調(diào)運等綜合措施，疫情一度控制在西部四省份．

圖1 2013年11月～2014年2月小反芻獸疫病例地理分布圖Fig．1 Geogrophical distributing map of peste des petits rumihants from November 2013to February 2014

隨著恢復西部省份活羊調(diào)運，加之內(nèi)地處于春節(jié)后補欄高峰期，病毒通過歐亞大陸橋傳入內(nèi)地，并經(jīng)活畜交易市場放大后流向全國多個省份．2014年3月份以來內(nèi)地相繼發(fā)生系列疫情，截止4月6日18時，全國已有18省份86地市144縣區(qū)報告發(fā)生185起疑似或確診疫情（見圖2），對3月份以來的疑似和確診疫情進行分析，超過90%的疫情是由活羊的長途調(diào)運引起的．因此了解動物的調(diào)運網(wǎng)絡(luò)對進一步研究動物疫病的傳播至關(guān)重要．

通過現(xiàn)場流行病學調(diào)查，結(jié)合市場鏈分析表明，我國活羊調(diào)運路線十分復雜，調(diào)運信息的采集相當困難，大規(guī)模的流調(diào)短時間內(nèi)做不到，只能從局部去考慮．現(xiàn)實中采取疫情溯源及疫情跟蹤方式，從小反芻獸疫疫情暴發(fā)點山東省嘉祥縣入手，對所有引入疫點的活羊進行追溯性調(diào)查，以及對從疫點輸出的活羊的去向進行跟蹤調(diào)查，得到了2014年3月全國活羊調(diào)運部分信息．根據(jù)獲得的不完全信息和數(shù)據(jù)，利用ArcGIS軟件得到全國活羊調(diào)運網(wǎng)絡(luò)觀測圖（見圖3）．

圖2 2007年以來全國疫點分布圖Fig．2 Distribution diagram about national epidemic spot since 2007

圖3 全國活羊調(diào)運網(wǎng)絡(luò)觀測圖Fig．3 Network observation map based on national live sheep migration

然而，根據(jù)疫情溯源及疫情跟蹤所得到的調(diào)運數(shù)據(jù)是不完整的，存在調(diào)運情況的缺失．除此之外，一些被調(diào)查者鑒于某些原因會隱瞞或謊報調(diào)運事實，導致所得到的調(diào)運數(shù)據(jù)為虛假信息．因此觀測網(wǎng)絡(luò)中既有一些丟失邊，又有一些虛假邊，不能反映真實的活羊調(diào)運情況．如果采取實際調(diào)研的方法揭示觀測網(wǎng)絡(luò)中丟失與虛假的鏈路需要耗費高額的成本，所以本文將利用精確的鏈路預測算法［11］，得到更加接近于真實也更加完整的活羊調(diào)運網(wǎng)絡(luò)．由兩部分決定，一是網(wǎng)絡(luò)被分成若干群的方案P3（見圖4（a）），二是分屬于兩個群的兩點之間產(chǎn)生連邊的概率矩陣Q3（見圖4（b））．網(wǎng)絡(luò)中的節(jié)點被分為三組，分別由三種形狀標識，概率矩陣Q 中的元素為式中：lOαβ為在AO中組α 和組β 之間的實際連邊數(shù)，而rαβ為兩組之間可能的最大連邊數(shù)．

2 全國活羊調(diào)運網(wǎng)絡(luò)的重構(gòu)

鏈路預測的主要目的之一就是網(wǎng)絡(luò)重構(gòu)［13］．本文從以上不完整的活羊調(diào)運觀測網(wǎng)絡(luò)（圖3）出發(fā)，利用隨機分塊模型預測網(wǎng)絡(luò)中所有鏈路的信度，然后根據(jù)鏈路信度的排序識別丟失邊和虛假邊；通過改進后的貪婪算法，加入一些預測到的丟失邊，刪除觀測網(wǎng)絡(luò)中可能存在的虛假邊，從而得到全國活羊調(diào)運重構(gòu)網(wǎng)絡(luò)．

2．1 隨機分塊模型

隨機分塊模型是最普適性的網(wǎng)絡(luò)模型之一［14－17］．該模型將網(wǎng)絡(luò)中的節(jié)點分成若干個群，兩個節(jié)點是否鏈接的概率只取決于節(jié)點所在的群．用Ω 表示全體分群方案組成的集合，給定一個具體方案P∈Ω 和這個方案下一個具體的連邊概率矩陣Q，一個隨機分塊模型M 就確定了，即M＝

（P，Q）．

以其中一種隨機分塊模型M3為例，該模型

圖4 隨機分塊模型M3Fig．4 Random block model M3

2．2 鏈路的信度

概率p（Axy＝1｜AO）可以用來表征鏈路｛vx，vy｝的信度［11，13］，

2.5 兩組患兒并發(fā)癥情況 對照組患兒并發(fā)癥發(fā)生率25.0%(10/40),3例(7.5%)肺炎，2例(5.0%)肺不張，外心包積液、低心排血量綜合征、敗血癥、瞳孔不等大、精神異常各1例(2.5%)。觀察組并發(fā)癥發(fā)生率4.8%(2/41),其中1例(2.4%)穿刺處血腫，1例(2.4%)封堵器脫落。

式中：｜Q｜是矩陣元素的數(shù)目，等于網(wǎng)絡(luò)劃分的群數(shù)的平方，而

對于某P 中的兩個群α 和β，rαβ表示兩個群中所有可能的連邊數(shù)，lOαβ表示所觀察到的網(wǎng)絡(luò)AO中連接兩個群α 和β 的連邊數(shù)，則根據(jù)Beta函數(shù)積分公式，可以得到鏈路｛vx，vy｝信度的最終結(jié)果

式中：σx是節(jié)點vx所屬群的編號；σy是節(jié)點vy所屬的群的編號，

對于一個只有5個節(jié)點的網(wǎng)絡(luò)，其分塊方式都有77種，遍歷18個節(jié)點所有可能的分塊方式，其計算量是不可接受的．因此結(jié)合統(tǒng)計力學中總體均值的形式，使用大都市算法［18］來抽樣相關(guān)分組更有利于得到鏈路信度的可靠性估計．首先把觀測網(wǎng)絡(luò)（見圖3）中的18個節(jié)點每一個節(jié)點分別看作一組，每一步選擇一個隨機的節(jié)點并試圖把它移動到一個隨機的其他組，計算H（式（5））的變化．如果ΔH≤0，這個移動就被接受，否則，這個移動以exp（－ΔH）的概率被接受繼續(xù)下一步移動，直到所有節(jié)點都移動到同一個組的時候循環(huán)結(jié)束，最終得到18種分塊方式．

根據(jù)式（4），遍歷以上18種分塊方式即可求出網(wǎng)絡(luò)中所有鏈路的信度．

2．3 網(wǎng)絡(luò)重構(gòu)

Guimera和Sales－Pardo設(shè)計了一個簡單的貪婪算法［11，13］：首先將網(wǎng)絡(luò)中所有的邊按照信度排序，然后每次將信度最低的邊刪除，同時連接一條信度最高的邊．此算法過程中，丟失邊和虛假邊的數(shù)目是相等的，這顯然是不真實的．本文改進了貪婪算法，將“刪邊－加邊”的操作分開進行．首先進行“刪邊”，每次將信度最低的一條邊刪除，這一操作僅當網(wǎng)絡(luò)整體的信度增大的時候被接受．如果被拒絕，則對剩余邊中信度最低的邊繼續(xù)進行上述過程，直到連續(xù)5次被拒絕后停止．然后進行“加邊”，每次連接一條信度最高的邊，這一操作也僅當網(wǎng)絡(luò)整體的信度?（式7）增大的時候被接受．如果被拒絕，則對剩余邊中信度最高的邊繼續(xù)進行上述過程，直到連續(xù)5次被拒絕后停止．

根據(jù)改進后的貪婪算法得到全國活羊調(diào)運網(wǎng)絡(luò)缺失鏈路（見表1）和虛假鏈路（見表2），增加丟失鏈路，刪除虛假鏈路就得到了一個新的網(wǎng)絡(luò)，即全國活羊調(diào)運重構(gòu)網(wǎng)絡(luò)A（見圖5）．此重構(gòu)網(wǎng)絡(luò)對于觀測網(wǎng)絡(luò)的可信度?＝（A｜AO）（式7）達到最大值．

表1 缺失鏈路及其信度Tab．1 Missing link and its reliability

表2 虛假鏈路及其信度Tab．2 False link and its reliability

圖5 全國活羊調(diào)運網(wǎng)絡(luò)重構(gòu)圖Fig．5 Reconstructed network graph with national live sheep migration

在以上重構(gòu)網(wǎng)絡(luò)（圖5）中，共有18 個節(jié)點，37條邊．其中，節(jié)點山東的度為13，節(jié)點四川的度為9，節(jié)點吉林的度為6．66．7%的省份有3～4條連邊．節(jié)點浙江的度最小．

由表1 可知，與河南有關(guān)的兩條鏈路（四川－河南、吉林－河南）的信度較高．據(jù)調(diào)查，河南是我國主要的活羊集散地之一，全省有幾十個規(guī)模較大的活羊交易市場，因此他們之間存在活羊調(diào)運的可能性較大．表2 中安徽－山東、貴州－山東這兩條鏈路信度較低，可能因為安徽、貴州也是較大的活羊集散地，且他們與山東的羊養(yǎng)殖模式類似，所以存在活羊調(diào)運的可能性較?。纱丝磥?，預測是符合實際的．

對以上的活羊調(diào)運網(wǎng)絡(luò)重構(gòu)過程進行了5次實驗，5次實驗得到的丟失鏈路與虛假鏈路完全相同．為進一步驗證所得結(jié)果的可靠性，在重構(gòu)網(wǎng)絡(luò)中隨機去掉一些保留路徑，再隨機加上同等數(shù)量的其他路徑，得到了一個構(gòu)造網(wǎng)絡(luò)．利用以上方法，對構(gòu)造網(wǎng)絡(luò)進行網(wǎng)絡(luò)重構(gòu)，結(jié)果準確地預測出了去掉和增加的路徑，還原了重構(gòu)網(wǎng)絡(luò)的面貌．可見，本文得到的活羊調(diào)運重構(gòu)網(wǎng)絡(luò)是比較可靠的．另一方面，根據(jù)市場調(diào)查和電話采訪，山西與內(nèi)蒙古之間確實存在活羊調(diào)運情況，這條鏈路在活羊調(diào)運觀測網(wǎng)絡(luò)中是不存在的，屬于預測到的丟失鏈路．由此可知，本文得到的活羊調(diào)運重構(gòu)網(wǎng)絡(luò)是比較真實的．

3 結(jié)論與應(yīng)用

本文根據(jù)2014年3月全國活羊調(diào)運信息，利用ArcGIS軟件得到全國活羊調(diào)運觀測圖，根據(jù)隨機分塊模型和大都市算法，通過Matlab軟件計算出網(wǎng)絡(luò)中所有可能存在的鏈路的信度，運用改進后的貪婪算法得到觀測網(wǎng)絡(luò)中缺失的15條鏈路和虛假的5條鏈路，最終重構(gòu)了全國活羊調(diào)運網(wǎng)絡(luò)．

本文所得到的活羊調(diào)運重構(gòu)網(wǎng)絡(luò)，共有18個節(jié)點，37條邊．其中，節(jié)點山東的連邊數(shù)最多，其次是四川，吉林．顯然這幾個省份與其他省份的羊群貿(mào)易往來最多，疫情傳播的風險最大．因此在疫病流行時，應(yīng)從這幾個省份開始采取相關(guān)措施，有效地切斷傳播途徑，將疫病控制在一個有限的范圍內(nèi)，減少經(jīng)濟損失．除此之外，在此重構(gòu)網(wǎng)絡(luò)的基礎(chǔ)上，還可以預測每個節(jié)點的感染途徑，感染時間和染病概率，為制定動物疫病的防控措施提供了很好的依據(jù)．

以上活羊調(diào)運重構(gòu)網(wǎng)絡(luò)不僅適用于小反芻獸疫，也為研究其他羊類疫?。ㄈ绮剪斒暇　⒖谔阋叩龋┨峁┝艘罁?jù)．

［1］Sarukkai R R．Link prediction and path analysis using markov chains［J］．Computer Networks，2000，33（1）：377－386．

［2］Zhu J，Hong J，Hughes J G．Using markov chains for link prediction in adaptive web sites［C］．Soft－Ware 2002：Computing in an Imperfect World．Springer Berlin Heidelberg，2002：60－73．

［3］Popescul A，Ungar L H．Statistical relational learning for link prediction［C］．IJCAI Workshop on Learning Statistical Models From Relational Data，2003：81－87．

［4］O’Madadhain J，Hutchins J，Smyth P．Prediction and ranking algorithms for event－based network data［J］．ACM SIGKDD Explorations Newsletter，2005，7（2）：23－30．

［5］Lin D．An information－theoretic definition of similarity［C］．ICML，1998（98）：296－304．

［6］Cannistraci C V，Alanis－Lobato G，Ravasi T．From link－prediction in brain connectomes and protein interactomes to the local－community－paradigm in complex networks［J］．Scientific reports，2013（3）：1－13．

［7］Li F，He J，Huang G，et al．A clustering－based link prediction method in social networks［J］．Procedia Computer Science，2014（29）：432－442．

［8］Liu W，LüL．Link prediction based on local random walk［J］．EPL（Europhysics Letters），2010，89（5）：58007．

［9］Clauset A，Moore C，Newman M E J．Hierarchical structure and the prediction of missing links in networks［J］．Nature，2008，453（7191）：98－101．

［10］Holland P W，Laskey K B，Leinhardt S．Stochastic blockmodels：First steps［J］．Social networks，1983，5（2）：109－137．

［11］GuimeràR，Sales－Pardo M．Missing and spurious interactions and the reconstruction of complex networks［J］．Proceedings of the National Academy of Sciences，2009，106（52）：22073－22078．

［12］Zhang X，Wang X，Zhao C，et al．Degree－corrected stochastic block models and reliability in networks［J］．Physica A：Statistical Mechanics and its Applications，2014（393）：553－559．

［13］呂琳媛，周濤．鏈路預測［M］．北京：高等教育出版社，2013．

［14］Karrer B，Newman M E J．Stochastic blockmodels and community structure in networks［J］．Physical Review E，2011，83（1）：016107．

［15］Ding J，Jiao L，Wu J，et al．Prediction of missing links based on multi－resolution community division［J］．Physica A：Statistical Mechanics and its Applications，2014．

［16］White H C，Boorman S A，Breiger R L．Social structure from multiple networks．I．Blockmodels of roles and positions［J］．American journal of sociology，1976：730－780．

［17］Anderson C J，Wasserman S，F(xiàn)aust K．Building stochastic blockmodels［J］．Social networks，1992，14（1）：137－161．

［18］Huang K．Statistical Mechanics［M］．New York：John Wiley ＆Sons，1987．