复杂网络的高阶组织

已知许多网络表现出丰富的低阶连接模式,可以在各个节点和边缘的级别捕获。在这个项目中,我们专注于在小型网络子图(图案)层面找到复杂网络的高阶组织。为此,我们基于图案而不是边缘来聚类图形的节点。

复杂网络的高阶组织。 Austin R. Benson,David F. Gleich和Jure Leskovec。

科学,第一卷 353,不。6295,pp.163-166,2016。

论文 补充材料

有关这项工作中的想法的介绍,这里有 来自NetSci 2016的演讲的幻灯片 (也可在 pptx中获得)。

基于Motif的谱聚类方法

我们的目标是找到具有小图案电导的节点集。相对于一个基序M个节点的一组S的基序电导是φ 中号(S)=切中号(S,小号)/分钟(体积中号(S),第二卷中号(小号)),其中切中号(S ,小号)是S中的至少一个节点和一个在基序M的实例的数量 小号,并且体积中号)(S被驻留在S.在M的实例中的节点的数目
img

我们用于寻找具有小图案电导的集合S的光谱聚类技术是:

  1. 给定网络和感兴趣的主题M,形成主题邻接矩阵,其(i,j)条目是节点i和j在M的实例中共同出现的次数。
  2. 从主题邻接矩阵的归一化拉普拉斯算子计算节点的谱排序σ。
  3. 找到具有最小主题电导的σ前缀集S; 正式:S = argminφ 中号(S - [R ),其中S [R = {σ 1,…,σ [R }。

img

例子

在许多情况下,我们知道特定的图案对于给定的网络很重要。例如,已知bifan基序经常出现在神经元网络中。我们可以使用这个主题来找到网络中的簇,如

秀丽隐杆线虫

,如图所示。 通常,主题的结构显示在算法发现的聚类中。这与传统的基于边缘的集群形成对比,后者通常密集连接。以下是Twitter关注者网络中的一个示例。 我们的框架足够通用,可以处理签名,加权和彩色图案。下面是酿酒酵母转录调控网络中所谓的相干前馈环基序的基于基序的聚类的实例。

img

img

img

有时,我们可能不知道哪个主题是有意义的。我们可以针对几个图案运行基于图案的聚类,并查看哪些图案可以产生良好的效果。在下面的例子中,观察主题电导表明M

6

组织了网络。提取的簇在图案M

6

周围清晰地成形。 最后,在某些情况下,我们从我们的数据中寻求更丰富的结构,这些结构不能仅通过节点集群来实现。在下面的示例中,我们使用来自主题邻接矩阵的频谱嵌入来捕获运输可达性网络中的高阶结构。

img

img

以上为机翻结果。详细请看原文

延伸阅读:

DARPA正资助斯坦福大学开展“简化科学发现的复杂性”(SIMPLEX)项目,该项目创建了一种可扩展的、通用的模体集群框架,其算法能够自动探寻和区分数据中的隐藏模型,以便于重新认识复杂科学与工程系统的结构和行为。

研究背景:网络可用来探寻和理解复杂系统——如军事后勤、全球金融、空中管制、社交媒体及人体内生物过程——的数学表征。在每个这样的系统中,层次分明的内部模型(如细胞内相互作用的分子和蛋白质,或者集成电路中运行的电容和电阻)决定了这些系统的功能或行为。然而,系统越大越复杂,就越难以利用当前的网络建模技术来发现这些模型,也越难以条理清晰、简单易懂地加以表述。

项目情况:斯坦福大学研究人员在克服上述挑战方面取得了进展,其开发的框架可识别并聚集数学家所谓的“模体”(motif)——系统中必不可少的、但往往晦涩难懂的模型。它们是数学建模的基本构件,有助于实现对复杂系统的计算表征。该团队最核心的成功是创建了一种算法,能够自动探寻和区分数据中的隐藏模型,这是阐述网络结构和功能的基础。其研究成果《复杂网络的高阶组织》已发表在《科学》杂志上。DARPA认为,这种方法能够更有效地对复杂网络进行数学表征,揭示网络中更深层次的功能关系及每个模型对整体的作用。它提供了一种分析性、系统的、可扩展的方法:基于对模型的认识,形成与给定网络相关的假设。它表明模体集群有助于化解复杂科学与工程系统的复杂性,并加速科学发现。

测试与应用举例:作为研究的一部分,斯坦福大学团队测试了其开发的模体集群框架,并将其应用到多个复杂系统。①连接美国和加拿大人口最多50个城市的空中航线。SIMPLEX算法自动检测到八大枢纽,表明模体集群表征准确抓住了系统的本质。该框架显示网络作为一个整体,是如何围绕这些模式进行组织,并提供关于给定模式对网络结构之重要性的度量,使得用户能够对模式进行比较,发现哪些是最重要的。②将模体集群应用于蛋白质网络。斯坦福大学正与贝勒大学合作,帮助形成关于蛋白质在复杂生物系统中如何相互作用的假设。如果取得成功,这一研究有助于更好地了解疾病、改进新药研发和用于基因组作图等。

来了,老弟
-------------    本文结束  感谢您的阅读    -------------
0%