提高复杂网络分析效率!中国科学家研发强化学习新框架

提高复杂网络分析效率!中国科学家研发强化学习新框架

近日,中国国防科技大学、美国加州大学洛杉矶分校和哈佛医学院的研究人员研发了一个深度强化学习框架FINDER。相比于现有的解决方案,FINDER能够更快速、更高效地找到复杂网络中一组最关键的节点,进而使复杂网络以较高的效率运行。

作者:董温淑来源:智东西|2020-06-30 09:54

 收藏

  分享

  提高复杂网络分析效率!中国科学家研发强化学习新框架

近日,中国国防科技大学、美国加州大学洛杉矶分校和哈佛医学院的研究人员研发了一个深度强化学习框架FINDER。相比于现有的解决方案,FINDER能够更快速、更高效地找到复杂网络中一组最关键的节点,进而使复杂网络以较高的效率运行。

这项研究发表在国际期刊《自然》旗下的《自然–机器智能》上,论文标题为《用深度强化学习找到复杂网络的关键参与者(Finding key players in complex networks through deep reinforcement learning)》。

论文链接:
https://www.nature.com/articles/s42256-020-0177-2

 

 

一、FINDER:适用场景更广泛,运行速度快出几个数量级

在物理科学、信息科学、生物科学等领域的研究中,研究人员可以通过建立网络拓扑结构来模拟实际情况、进而作出预测。

在这类复杂网络的运行过程中,节点间的配合直接决定了复杂网络运行的效率。当被用于解决NP难题(NP-hard)时,复杂网络中节点的“分工协作”尤其重要。

NP难题指的是在多项式时间内可以被验证其正确性的问题。比如,在疫情防控领域,复杂网络模型可以模拟出疫情传播情况、帮助找到疫苗药物分子等。运行这些任务时,复杂网络要推演和验证病毒是否会传染给下一个人、某种药物分子是否有效的各种情况。在这个过程中,找到最关键的节点能够提升复杂网络的运行效率。

对于这类问题,现有的解决方案通常基于大型网络进行训练、针对特定场景提出策略,但缺乏统一的框架。相比之下,中国国防科技大学、加州大学洛杉矶分校、哈佛医学院的研究人员提出的FINDER可以应用于广泛的复杂网络场景,其运行速度快了几个数量级。

二、分两阶段进行训练,分别采用不同奖励函数

FINDER框架采用纯数据驱动的方法,分两个阶段进行训练。在两个阶段中,研究人员用不同的奖励函数来训练FINDER。

第一阶段用经典模型生成的小型合成网络对FINDER进行离线训练。离线训练采用ϵ-greedy策略。

离线训练阶段分三步进行:首先,研究人员生成一批合成图形;然后,研究人员从合成图形中任意取样一个图形;接下来,FINDER框架在这一图形上进行整个寻找关键节点的流程。这一流程中,代理与图形通过一系列状态、动作、激励进行交互。

为了确定状态的正确动作,代理先在当前的图形上编码,并获取每个节点的嵌入向量。节点的嵌入向量会捕获节点的结构信息和节点特征之间的长程相互作用(long-range interaction)。接下来,代理将嵌入向量解码为标量Q值,以便所有节点能够预测部署某个动作的长程增益。

提高复杂网络分析效率!中国科学家研发强化学习新框架

▲离线训练阶段示意图

一旦离线训练结束,FINDER就进入第二个训练阶段,被应用于真实网络拓扑结构中。研究人员在浣熊接触网络(the raccoon contact network)的最大连通元件(connected component)上进行测试。最大连通元件包括14个节点和20条边。

这一阶段中,代理首先将当前网络编码为低维嵌入向量,然后利用这些向量对每个节点的Q值进行解码。

第二阶段采用“批量节点选择(batch nodes selection)”策略。该策略在每个自适应步骤中选择一个有限分数的最高Q节点,避免了对嵌入向量和Q值的逐个迭代选择和重新计算。批量节点选择策略不会影响最终的结果,但可以降低几个数量级的时间复杂度。

研究人员会重复这个过程,直到复杂网络达到用户定义的终端状态、被移除的节点构成最优的节点集合。

提高复杂网络分析效率!中国科学家研发强化学习新框架

▲用真实复杂网络进行训练示意图

三、对比3个模型性能,FINDER找出关键节点的效率最高

相比于机器人等传统的强化学习技术(状态和动作较为简单),复杂网络技术更加复杂和难以表示。研究团队高级研究员孙怡舟称,这是因为复杂网络具有离散的数据结构和处于极其高维的空间。

本项研究中,研究人员用图神经网络(GNN)来解决这个问题。图神经网络中的节点代表动作、图形代表状态。

以911恐怖袭击事件发生预测网络为例,网络中每个节点代表参与911恐袭的恐怖分子、每个边(edge)代表他们的社会交流。

研究人员在911恐怖袭击事件发生预测网络上运行FINDER框架,并运行现有的高维(HD)方法和集体影响(CI)方法做对比。

下图d显示了三种方法的ANC曲线。在框架部署动作后,剩余节点的重要性越低,代表框架性能越好。

可以看到,FINDER框架最有效地找到了复杂网络中关键节点。相比于其他两个解决方案,随着被移除节点的重要性升高,运行FINDER框架的复杂网络中剩余的节点重要性最低。

▲911恐怖袭击事件发生预测网络(蓝色点代表剩余图形中的节点,红色点代表当前时间步长中FINDER找出的关键节点,灰色点代表剩余的孤立节点)

结语:未来将可用于更多类型复杂网络

FINDER框架通过深度强化学习方法进行训练,可以找到复杂网络中的关键节点。在未来,FINDER框架或可被用于优化社交网络、电力网络、传染病蔓延网络等模型的性能。

目前,加州大学洛杉矶分校的研究团队正计划将FINDER框架用于网络科学研究。哈佛医学院的团队希望将FINDER用于生物网络,以确定蛋白质交互网络和基因调控网络中的关键参与者。

另外,研究人员称未来将从以下三方面着手,提升框架寻找关键节点的性能:设计出更好的图形表示学习架构;探索如何在跨图形甚至跨域转移知识;研究并解决复杂网络上的其他NP难题。

【编辑推荐】

  1. 前端老司机都在用的Chrome开发者工具15 个小技巧
  2. 微软开发出一套能恢复严重退化老照片的新算法
  3. 深度学习先驱Yann LeCun被骂退推特:你们都很懂,从此我不说话了
  4. 财务服务器“虚拟化”,浪潮助力鄂旅投开启“云化”之路
  5. Linus Torvalds:Linux 内核、社区多元化和开发者的未来

热门文章

暂无图片
编程学习 ·

安卓安全那点事

本文旨在对于一个安卓app的安全知识做一个较为泛泛的总结,为开发出更安全的应用提供思路。内容比较粗略,仅起到抛砖引玉的效果,还望大家见谅。Android应用的安全 意义 在维基百科上有一个关于计算机安全的定义: 计算机安全(computer security)是计算机与网络领域的信息安…
暂无图片
编程学习 ·

树莓派4B介绍及其系统安装 入门教程(一)

树莓派4B介绍及其系统安装 入门教程(一)树莓派介绍系统下载安装连接外设启动后续计划入门进阶扩展参考资料 树莓派介绍 树莓派介绍可以参考链接: 树莓派介绍。里面介绍的很详细了,这里就不重复讲了,也可以去树莓派官方网站下载它的参数资料,里面也有很多利用树莓派设计制作…
暂无图片
编程学习 ·

【数据结构】数据结构三要素

数据结构三要素 数据结构的三要素包括数据逻辑结构、数据存储结构和数据的运算。 数据逻辑结构 数据的逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。它与数据的具体存储形式无关,是独立于计算机的。数据逻辑结构通常分为线性结构和非线性结构。典型的数据结构…
暂无图片
编程学习 ·

IO基础篇:自动关闭接口AutoCloseable

介绍 在没有AutoCloseable之前,我调用资源对象,调用完毕后,必须要关闭,否则可能出现资源耗尽的情况 从名字就可以看出,AutoCloseable是一个可以自动保存资源并且关闭资源对象的接口,那么实现它的类就可以自动关闭资源,那怎样自动关闭呢?我们可以看下面例子: 例子 publ…
暂无图片
编程学习 ·

JS笔记(一)

1.JS基本类型:ECMAScript 中有5种简单数据类型(也称为基本数据类型):Undefined,Null,Boolean,Number和String。一种复杂数据类型:object# typeOf null 的结果为Objectvar n = null var flag = true var s = str var num = 11 var un = undefinedconsole.log(typeof(n)); …
暂无图片
编程学习 ·

JavaScript-从入门到入土(五)

BOM BOM(Browser Object Model): 浏览器对象模型,是用来描述与浏览器进行交互的方法和接口 BOM下面有一个核心的对象 – window对象。 window下面的常用的事件操作: onload() 页面内容加载完成后执行这里的代码 onscroll() 浏览器的滚动条触发时触发此事件 onresize(…
暂无图片
编程学习 ·

Mybatis直接写sql与使用association映射性能比较

最近在公司发现前辈写多表查询时使用mybatis并未使用等标签封装数据 这引发我对mybatis=有无使用标签进行数据查询的性能比较产生了兴趣,于是乎~~~做了个小小的测试 首先建立两个表:student 和 teacher teacher表结构:student表结构:用java分表为两个表写了个120万的循环…
暂无图片
编程学习 ·

论面向服务架构设计及其应用

在准备架构师考试过程中发现可供参考的论文范围非常少且内容陈旧给学习带来很大烦恼,通过考试后把我准备的论文共享出来水平有限但内容格式迎合考试,希望给大家一个参考。范文以“论面向服务架构设计及其应用”为题书写,希望对大家有所帮助。【摘要】2017年5月,我参加了某省…
暂无图片
编程学习 ·

排序算法总结

排序算法总结选择排序插入排序希尔排序归并排序自顶向下自底向上快速排序堆排序选择排序 算法流程:首先找到数组中最小的元素 将这个最小的元素与数组首位元素交换位置 在剩下的元素中找到最小的元素,并与数组第二个元素交换位置 如此往复直到整个数组排序算法分析:时间复杂度…
暂无图片
编程学习 ·

一文教你如何在IDEA上安装scala插件并创建工程

大家好,我是不温卜火,是一名计算机学院大数据专业大二的学生,昵称来源于成语—不温不火,本意是希望自己性情温和。作为一名互联网行业的小白,博主写博客一方面是为了记录自己的学习过程,另一方面是总结自己所犯的错误希望能够帮助到很多和自己一样处于起步阶段的萌新。但…
暂无图片
编程学习 ·

Python基础语法:print()、input()函数与变量

知识:print()、input()函数与变量————————————————————————————————————————1、print()与引号的使用print(This is a egg) #》》This is a egg print(This \s a egg) #》》Thiss a egg print("Thiss a egg") #可以打印&quo…
暂无图片
编程学习 ·

指针的偏移

基本数据类型指针偏移//方便演示,先初始化一个指针为空。 int* a = nullptr; a = a+1;//+1就偏移一个单位,而a定义的是指向int型数据的指针,int型有4个字节,所以输出就是00000004//假设我们定义一个一维数组int arr[5]={1,2,3,4,5};int* p= &arr[0];//这里也可以直接写…
暂无图片
编程学习 ·

秋招offer收割机——后台服务器开发方向(专业学习路线图总结)

IT行业,从业技术方向千千万,为什么我称后台服务器开发领域为offer收割机。 首先我们看一下,如果要从事后台服务器开发要掌握哪些技术! 有点多,做好心理准备。可能技术的全面度是你之前没有见过。 看到这里是不是先关注,收藏一波。便于日后再学~~~1.算法与设计 排序与查找…