如何以最小代价破坏系统结构？一套基于机器学习的方法

文章图片
导语
复杂系统的结构连通性会极大影响其功能，对于规模巨大的系统，如何确定一组最小规模的节点，使得其被移除后系统几乎崩溃？这一问题也被称为网络拆解问题，备受研究者的关注。近日，发表在NatureCommunications上的一篇论文“复杂系统的机器学习拆解和瓦解预警信号” ，提出了一种基于机器学习的框架，能够有效评估节点属于拆解最小节点组的概率，该框架同时提供了一种量化系统风险和实现系统崩溃预警的方法。
「网络科学·集智课堂」迎来全新升级，我们邀请陈关荣、樊瑛、周进、李翔、张江、闫小勇、刘宗华、石川、虞文武、赵海兴、史定华等网络科学专家作为导师，以「复杂系统的数学建模与应用」为主题展开课程。课程自10月16日持续至12月25日，学员可加入400人+的集智网络科学交流社区，详情见文末。
研究领域：网络拆解问题，深度学习，可解释性，系统崩溃预警

文章图片
论文题目：
Machinelearningdismantlingandearly-warningsignalsofdisintegrationincomplexsystems
论文地址：
【如何以最小代价破坏系统结构？一套基于机器学习的方法】https://www.nature.com/articles/s41467-021-25485-8
1.如何以最小代价最大程度地破坏系统结构？
现实生活中的复杂系统的结构和动力学可以通过由点边构成的复杂网络而有效表征，例如常见的基础设施网络、社交网络、蛋白交互网络等。网络的结构拓扑会极大地影响系统的运行，找到对网络结构影响最大的节点加以破坏，能够以最小的代价最大程度地破坏系统的结构与功能。
例如，图1展示了巴西贪腐网络的拆解过程，网络中的节点表示贪腐案件涉及到的人，连边表示两个人至少一次出现在同一案件中，通过制定有效的网络拆解方案，只需突破少量个体，即可快速破坏整个贪腐体系。而另一方面，若该网络表征的是社会正常运行赖以生存的电网、水网等基础设施系统，则拆解方案中的节点将成为维持系统功能的重点保护对象。
此类拆解方案的制定问题通常被称为网络拆解问题（或网络瓦解问题）。在众多网络结构特性的评价中，研究者最常利用网络最大规模连通集团中的节点数作为网络结构连通性的评价标准。因此，网络拆解问题受到广泛认可的严格定义是：如何确定一个最小规模的节点集合，使得这些节点被移除后网络破碎化为众多很小的连通集团。图1中的(b)(c)相同颜色的节点位于同一连通集团，而白色节点群表示最大连通集团。该问题本质上是一个NP-hard问题，问题的难度随着网络规模的增加而急剧增长，在之前的研究中，研究者通常尝试运用渗流理论和图论等知识，通过设计启发式规则来获取问题的近似最优解。

文章图片
图1：巴西贪腐网络的拆解过程
2.训练一个机器，学习拓扑机制以拆解网络
与传统基于结构启发式的方法不同，在本文中作者创新地提出了一个有效的机器学习框架GDM（GraphDismantlingwithMachinelearning）来解决上述问题，该框架的主体是一个由图卷积层和回归子组成的几何深度学习模型，能够通过在大量小型人工网络中的训练，学习到属于最小拆解集合中节点的特征聚合方式，进而快速判断出大规模网络中节点属于最小拆解集合的概率。该框架以网络中节点的中心性等特征为输入，以节点位于网络最小拆解集的概率为输出，按照概率从大到小依次移除网络中的节点，即可有效地拆解网络。