难民迁移数据的马尔可夫链模型

（7） 因此，在每个连续时间戳开始时，顶点总体继承自上一个时间戳所有操作结束时的最终总体。这是迭代进化系统的传统马尔科夫过程。更具体地说，如果一个中立城市成为一个营地或营地，由于一个城市的形式不是固定的，而是在时间戳上间歇性地演变，这是一个非齐次马尔可夫链[23]。上述马尔可夫系统有利于建模移民，因为它允许仅根据转移概率Pji（t）建立一个相对紧凑的模型，而对中间概率和一天内跨越多个城市的难民的担忧是无关紧要的，因为它们已经被封装在转移概率中。因此，实现随机矩阵模型的主要困难在于计算Pji（t）的值。我们在两个时间戳之间进化顶点种群的算法形成了一组顺序操作，因此可以将计算转移概率的问题分解为更小的部分。这允许应用动态编程技术，这本质上是一种有效的递归形式。为了实现这一点，我们引入了一个新的位置特定的n元组gi（d，t）={s（d，t），s（d，t），…，sn（d，t）}与顶点vi关联。女孩的元素sj（d，t）表示难民在时间戳t结束时到达顶点vja的概率，这取决于难民在当前时间戳t期间之前旅行的距离d，因此他们目前居住在城市vi，如果是d≥ D、 那么，难民就不能再前往不同的城市，所以在时间戳的剩余时间里，他们将留在城市VII。因此，G（d，t）d≥D={0，0，…，0，1，0，…，0}。（8） 其中，单个1出现在向量的第i个条目中。

如果d<d，则每个1≤ j≤ n、 因此，以中等概率Iji（t）从vito Vjg移动；在这次迁移结束时，Therefegee现在在城市vjand已经迁移了d+wi j的总距离。此时，难民最终目的地的概率分布为g（j，d+wi j）。它遵循thatgi（d，t）d<d=∑1.≤ j≤nIji（t）g（j，d+wi j）。（9） 注意，当vi，vjare不相邻时，我们的和包含一项Iji（t）g（j，d+wi j）=0·g（j，∞);我们通过了公约g（j，∞) = {0，0，…，0}对于所有j，确保表达式得到充分定义，尽管乘以0意味着g（j，∞) 与此无关。因此，式（9）根据公式gj（d，t）的表达式得出了gi（d，t）的递归公式，其中d=d+wi j>d。因此，我们可以通过首先计算gi（d，t）形式的所有向量来有效地计算所有向量gi（d，t- 1，t）并存储结果，然后计算gi（D）形式的所有向量- 2，t），等等；等式（8）处理术语gi（d，t）和d≥ 发生在递归中的。根据形式Iji（t）gj（t）（d+wi j，t）的n个项计算每个gi（d，t）需要O（n）个时间：它本质上是对形式gj（d+wi j，t）的n个向量求和，每个向量都已经计算过并且是n维的。因此，该算法计算1的gi（d，t）形式的nDvectors≤ 我≤ n、 d<d in nD·O（n）=O（nD）时间。转移概率Pji（t）相当于时间戳t期间当前位于城市的难民，其已行驶d=0距离，到达时间戳t末端的城市vjbyth的概率。

因此，Pji（t）是gi（0，t）中所有1的第j个条目≤ i、 j≤ n、 所以计算所有的gi（d，t）项可以计算所有的跃迁概率Pji（t）。过渡概率随时间变化是恒定的，除非中间概率iji（t）发生变化，只有当一个城市成为难民营或冲突地点时才会发生这种变化，虽然这种情况在我们的模型中发生，但这种情况并不常见。因此，上述程序在每次难民危机期间只应运行几次。从中间概率计算转移概率完成了我们模型的算法方面。4应用：布隆迪危机建模我们利用了布隆迪危机的数据，该数据来自以前的危机模型，称为逃离因苏莱梅诺娃·贝尔·格罗恩（SBG）[8]，而后者又从联合国难民事务高级专员（UNHCR）处获得数据。SBG[8]提取的难民署数据从2015年5月至2016年6月运行，总计396天，因此模型中的时间戳范围为0≤ t型≤ 在布隆迪危机中，有五个活跃的难民营，每个难民营都由联合国在尼亚鲁古苏、恩杜塔、纳基瓦尔、马哈马和卢森达建立。图1a显示了布隆迪境内和周边的30个主要城市，这些城市在《逃离》中进行了建模，图1b显示了用于对SBG中构建和使用的系统进行建模的图表【8】。图1显示了一个非平面图，表示连接相关位置的其他路线，我们通过向图形GPin面板（b）添加更多边来构建该图，如第3节所述。在SBG【8】中，作者假设在viareRi城市中剩余的概率Rio=0 Vis为冲突现场0.7 Vis为中立现场0.999 Vis为营地现场。（10） 这些估计似乎是合理的，所以我们在模型中也保留了它们。

我们还从SBG的逃逸模型[8]中列出了布隆迪境内的主要武装冲突，并在适当的时间戳将相应的地点转换为冲突地点。第一次此类冲突发生在2015年5月1日，我们将其设定为模型的开始日期t=0。SBG【8】估计马班达鲁塔那马坎巴马卡布科卡鲁奇米吉·穆因·加吉斯鲁坎库佐·杜塔加·霍马尼亚·鲁古·卡贡加（b）的Bujumburabubanzacibitokemuramvyakayanzamwarorumongelusendabukinanananananakivalekirundogitegakabarorengoziburambibururiricum社区。Bujumburabubanzacibitokemuramvayakayanzamwarorumongerutanamakambakaruziruyigigisurucankuzomuyingakirundongozigashohonyarusumakebukocommunite of mabandakagungalusendedabukinanyanakabarorebururigitteganakvalendutamahama（c）。图1：（a）。覆盖在布隆迪及其周边地区地图上的位置标签（来自GoogleMaps[33]）。注意，Nakivale位于图中更北的位置。（b） 。一个平面图gp，表示连接与布隆迪难民危机相关地点的主要道路，如[8]所用。（c） 。表示连接相关位置的附加路线的非平面图，通过向图形GPin面板（b）添加附加边构建，如第3节所述。难民一天最多旅行200公里。可以说，这过于乐观了，因为大多数难民步行旅行[8]，所以我们将每日距离阈值设置为D=120（单位为公里），相当于8公里/小时的15小时。接下来，我们初始化人口向量B（t），以匹配布隆迪地区的难民人数；我们再次从[8]获得了该数据，他们从UNHCR RefugeCamp注册数据中检索到该数据。SBG【8】指出，预测武装冲突造成的难民人数非常困难，但可以通过卫星图像等多种手段获得粗略估计【6】。

因此，SBG【8】的目标不是预测危机导致的难民数量，而是预测这些难民的分布情况，考虑到他们的总数；我们的模型也关注这一目标。我们将在第5节中返回，直接将我们的结果与SBG的逃离模型的结果进行比较【8】。由于B（t+1）=A（t）B（t）代表从时间t开始在时间t+1的预期难民分布，因此B（t+1）中的难民总数与B（t）中的难民总数相同。这意味着，难民人数的任何增加都不会反映在矩阵乘法中，因此必须通过额外的过程来执行。具体而言，根据联合国难民事务高级专员办事处（UNHCR），我们用U（t）表示t时布隆迪难民营中的难民人数。在每个时间戳t之后，总体差异U（t+1）- 计算时间戳t和时间戳t+1之间的U（t），然后计算额外的U（t+1）-U（t）重新聚集通过将其分布到模型中的冲突点中随机添加到人口向量B（t），概率与冲突点的人口成比例。这确保了模型始终包含准确的难民人数。[8]的补充材料对逃逸进行了敏感性测试，结果表明，在最大距离D和停留概率Ri的适度变化下，结果是稳健的。由于这种添加难民的机制，在时间戳t之后，模型中的难民总人数与t天后难民署难民营中的难民总人数相同。因此，该模型持续低估了图形，因此低估了每个难民营中的难民人数，因为模型中的许多难民仍在设法集中。

在模型中，为了解释难民的产生和他们到达难民营之间的延迟，当提取每个难民营中的难民人口时，我们按照一个常数因子向上缩放每个难民营中的难民人口，以便难民营中的总难民人数与难民署每天的数据相匹配。这种重新缩放发生在我们在下面和fleed中概述的四个马尔可夫链模型中。由于我们的既定目标是根据难民总数预测难民在难民营中的分布，因此这一救援并不重要。然而，由于这种缩放在某种程度上是临时的，我们在下面概述的马尔可夫链变体之一旨在消除这种重新缩放的需要。现在，我们将第2节和第3节中概述的建模算法应用于最近因内战导致的布隆迪难民危机，重点是2015-2016年期间难民营登记的一组数据。我们使用马尔可夫链运行四个不同的模型，每个模型都是基于第2节和第3节中概述的原则，如下所述：马尔可夫链：初始图。根据Bing地图上布隆迪主要道路的分析，我们将马尔可夫链方法应用于【8】中构建的平面图，见图1b。马尔可夫链：图形调整。此外，我们还将马尔可夫链方法应用于修改后的图G，该图是我们根据第2节中的程序（如图1c所示）从GPG中得出的，我们称之为图调整模型。马尔可夫链：营地调整。在我们的模型中，长期迁移到难民营的概率被系统地分配为较小的中间概率。这种启发式对于向中立城市的迁移是有意义的，因为难民更喜欢进行一系列较短的迁移，而不是一次较长的迁移[2]，但这种推理对于难民营来说是错误的，因为他们是难民的最终目的地，而不是中间位置。

此外，难民有各种各样的动机选择遥远的难民营，例如感知到的安全和远离危险。为了实现这一观察结果，我们创建了一个额外的图形G，绘制代表向难民营长距离移动的边ei jin G，并用权重wig=D重新分配这些边，以便向难民营长距离移动的机会与向难民营中等移动的机会相同。我们称这种变化为营地调整模型。马尔可夫链：时间调整。现在，我们提出了第四个马尔可夫链模型，我们称之为时间调整模型，它消除了在每个时间戳结束时进行总体重新缩放以匹配总难民人口的需要。用T表示模型中难民从冲突地点前往难民营所需的平均时间。然后，如果在时间戳t时模型中有U（t+t）难民，则大多数难民应在t天内到达Refugee难民营，因此在时间戳t+t时，居住在模型内难民营中的难民人数约为U（t+t）。我们可以利用这一观察结果，在模型T中引入适当数量的误差，从而消除在每个时间戳结束时重新缩放的需要。具体而言，在时间戳t=0时，我们引入U（t）难民而不是U（1）难民，并且在每个时间戳t的末尾，我们添加一个额外的U（t+t+1）-U（t+t）难民而非U（t+1）-U（t）难民。还需要计算T，即难民从冲突地点到阿雷福吉难民营的平均旅行时间，这可以通过运行模拟来找到，其中冲突地点的所有人口在时间戳T=0时成为难民，然后让N（δ）表示δ天后1天的难民营总人口≤ δ ≤ 对于一些适当大的常数M。

ThenN（δ+1）- N（i）难民需要δ+1天才能到达，因此平均旅行时间isT=NM-1.∑δ=0（δ+1）（N（δ+1）- N（δ））=N锰（M）-N（米- 1） +N（M- 2） +···+N（0）.对于M=100，我们发现T=16，因此这是我们在时间调整模型中使用的值。5结果：布隆迪危机建模我们现在将展示上述布隆迪模型的结果。图2显示了不同的图表，这些图表是主要地区难民营中难民人数随时间变化的模型结果。每个图表代表与布隆迪危机相关的五个不同难民营中的一个，在每个图表中，我们根据时间戳（天）绘制给定难民营中的难民人口。在每个图中，我们显示了五条曲线：四条实线对应于第4节中概述的四个马尔可夫链模型，虚线是联合国难民署营地人口数据，阴影区域表示数据有10%的误差。仅从这些人口图就很难确定每个模型在预测五个难民营中的难民人口方面的有效性。为了量化福利的好处，我们现在引入指标来衡量给定难民模型的成功与否。用X表示相关难民营的集合{Nyarugusu、Nduta、Nakivale、Mahama、Lusenda}。对于每个campxi∈ 十、 假设Ni（t）是给定模型中时间戳t处该营地的人口，根据难民署的数据，πi（t）是第t天该营地的人口。注意，U（t）精确地表示每个营地的π之和：∑xi∈Xπi（t）=U（t）。我们考虑的第一个衡量标准是给定的夏令营第t天的平均相对差异（ARD），由EI（t）=Ni（t）给出- πi（t）| U（t）。（11） 给定时间戳t上的总ARD是所有campsE（t）的ARD值之和=∑xi∈XEi（t）。

（12） 此外，考虑给定模型的时间平均ARD也很有用，方法是平均某一时期内的所有每日ARD值。特别是，我们考虑数据覆盖的整个时期内的平均ARDhEi（高达t=396）hEi=∑j=0Ej=（E（0）+E（1）+····+E（395））。(13)0 100 200 300 400020 00040 00060 00080 000100 000天人口0 100 200 300 400010 000 20 000 30 000 40 000 50 000天人口0 100 200 300 4000500010 00015 00020 00025 00030 000天人口0 100 200 300 400010 000 20 000 30 000 40 000 50 000 60 000天人口0 100 200 300 4000500010 00015 00020 00025 000天人口----图2：五个主要难民营中与布隆迪难民危机相关的人口增长曲线图，由我们的每个模型预测，作为时间戳（天）的函数。每个图中的四条实线对应于第4节中概述的四个马尔可夫链模型，灰线是[8]中的难民署营地数据，阴影表示数据中有10%的误差。50 100 150 200 250 300 350 4000.00.20.40.60.8天总ARD图3：等式中定义的总平均相对差（ARD）。（11） &（12），每个马尔可夫链模型的每个时间戳（天）。可以看出，重新定义的图表改善了数据的拟合度。彩色曲线与图2中的曲线相匹配。图3显示了每个模型的总ARD E（t）随时间的变化。这提供了一个很好的比较工具来评估模型与数据的匹配程度。

观察到，使用“初始图”（图1b）的马尔可夫链模型始终具有相对较高的误差幅度，而图调整模型和camp调整模型（图1c）得到了显著改进。值得注意的是，在每个模型的最初几天和实际的引用危机中，都可能存在大量噪音，因此我们预计随着注册实践的改进和营地的情况变得更加稳定，数据的质量会随着时间的推移而提高。为了更好地分析模型的长期准确性，我们还考虑了平均ARD，忽略了数据的最早周期，因为这可能提供了更可靠的“拟合优度”度量。具体而言，我们称平均ARD忽略了前z天（从t=0开始计算）的z天清洁平均ARD，并用hEizwithhEiz表示≡396- z∑j=零。（14） 我们将考虑30天和100天清洁平均ARD，表示为hEi和hEi，第4节四个马尔可夫链模型的值如表1所示。初始图形Camp调整后的图形调整后的时间调整后的hEi 0.41 0.22 0.32 0.37HEI 0.38 0.21 0.28 0.34HEI 0.37 0.21 0.24 0.28表1：各型号的所有时间平均ARD hEi和清洁平均ARDs hEi和hEi。从表1的统计数据中，我们可以对我们的模型得出一些一般性结论。首先，在三个数值度量hEi、hEi和hEi中，Camp调整模型的平均ARD均低于其他模型。此外，结果清楚地证明了第2节中介绍的地理调整的优点，CampAdjusted和Graph Adjusted模型产生的长期平均ARDs最低。与代表主要道路系统的图形相比，amp-Adjusted和Graph-Adjusted模型与数据的匹配度有所提高，这可能表明难民在越野行驶，或者在Bing或Google地图上没有详细记录的次要道路上行驶。