1. 我是CIO首页
  2. 资讯
  3. 人工智能

一个深度强化学习框架,用于识别复杂网络中的关键参与者

一个深度强化学习框架,用于识别复杂网络中的关键参与者
在网络中寻找关键参与者。(a)9/11恐怖主义网络,其中包括62个节点和159个边缘。节点代表参与9/11攻击的恐怖分子,边缘代表他们的社交交流。节点大小与其程度成正比。(b)移除高度(HD)最高的16个节点(青色)会造成相当大的损害,剩下14个节点的GCC(紫色)。(c)删除具有最高集体影响力(CI)的16个节点(青色)会导致碎片,剩下的GCC(紫色)包含18个节点。(d)FINDER仅删除14个节点(青色),但导致网络更加分散,其余的GCC(紫色)仅包含9个节点。

网络科学是一个旨在揭示诸如电信,计算机,生物和社会网络等网络背后的结构和动态的学术领域。近年来,网络科学家一直试图解决的基本问题之一是,确定最能影响网络功能的最佳节点集(称为关键参与者)。

确定主要参与者可能会极大地受益于许多实际应用,例如,增强网络免疫的技术,以及辅助流行病控制,药物设计和病毒营销。然而,由于其具有NP难性,使用具有多项式时间复杂度的精确算法来解决此问题已证明具有很高的挑战性。

中国国防科学技术大学,加利福尼亚大学洛杉矶分校(UCLA)和哈佛医学院(HMS)的研究人员最近开发了一种名为FINDER 的深度强化学习(DRL)框架,该框架可以识别复杂网络中的关键参与者更有效率。他们的框架(在发表于《自然机器智能》上的一篇论文中介绍)中接受了由经典网络模型生成的一小套合成网络的训练,然后应用于实际场景。

“这项工作是由网络科学中的一个基本问题所激发的:我们如何找到最佳的关键角色集,这些角色的激活(或移除)将最大程度地增强(或降低)网络功能?” 进行这项研究的高级研究人员之一刘养宇告诉TechXplore。“已经提出了许多近似和启发式策略来处理特定的应用场景,但是我们仍然缺乏一个统一的框架来有效地解决这个问题。”

FINDER代表通过DEep强化学习在网络中寻找关键参与者,它以最近开发的深度学习技术为基础,用于解决组合优化问题。研究人员在由经典网络模型生成的大量小型合成网络上对FINDER进行了培训,并使用针对要解决的任务的奖励函数来指导FINDER。该策略可指导FINDER根据其当前状态(即当前网络结构)确定在一段时间内累积最大报酬应采取的措施(即应选择的节点)。

参与这项研究的另一位资深研究员孙义州说:“在传统的强化学习任务中,例如在机器人技术中,可以很容易地表示状态和动作,而对于网络而言,情况并非如此。” “在进行此项目时,我们面临的另一个挑战是确定如何表示网络,因为它具有离散的数据结构并且位于一个非常高的空间中。为解决此问题,我们扩展了当前的图神经网络来表示节点(动作)和图形(状态),这是与强化学习任务共同学习的。”

一个深度强化学习框架,用于识别复杂网络中的关键参与者
在9/11恐怖分子网络中寻找关键参与者,其中每个节点代表参与9/11攻击的恐怖分子,边缘代表他们的社交交流。节点大小与其程度成正比。三种方法:(a)高学历(HD);(b)寻找者;(c)集体影响力。蓝色节点表示剩余图中的节点,红色节点表示在当前时间步确定的关键参与者,灰色节点是其余的孤立节点。面板(d)展示了这三种方法的累积归一化连接性(ANC)曲线,其中的水平轴为已删除节点的比例,垂直轴为其余巨型连接组件(GCC)中节点的比例。

为了有效地表示复杂的网络,研究人员共同确定了各个网络状态和动作的最佳表示,以及当网络处于特定状态时确定最佳动作的最佳策略。结果表示可以指导FINDER识别网络中的关键参与者。

Sun,Liu及其同事设计的新框架具有很高的灵活性,因此只需更改其奖励功能,就可以将其应用于各种现实网络的分析。它也非常有效,因为发现它在效率和速度方面都优于许多以前确定网络中关键参与者的策略。值得注意的是,可以轻松扩展FINDER以分析包含数千个甚至数百万个节点的广泛网络。

“与现有技术相比,FINDER在寻找复杂网络中关键参与者的有效性和效率上均取得了卓越的性能,” Liu说。“这代表了解决复杂的现实世界网络上具有挑战性的优化问题的范式转变。FINDER不需要领域特定知识,而只需真实网络的程度异质性,就可以通过仅在小型合成图上进行离线自训练一次来实现这一目标,然后令人惊讶地将现实世界网络的各个领域的规模都大大提高了。”

迄今为止,新的深层加固框架已取得了令人鼓舞的结果。将来,它可用于研究社交网络,电网,传染病的传播以及许多其他类型的网络。

刘,孙和他们的同事收集的发现强调了经典网络模型(如Barabási–Albert模型)的希望,并从中汲取了灵感。尽管简单的模型可能看起来非常基础,但实际上,它们通常捕获了许多现实世界网络的主要特征,即程度异质性。当尝试解决与复杂网络有关的复杂优化问题时,此功能可能具有巨大的价值。

“我的实验室现在沿着相同的研究方向寻求多个研究方向,包括:(1)设计更好的图表示学习体系结构;(2)探索如何在不同图甚至不同领域的图之间传递知识;(3)研究图上的其他NP难题,并从学习的角度解决它们。”

当Sun和她在UCLA的团队计划研究网络科学研究的新技术时,Liu及其在HMS的团队希望开始在真实生物网络上测试FINDER。更具体地说,他们希望使用该框架来识别可能在人类健康和疾病中发挥关键作用的蛋白质-蛋白质相互作用网络和基因调控网络中的关键参与者。

本文为作者 胡慧 独立观点,并不代表 我是CIO 立场。

发表评论

登录后才能评论