查看原文
其他

Science经典:复杂网络的简单构造模块——网络模体

郭瑞东 集智俱乐部 2021-02-24


导语模体(motif)是一个对初涉复杂科学的人来说,相对陌生的概念,但它却是复杂网络研究中最有力的工具之一。2002年的 Science 论文“Network Motifs: simple Building blocks of Complex Networks”介绍了模体的概念,至今引用次数已有 6000 多次。本文将概述这篇论文,并阐述模体在复杂网络中的广泛应用与研究前沿,说明模体已成为复杂网络研究中不可或缺的基础组件。即使对于非相关领域的研究者,理解模体的概念也可以让你体会生活中的复杂性与涌现现象。


论文题目:Network Motifs: simple Building blocks of Complex Networks论文地址:https://science.sciencemag.org/content/298/5594/824



1. 模体:

网络中多层出现局部的结构


模体的定义是:“在复杂网络中发现的某种相互连接的模式个数显著高于随机网络”。所谓互相连接的模式,在三个节点组成的有向图,一共有如下 13 种可能,其中每一种,如果在网络中出现的概率比随机网络中明显高一截,就可以看成是一个模体。模体相关的研究,又被称为基元,具体可参考《复杂网络基元研究方法及应用》这本书。


图1:3个节点所有可能的连接方式


模体可以通俗地理解为网络中频繁出现的局部连接模式。模体不限于 3 个节点。4 个或 5 个节点组成的子网络结构,也可以看成是模体。


如果节点中的边带有权重,或者节点有着内在属性(特征),可以将模体扩展为权重数值排列不同的多个子图。这些子图可以描述网络生成的动力学特征。不同于内部紧密连接的社(community),模体描述的因为网络生成过程中所涌现出的规律,而不是已完成的网络所呈现的局部密集的区域。



2. 模体的普遍与跨学科性


不同的网络中,描述的相互作用有所不同,例如在基因表达量网络中,是因为基因 X 的表达会调控基因 Y 的翻译,从而当基因 X 被 RNA 翻译成蛋白质时,基因 B 也会被翻译;在神经元网络中,类似的结构是由于神经元 X 激活了神经元 Y;而在生态网络中,则是由于大鱼 X 吃掉了小鱼 Y。通过模体这一概念,不同网络的特异性被抹去,使得研究者得以关注跨领域的共性,而这正是复杂网络研究的魅力所在。


图2:不同网络中元素间相互作用方式范例


无论是生物学,神经科学,生态学还是社交网络,论文引用网络,只要存在复杂网络,就会有模体,往往还是相同的模体出现,即使他们描述的元素不同。在日常生活中,装饰图案或音乐中反复出现的局部规律,也可以看成是广义上的模体。

图3:无处不在的模体 motif


复杂系统的涌现特征,在模体中得到了集中的展现。在局部统计显著的连接模式,会造成网络全局特征的不同,而这些特征,在仅仅观察局部网络时,是无法显现出的。模体这个概念的引入,使得网络研究的着眼点不仅限于节点角色或者是网络的整体结构,而是考虑了网络的微观结构。




3. 如何检测模体的存在


如何快速准确地找到网络中的模体,近 20 年来已有很多改进的方法。这里只介绍最初论文中提到的基本方法。下图中左图是真实世界中的网络,其中的红色三角形连接模式(即找到的模体)如左下所示。右图是随机生成的网络,在多种随机网络中,右下角的连接模式出现的概率都显著小于左图,因此可以判定其为左图中的三角形确实为左侧真实网络中的模体。
           

图4:如何通过随机网络找到模体


真实网络中模体的出现,不受制于网络的大小。下图显示线虫中基因表达网络中的前馈环路模体在不同大小的真实网络的子网络中出现的概率,与之形成对比的是随机生成网络中其出现的概率。可以看出,即使是在子网络中节点只有 30 个时,真实网络与随机网络也有显著不同,且真实网络中,不会随着节点个数的增加,导致模体出现频率出现显著变化。

图5:不同大小的真实与随机网络中模体出现概率对比


4. 了解常见的模体,

找到复杂人际网络中的规律


在 2002 年这篇 Science 论文中,作者给出了一组在多种背景中都会出现的网络模体,例如:

图6:在多种背景中会出现的网络模体

在社交网络中,上述的模体,似乎古人早已发现。例如 Three chain,可以看成是螳螂捕黄雀在后;而 Feed forward loop 对应隔山打牛;Three-node feedback loop 对应因祸得福祸福相倚。透过不同社交网络中出现的不同类型的模体,可以判断网络对应组织的文化,例如一个人际网络中,经常出现 X 制约 Y,Y 防范 Z,而 Z 又拿着 X 的小辫子的情况,这样的网络中对应的 Three-node feedback loop 模体意味着这样的组织中人际关系复杂,相互防范,不是一个适合心思单纯者的环境。



5. 模体在复杂网络中的应用


复杂网络的一大涌现性体现在其同时具有脆弱性(面对特定攻击)和鲁棒性(面对一般攻击时的恢复能力),在[1]中,通过对欧洲不同国家电网的分析,找到了特定模体出现频率和电网面对攻击(节点被删除)时的恢复能力存在相关性,从而通过基于模体的分析,判定德国和意大利电网相比法国和西班牙的更可靠。


19年的综述“Network Motifs: A Survey”[2]中,概述了模体在具体场景下的应用。首先在生物学网络中,例如蛋白质相互作用网络,可通过模体预测蛋白质间的相互作用[3],或蛋白质在网络中的功能[4]。在通过时空网络(Spatio temporal Network)对生物体的特征建模时,网络中模体的存在,可以帮助理解生物体发育过程中,基因调控网络如何发挥作用[5]。在人体内生物信号间的传导网络中,通过找到特定的模体,可以为乳腺癌的诊断和治疗提供助力[6]。在人际交流网络数据组成的时序网络中,通过识别模体,可以找到男性与女性交流方式的差异性,并找到网络中局部中的局部的均一性[7],通过识别不同的模体,可以研究微博中信息流在处在传播过程中的那个阶段[8]。通过识别模体,还可以优化无人驾驶汽车之间的信号交流网络,减少延迟[9]等。

论文题目:Network Motifs: A Survey论文地址:https://link.springer.com/chapter/10.1007/978-981-13-9942-8_8



6. 模体相关研究的进展与方向


模体相关的前沿研究,一个方向是找出更快捷的算法,来识别模体,尤其是在包含海量节点的网络中,使用 GPU,识别出包含更多节点的模体(当模体包含的节点增加,识别模体所需的时间和存储都会指数级增加)。


第二个方向是在大规模时间序列网络中,快速识别出一组相近的模体。


第三个方向是如何在多层网络,或超图中定义出类似模体这样的局部结构,从而将模体的分析扩展到高阶网络,对于该问题,可以参考[10],文中对多层模体给出了形式化的定义,并通过对真实多层网络的分析,得出多层网络中的模体在不同层次上的同质性。


在高阶网络上,基于模体可以对网络进行聚类,并将跨越网络不同层的模体定义为模体切割,从而定义出图元(graphlets)的高阶描述符,将局部连接模式 (local wiring patterning)与由其所处的高阶结构模块化结合起来[11],由此由模体出发定义出描述高阶网络局部结构的新的概念。

       

参考文献:

[1] What network motifs tell us about resilience and reliability of complex networks. https://www.pnas.org/content/116/39/19368[2] Network Motifs: A Survey.https://link.springer.com/chapter/10.1007/978-981-13-9942-8_8[3] Labeling network motifs in protein interactomes for protein function prediction. https://ieeexplore.ieee.org/document/4221703[4] Graph mining of motif profiles for computer network activity inference. https://www.cs.purdue.edu/mlg2011/papers/paper_16.pdf[5] Spatiotemporal network motif reveals the biological traits of developmental gene regulatory networks in drosophila melanogaster. https://bmcsystbiol.biomedcentral.com/articles/10.1186/1752-0509-6-31[6] Identification of breast cancer patients based on human signaling network motifs. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3842546/[7] Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences. https://www.pnas.org/content/110/45/18070[8] Understanding Information Flow in Cascades Using Network Motifs. http://arxiv.org/abs/1904.05161 
[9] Spatio-temporal motifs for optimized vehicle-to-vehicle(v2v) communications. https://arxiv.org/abs/1711.06306[10] Analysing Motifs in Multilayer Networks. http://arxiv.org/abs/1903.01722[11] Full Higher-order organization of complex networks. https://science.sciencemag.org/content/353/6295/163.


(参考文献可上下滑动)



作者:郭瑞东

审校:刘世康

编辑:张爽


推荐阅读


复杂网络上的爆发现象综述:相变、爆发、生命起源有何共同之处
Nature 通讯:复杂网络如何化繁为简?
复杂网络升阶指南:如何构建最优网络模型
召唤热爱科学,乐于探索的你 | 2020 集智俱乐部志愿者招新





集智俱乐部QQ群|877391004

商务合作及投稿转载|swarma@swarma.org

◆ ◆ ◆

搜索公众号:集智俱乐部


加入“没有围墙的研究所”

让苹果砸得更猛烈些吧!



👇点击“阅读原文”,了解更多论文信息

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

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