基于鏈路預(yù)測的全國活羊調(diào)運(yùn)網(wǎng)絡(luò)重構(gòu)

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

2．1 隨機(jī)分塊模型

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

（P，Q）．

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

圖4 隨機(jī)分塊模型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 中的兩個(gè)群α 和β，rαβ表示兩個(gè)群中所有可能的連邊數(shù)，lOαβ表示所觀察到的網(wǎng)絡(luò)AO中連接兩個(gè)群α 和β 的連邊數(shù)，則根據(jù)Beta函數(shù)積分公式，可以得到鏈路｛vx，vy｝信度的最終結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以上活羊調(diào)運(yùn)重構(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］呂琳媛，周濤．鏈路預(yù)測［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．