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

有兴趣在其他冲突和长期数据集上进一步验证这一结论。时间调整模型一开始的结果相对不准确，但平均误差很快就会下降，正如预期的那样，因为这是一个时间敏感的模型。然而，忽略前100天，考虑到hEi，时间调整后的模型给出的平均值相对较低，这表明我们成功地消除了每个时间戳结束时福吉难民营人口的重新缩放，同时仍然产生了一个相对准确的模型。这一点很重要，因为取消重新调整规模的过程会产生更透明的模型，减少对难民署数据的依赖。马尔可夫链模型中的一个关键参数是距离阈值D，它决定了难民一天可以旅行的最大距离。该参数也是一些不确定性的来源，因为我们假设的选择D=120（以公里为单位）似乎相当于50 100 150 200 000 20 000 40 000 60 000 80 000 100 000 000最大行程阈值D在t=396时的人口图4：随着最大距离阈值D的变化，马尔科夫链：营地调整模型预测的数据集最终进入时（t=396）每个营地的人口。每个难民营的预测由不同的实线表示，虚线表示难民署数据中报告的人口，如【8】所示。值得注意的是，随着D的变化，图中的边数也会发生变化，如第2节所述。合理的话，根据道路质量、气候和交通选择，可以想象其变化幅度适中。此外，对于D变化的Camp调整模型，图中的边数变化如第2节所述。因此，谨慎的做法是探索varingd如何影响难民的后期分布。

我们在图4中显示了t=396（数据集中的最终条目）时，不同D对营地人口的影响，实线给出了马尔可夫链：营地调整模型的预测，虚线表示难民署数据中报告的值。观察D 100然后，对最晚时间数据的影响变得稍微差一些，然而，对于D>100，结果对D的变化相对不敏感，这提供了一些证据，我们不需要担心最大行程距离的精确值或可能的局部变化。6讨论：与基于代理的模型的比较接下来，我们将讨论我们的马尔可夫链模型与以前使用基于代理的模型的方法之间的差异，具体参考Suleimenova、Bell和Groen[8]提出的一个称为逃离的最先进示例。我们将简要总结Fleed的主要组成部分，然后将我们的结果与运行Fleed（公开提供）获得的结果进行比较。Fleed【8】实现了一种截然不同的方法，称为基于代理的建模【13】。基于代理的模型由一系列固定状态和一组代理组成。Individualagents根据系统规则在这些状态之间进行转换，在每个整数时间戳更新其当前状态。在建模迁移时，一种常见的方法是定义一个包含感兴趣区域的地理信息的加权图，并引入一个代理来表示该区域的每个个体。然后，这些代理根据一些预先定义的算法在图的顶点之间迁移。

这一方法已在灾害驱动的移民[34]、叙利亚持续冲突[35]和布隆迪、马里和中非共和国冲突[8]等领域得到了充分研究和应用。正如在我们的马尔可夫链模型中一样，逃离[8]由一个存储地理信息的图和一个难民用来在图中的城市之间移动的预先指定的算法组成。我们在前面提到，我们从FREAME导出了马尔可夫链模型中的平面图（图1b）。同时，他们基于代理的模型与我们的马尔可夫链模型明显不同，因为逃离将模拟中的每个难民视为一个完全独立的实体，做出独立的选择。虽然我们根据国家间转移的一般概率对难民流动进行建模，但fleed在每个时间段内对系统中的所有代理进行迭代，并为每个代理模拟其通过各个城市的预期移动。我们之前注意到，我们用于正确初始化人口向量的启发式方法。在任何给定的时间戳上，都是从Fleed的启发式方法中派生出来的，用于在模拟的每一天生成新代理，添加到系统中的新代理数是使用有关难民人数的真实数据计算的。这是可以接受的，因为逃离的目的是预测难民在网络上的最终分布，而不是流离失所的难民的实际人数，因此，在每个时间戳结束时都会对分布进行缩放，以确保逃离难民营中的难民总数与UNHCRdata的相应总数相匹配，我们在三个马尔可夫链模型中使用相同的重缩放。尽管FREAND和我们的马尔可夫链模型有一些相似之处，但算法的不同导致了显著不同的结果。现在，我们比较了营地人口的演变和等式中定义的ARD度量。

（11） -（13）定量比较逃逸的马尔可夫链模型。图5类似于图2，但相反，图5显示了每个营地的人口变化，如FLUE（与[8]中给出的结果相匹配）预测的，与我们在初始图（使用与[8]相同的图）和营地调整图（图1c）上实现的马尔可夫链模型所示。此外，在图6中，我们将总ARD显示为图5中所示三个模型的时间戳函数，这为每个模型的相对独立性提供了定量评估。值得注意的是，到模拟结束时，五个模型中的每一个都或多或少地收敛到一个常量值，而Fleed的ARD总量最高。表2简要地描述了这些趋势，其中显示了每个模型的所有时间平均ARD hEi和清洁平均ARD hEi和hEi。初始图表Camp调整后的FleehEi 0.41 0.22 0.29hEi0.38 0.21 0.27hEi0.37 0.21 0.28表2：各型号的所有时间平均ARD hEi和清洁平均ARD hEi和hEi。营地调整模型和逃离模型显示，随着时间的推移，ARD平均值相对稳定，约为0.21和0.28，而其他模型需要更长的时间才能收敛到较低的ARD值。特别要注意的是，就难民模型的主要焦点——长期预测能力而言，马尔可夫链：营地调整模型优于bothFlee和马尔可夫链：初始图。

营地调整后的模型的值为hEifor，约为Fleed的76%，这意味着长期误差减少了24%。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天人口--  -  图5：与图2类似，但这里我们将我们的最佳模型马尔可夫链：Campadjusted与SBG的逃逸模型[8]以及马尔可夫链：初始图进行比较。注：逃离和马尔可夫链：初始图使用相同的图，图1b，而营地调整模型使用图1c的图。50 100 150 200 250 300 350 4000.00.20.40.60.8DaysTotal ARD图6：基于代理的模型“逃离”的总平均相对差异（ARD）与应用于图2b图形的马尔可夫链模型以及应用于图2c中营地调整图的马尔可夫链模型的比较。在[8]中，为了量化他们的结果，作者使用吉文代的营式ARD Ei（t）作为布隆迪危机建模成功的主要衡量标准。

在这里，我们将重点放在总ARD上，我们认为总ARD是整体建模精度的更明确指标，但附录中提供了每个模型的营地ARD，以提供更直接的比较，从单个营地ARD的整体来看，可以得出每个模型优度的类似结论。因此，我们得出结论，与逃离相比，马尔可夫链模型可以适度改善拟合优度，此外，马尔可夫链在运行时和代码长度方面比基于代理的方法产生了更有效的模拟工具。就代码长度而言，构建复杂的基于代理的模型（如Fleeoperate）所需的组件分布在多个文件夹、数十个文件和数千行代码中【8】。与此相反，我们的每个马尔可夫链模型都包含在一个文件中，并且不到500行代码。虽然程序长度不能衡量效率或适用性，但代码的维护成本和出现错误的可能性与程序长度直接相关。要量化基于代理的逃离的复杂性，请考虑一个运行t个时间步的模型中感兴趣区域内的总共R个难民和NCITE。在每个时间戳，Fleee都会迭代系统中的所有代理以更新其状态，因为基于代理的模型会分别显示每个代理。此外，在决定迁移到哪个城市之前，每个代理都会遍历n个城市的列表，因此每个R代理在每个时间戳都需要O（n）个时间来更新，导致总时间复杂度至少为O（nRt）。分析马尔可夫链模型的总体时间复杂度稍微困难一些。

如果感兴趣区域内有n个城市，那么我们在第2节中注意到，我们使用Floyd War的图形修改算法将在O（n）时间内运行，然而，这些算法仅在模拟开始时运行，以建立图形。同时，我们注意到第3节，我们计算了O（nD）时间内的跃迁概率pji。一旦转移概率计算了一次，就不需要重新计算，因为我们在多个时间戳上重复使用相同的精确矩阵A（t），除非对图中的城市进行了根本性的更改，例如，一个中立城市转变为冲突地点，改变了中间概率，从而改变了系统的转移概率。这些顶点更新的数量与顶点数量n的数量相当，因为中立城市可以成为冲突点，但相反的情况要难得多。因此，计算跃迁概率大约需要O（n）·O（nD）=O（nD）时间。最后，在每个时间戳，Markovchain只执行n×n矩阵与n维向量的简单乘法，这只需要O（n）个操作，因此对系统的更新总共包含O（nt）个时间。因此，我们估计马尔可夫链模型的时间复杂度为O（n+nD+nt）。就布隆迪而言，R~ 10难民，t=396~ 10天，有n个~ 10个顶点，而D~ 因此，逃逸以O（nRt）=O（10）操作运行，而马尔可夫链模型则是O（n+nD+nt）=O（10）操作，因为nD项支配渐近。实际上，在标准台式机或笔记本电脑上执行这些不同的模拟时，运行时的这种数量级差异是显而易见的。

一般来说，迁移模型通常只涉及重要的城市中心，因此n的值相当小，而R的值可能会非常大，这使得基于代理的模型比马尔可夫链的实现更不可行。7结论性意见在这项工作中，我们基于关于难民流动与当地地理之间联系的新启发法，实施了难民危机中难民迁移的马尔可夫链模型。通过将我们的模型应用于布隆迪难民危机，并与该危机的现有基于代理的模型进行比较，我们得出结论，我们使用马尔可夫链的方法更有效，减少了基于代理的建模中不必要的复杂性，并显示出长期预测误差减少了24%。基于代理的逃逸模型在[8]中针对三个不同的冲突（布隆迪、马里和中非共和国）进行了明确验证，但为简洁起见，我们在此仅将分析局限于布隆迪冲突。然而，我们顺便强调，这里开发的马尔可夫链模型在应用于[8]中所述马里和中非共和国的数据和图表时，与其他两个冲突提供了类似的良好效果（与逃跑相比）。应当指出，收集难民营难民登记数据是一项具有挑战性的任务，难民署的数据与实际难民营人口之间可能存在很大差异，这是非常可行的。此外，离开难民营前往新目的地的难民，比如说另一个难民营或中立城市的亲戚住宅，可能不会优先考虑注销登记，因此数据不能准确反映难民营的离开情况。

我们试图通过在图2和图5中加入10%的误差幅度来解释数据中的这些潜在差异，然而这是一个相当直截了当的启发，更好地理解数据中的固有错误是非常可取的。将我们的模型应用于更高质量和更大的数据集，将使我们能够更好地重新定义这里介绍的马尔可夫链模型。由于最近难民危机的增加，有许多原因可以说明为什么改进难民模式会有用。准确的难民模型将使我们能够预测将抵达特定地区或城市的难民人数、他们将抵达的日期，以及这些难民在多个地区的分布情况，提前几天甚至几周，提供有关移民原因的良好信息。这将是非常有益的，因为准确的建模可以让难民和政府组织确定在哪里最好地分配援助资源，以最大限度地发挥影响和效率。预测模型还将允许城市和地区采取适当的措施来容纳大量寻求庇护的人，这通常会导致严重的破坏性情况。事实上，随着全球气候变化的开始、不平等的加剧和全球稳定的下降，流离失所者的数量很可能在未来显著增加[36]。因此，越来越需要更好的模拟，在这项工作中，我们提倡采用基于马尔可夫链的模型，以便更准确和有效地建模这些危机。致谢我们感谢威廉·琼斯（William Jones）、劳拉·沙波斯尼克（Laura Schaposnik），尤其是德里克·格罗恩（Derek Groen）进行了宝贵的讨论，以及坦尼亚·霍瓦诺娃（Tanya Khovanova）和克劳德·艾彻（Claude Eicher）对草案的评论。

JU感谢西蒙斯几何和物理中心（项目：中国系统的几何和物理）和牛津新学院的热情款待和支持。这项工作是作为麻省理工学院PRIMES项目的一部分完成的。附录：每个难民营的ARD在本附录中，我们将每个难民营的ARD作为时间戳的函数。ARD fora难民营很好地衡量了将单个难民营建模为难民总人口比例时存在的误差。请注意，图3和图6显示了每个模型每天的总ARD，基本上是图7中五个图表的“和”。图7显示了五个模型的五个难民营中的ARDs，这里开发的四个马尔可夫链模型，以及SBG的逃跑模型[8]。观察到，在Lusenda和Nakivale这两个阵营中，所有五个模型都表现很好，导致几乎无法区分的长期ARD约为零。然而，这一趋势在其他三个阵营中并不存在。50 100 150 200 250 300 350 4000.00.10.20.30.40.50.6天50 100 150 200 250 300 350 4000.000.050.100.150.200.25天50 100 150 200 250 300 350 4000.000.050.100.150.200.25天50 100 150 200 250 300 350 4000.000.050.100.150.200.25天50 100 150 200 250 300 350 4000.000.050.100.150.200.25天--  -  --图7：每个营地每个模型的平均相对差异（ARD）。在Nduta中，使用第2节中我们的图形修改算法的所有三个模型的性能都明显优于FREAME和马尔可夫链模型：初始图，这两个模型都优于未修改的图。在尼亚鲁古苏，逃跑最初会产生相对准确的结果，但四个马尔可夫链模型最终会收敛到更准确的预测。