保护缠结网中的基本连接

 
现在是冬天了。正如任何常旅客所知，冬天可能意味着机场天气延迟。在主要的机场枢纽明尼阿波利斯的一场暴风雪，可能很快导致温和的迈阿密或多雾的伦敦的航班延误。
为了最大程度地减少干扰，空中交通管制分析师会优先考虑恢复工作。但是，由于变量太多，他们很难提出自信的建议。但这只是计算机可以编程解决的数据驱动型问题。问题是时间。当前的方法还不够快，无法实时提供解决方案。
现在，由PNNL的计算机科学家领导的研究团队开发了一种名为Ripples的新图形工具，该工具可以在一台超级计算机上不到一分钟的时间解决复杂的图形分析问题，例如机场中断分析。最好的可比工具可能需要在常规计算机上用一整天才能解决相同的问题。有一天，这一计算里程碑可以对实时决策者可用的网络影响(例如空中交通中断)进行分析。
负责机场建模工作的PNNL计算机科学家Arun Sathanur说：“我们的方法利用了严格的社交网络分析方法，正式称为影响力最大化问题，并将其扩展到可在高效并行计算平台上运行。” “这些模型擅长查找有影响力的实体，分析连接的影响，并指出中断在何处具有最大的级联连锁效应。”
该研究团队还包括东北大学和交通运输部Volpe国家运输系统中心的研究人员，于2019年11月在IEEE国土安全技术国际研讨会上介绍了他们的机场网络分析。
他们利用运输部联邦航空管理局提供的公开数据，将机场分为影响力类别，并显示哪些机场最有影响力，以及最重要的“影响者”名单在整个日历年中如何变化。
这些发现提供了原理证明，最终可以用于管理机场网络中断。
PNNL的运营研究科学家，由Sathanur领导的机场建模工作的首席研究员Sam Chatterjee说：“涟漪图为主动的战略计划和运营提供了强大的工具，并且在网络运输基础设施系统中具有广泛的适用性。
在日益拥挤的世界中，能够在意外系统故障或网络安全漏洞后迅速恢复服务将是一项巨大的好处。这是网络分析的领域，最初是为了了解社交网络中的人们如何相互连接而开发的。越来越多的网络分析和可视化分析被用于做未经授权的访问计算机网络，检测癌性肿瘤中蛋白质之间的关系以及解决诸如机场网络拥挤问题之类的交通拥挤难题。
但是，为了使分析结果值得信赖，必须执行一系列计算以计算影响范围。 PNNL的高级科学家，ExaGraph的主要研究人员Mahantesh Halappanavar说，这实际上是一个计算难题。ExaGraph是由美国能源部(DOE)的Exascale计算项目资助的应用程序协同设计中心。
他说：“对于许多现实情况，并不总是很清楚如何为网络中各个实体之间的连接强度分配准确的权重。” “因此，我们使用多种设置重复进行仿真，以提高计算出的解决方案的可信度。”即使权重众所周知，该方法仍然依赖于执行大量模拟来识别有影响力的实体。
他们通过运行影响级联模型的这些重复模拟来估计任何组中最重要的影响者，直到得出准确的估计为止。这种方法难以在中等规模的网络中甚至找到一小部分重要的影响者，而且要花几天的时间才能完成。
这就是为什么涟漪在解决速度上如此显着提高的原因。
华盛顿州立大学电气工程与计算机科学学院Ripples和波音公司计算机科学百年教席的共同开发者Ananth Kalyanaraman说：“在大型网络中最有影响力的实体上进行分选可能很快变得很耗时。”铂尔曼。 “涟漪图及其较新的变体cuRipples使用一种利用大量计算能力的策略，包括现代图形处理单元中的计算能力，以在搜索过程中寻找“下一个最具影响力的”实体。”

 
可靠的答案
此外，涟漪图基于所谓的“近似保证”解决方案，它使用户可以权衡解决方案的质量和时间来计算解决方案，同时还具有判断解决方案质量的能力计算的。基于PNNL和WSU的团队密切合作，以在由DOE管理的最快的超级计算机上有效地缩放Ripples工具。
这种策略使Ripples可以有效地收敛于更高质量的解决方案，其速度比以前为并行系统设计的方法要快790倍。
Ripples的首席开发人员PNNL的Marco Minutoli说：“如果我们能在一分钟内融合到一个解决方案上，我们就可以开始将其用作交互式工具。” “我们可以实时地提出和回答新问题。”
PNNL科学家已经在这样做。他们已经开始使用涟漪图处理大量数据，并在以下方面找到最重要的影响者：
识别土壤微生物群落对水分变化的响应中最重要的物种;
跟踪传染病的传播并提出控制策略以控制流行病的传播;和
确定空气样本中最重要的成分，将其包含在详细的气候模型中，以研究其对空气污染的影响。
Minutoli说：“据我们所知，这是大规模并行化影响最大化操作的第一步。”
研究团队已将该方法提供给Github上的研究社区。他们正在计划下一个重大改进(cuRipples)，它将优化世界上最快的超级计算机Summit上的方法。