查看原文
其他

多层网络引入相关性,提升链路预测能力 | PRE研究速递

郭瑞东 集智俱乐部 2022-05-09


导语


传统研究中,多层网络进行建模的过程并未考虑层与层之间的相关性,这导致了很难将其适用于现实场景。近日一篇发表于Physical Review E 的论文,以随机网络模型为基础,引入多层网络间不同层节点的相关性,在链路预测问题中取得良好表现

郭瑞东 | 作者

赵雨亭 | 作者

邓一雪 | 编辑





原文题目:

Inference of edge correlations in multilayer networks

原文地址

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.102.062307




1. 使用多层网络对生活中的现象进行建模




多层网络分析是网络科学的热点方向。借助多层网络,多种类型的相互作用(如依赖时序等的数据)都可以被研究。


任何一位学生,大一入学时的社交网络和大四毕业时截然不同。如果将每年的社交网络看成是多层网络中的一层,由于人们持续会选择和特定的人发生联系,所以每一层节点中经常会出现如三人小团体这样的局部结构。同时,不同学年——即不同网络层次的朋友——也有着相互之间的关联:从上一年到当下,有些友谊依然持续,有些则不然。这体现了不同层次网络之间的相关性。
图1. 多层网络示意图


研究者将问题限制到上图的两层网络。黑点之间的连线意味着节点间存在正相关,白点之间的连线意味着存在负相关,黑点与白点之间的连接,意味着两点之间存在着统计独立性。由此,改进后的多层网络可实现对现实不同场景进行建模。如描述使用者-物品,本文改进后的网络可表示为消费者(黑点)有选择的购买某类商品(白点)




2. 多层网络上的推断问题




使用随机多层网络这一工具,可以解决多种网络相关问题——例如链路预测(根据已知的网络,预测未知网络的部分节点间的)、图与图的配对(根据两个匿名的社交网络,例如推特和脸书,预测哪两个用户是同一个人)、多层网络合并(判定不同层网络之间的相关性,将强相关的两层通过丢弃或合并减至一层)等。


为了解决上述问题,一个常见的套路是通过生成随机网络拟合真实数据,得出随机网络中的参数,从而将真实世界的问题转换为解决随机网络中的问题——这样能够利用随机网络生成机制,让问题变得容易解决。


目前常用多层随机块模型(SBMs)来进行网络结构推断,即链路预测。该模型根据节点的小团体标签,独立地对不同层中的连线进行抽样。但随机块模型的假设前提存在缺陷:在真实场景下不同层次节点之间的连边关系,不一定是每层网络独立的。





3. 节点度校正的随机块模型效果最优




本文研究者利用三种方式构建随机多层网络并比较:分别是ER随机网络模型、随机块模型(加入层于层之间节点的相关性的参数)、以及论文提出的新模型——节点度校正的随机块模型。该模型在随机块模型的基础上,允许不同层的网络呈现不同的节点度分布,使用最大似然法进行参数估计。


图2. 三种网络模型的链路预测效果对比


在模型验证阶段,研究者先使用模拟数据,比较不同模型下链路预测的准确性。结果显示新的模型有更好的ROC(receiver operating characteristic curve,接收者操作特征曲线。用于选择最佳的信号侦测模型、舍弃次佳的模型。或是在同一模型中设定最佳阈值)。同时通过真实消费者数据构建二分网络,预测哪些消费者会购买特定产品。由此,进而论证了新模型具有较好的预测准确性。





4. 模型应用及拓展




之后,研究者使用了三种社交网络(贸易网、航空交通网及arXiv网站)、三种生物网络(线虫神经元连接组、疟原虫基因组、人类蛋白组)的数据,分别计算每层网络之间的相关程度,进一步说明了使用多层网络这一工具,可以抽取出数据背后的领域知识。


当前的模型只能依次在两个相邻层之间,进行参数估计。展望未来,可以尝试将模型扩展到同时考虑多层之间的相关性。上述改进,可以进一步减少建模中的人为干预——如本模型可以根据某月的购物数据,预测下月的可能购物;也可以根据去年12月的数据,预测今年12月的情况——然而,这个过程仍然需要人为进行选择基于哪种信息进行预测。如果考虑了多层而非相邻两层间的相关性,则模型可以自动根据去年12月的购物情况,对今年12月进行预测。


该文提出的模型,使得研究者在使用多层网络时,可以不再假设层与层之间是相互独立的,能够更准确进行链路预测、社团发现等任务,从而降低人为干预的比重。


复杂科学最新论文


集智斑图顶刊论文速递栏目上线以来,持续收录来自Nature、Science等顶刊的最新论文,追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能,每周通过微信服务号「集智斑图」推送论文信息。扫描下方二维码即可一键订阅:


推荐阅读



点击“阅读原文”,追踪复杂科学顶刊论文

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存