复杂网络的高阶组织

1. S中的节点尽量多的包括模体M
2. S应该尽量避免破坏模体
   更准确的说，对于给定的模体M，本文所提出的高阶聚类框架的目标是找到一个聚类S， 使得下式取得最小值：
   
   其中cut(S, _{S):表示将整个网络分为S和}S(S的补集)时被破坏的模体M的个数， vol(S)则是集合S中属于模体的节点的数量。
   在图1B中可以看出：ΦM(S)=1/min[8,10] = 1/8;(当S为5时)模体电导最小。
   找到精确的节点集S，使基序电导最小，在计算上是不可行的(12)。为了近似最小化Eq. 1，从而识别高阶簇，我们开发了一个优化框架，该框架可证明找到接近最优簇[补充材料(13)]。将基于与图(11)相关矩阵的特征值和特征向量的谱图聚类方法推广到网络的高阶结构。该方法保持了传统谱图聚类的特点:计算效率高，易于实现，并对得到的聚类的近似最优性有数学保证。具体地说，我们的高阶聚类框架识别的聚类满足基序 Cheeger不等式(14)，这意味着我们的优化框架发现的聚类最多是一个偏离最优的二次因子。
   
   图1 高阶网络结构和高阶网络聚类框架
   （A） 高阶结构由网络基序捕获。例如，这里显示了所有13个连接的三个节点的有向图形。（B）基于基序 M7的网络聚类。对于一个给定的基序M，我们的框架的目标是找到一组节点S，使基序电导最小，fM(S)，我们将其定义为在S或S(13)中基序的实例中基序切割(填充三角形切割)的数量与最小节点数量的比值。在这种情况下，有一个主题削减。（C）高阶网络集群框架。给定一个图和一个感兴趣的基序(在本例中为M7)，通过计算基序实例中两个节点同时出现的次数，该框架形成一个基序邻接矩阵(WM)。然后计算了基序邻接矩阵拉普拉斯变换的特征向量。由特征向量(15)的分量提供的节点的有序s产生了增大r的嵌套集Sr = {s1，，， Sr}。我们证明了基于最小基序电导的集Sr (Sr)是一个近似最优的高阶簇(13)。
   该算法(如图1C所示)有效地识别了如下节点簇S：
   （1） 给定一个网络和一个感兴趣的模体M，形成模体邻接矩阵WM，其(i, j)是模体M中节点i和j的共现计数:(WM)ij =包含节点i和j的M的实例数。
   （2） 从模体邻接矩阵的归一化拉普拉斯算子计算节点的谱排序σ。
   （3） 找到具有最小主题电导的σ前缀集S; 正式：S = argminφ 中号（S – [R ），其中S [R = {σ 1，…，σ [R }。
   算法过程描述：
   0)输入网络和给定的模体。

1)计算矩阵Wm， 其元素(i， j)为节点i和j在模体中共现的次数，即模体包含节点i和j的个数（该矩阵为对称矩阵）。

2)计算模体的laplacian矩阵L， L=D- Wm， 其中D为对角矩阵，Dii =Σj(WM)ij 。

3)对laplacian矩阵进行单位化为Lw， Lw = D^(-1/2)LD(-1/2), 其中D = 1/D^1/2。

4)\sigma为对D(-1/2)z进行升序排列得到的下标序列， 其中Lw的第二小的特征向量所对应的特征值。

5)扫描\sigma序列产生它的前缀集合， 寻找最小的模体比， 即使得上式最小的\sigma的前缀集合。

图二 线虫神经网络中的高阶簇。（A）四节点双扇形图案，在神经元网络中过表达（1）。直观地说，这个主题描述了信息从左边的节点到右边的节点的协同传播。（B）秀丽隐杆线虫中最好的高阶群基于（A）中的基序的额叶神经网络。该集群包含三个环形运动神经元（RMEL，-V和-R;青色），具有许多输出连接，作为信息源; 六个内部唇部感觉神经元（IL2DL，-VR，-R，-DR，-VL和-L;橙色），有许多传入连接，作为信息的目的地; 和四个URA运动神经元（紫色）充当中介。这些RME神经元已被提议作为神经环的先驱（21），而IL2神经元是已知的听写调节器（22）），高阶集群暴露其组织。该集群还揭示了RIH是信息处理的关键中介。该神经元具有来自三个RME神经元的传入链接，到六个IL2神经元中的五个的传出连接，以及群集中任何神经元的最大连接总数。（C）整个网络环境中高阶集群的图示。节点位置是神经元的真实二维空间嵌入。大多数信息从左向右流动，我们看到RMEV，-R，-L和RIH作为右侧神经元的信息来源。

对于三角形模体，该算法可以扩展到具有数十亿条边的网络，而且通常只需要几个小时就可以处理如此大小的图形。在具有数十万条边的较小网络中，该算法可以处理数量为9的模体。虽然三角形模体算法的最坏情况计算复杂度为Q(m1.5)，其中m为网络中的边数，但在实际应用中，该算法要快得多。通过分析16个真实世界的网络，其中边的数量m的范围从159,000到20亿，我们发现计算复杂度为Q(m1.2)。此外，该算法易于并行化，可以使用采样技术进一步提高性能(16)。 该框架可应用于有向、无向和加权网络。此外，它还可以应用于边上有正，负信息的网络，这在社交网络中很常见(朋友对敌人或信任对不信任)和代谢网络(边缘表示激活而不是抑制) (13)。该框架可用于识别领域知识表示感兴趣主题的网络中的高阶结构。在补充材料中，我们还表明，当一个领域特定的高阶模式事先不知道时，该框架还可以用来确定哪些主题对于给定网络的模块化组织是重要的(13)。这样一个通用的框架允许在许多不同的网络中使用单独的模体和一组模体来实现复杂的高阶组织结构。该框架和数学理论立即扩展到其他谱方法，如在种子节点周围找到集群的本地化算法(17)和找到重叠集群的算法(18)。要找到几个集群，可以使用来自多个特征向量的嵌入和k-means集群(13,19)，也可以应用递归二分法(13,20)。

该框架可用于识别网络的高阶模块化组织。我们将高阶聚类框架应用到Caenorhabditis elegans神经网络中，其中四节点双扇模体过度表达(图2A)(1)。然后，高阶聚类框架揭示了Caenorhabditis elegans神经网络中基序的组织。我们在额叶区发现了一个由20个神经元组成的簇，具有低双扇模体电导(图2B)。集群显示了一种控制nictation的方法。在簇内，环形运动神经元(RMEL， -V，或-R)，提出了神经环的先驱(21)，通过神经元RIH将信息传递到内唇感觉神经元，nictation的调节因子(22)(图2C)。我们的框架将双扇模体在这种控制机制中的重要性联系起来。
该框架还提供了关于网络组织的新见解，而不仅仅是基于边缘的节点集群。在一个交通可达性网络(23)上的结果显示了它是如何找到必要的枢纽互联机场的(图3)。当使用两个two-hop的基序(图3A)捕获高度连接的节点和非枢纽时，这些极值出现在主光谱方向上(图3C)。[归一化基序拉普拉斯算子嵌入的第一个谱坐标与空城站城市人口呈正相关，Pearson相关系数为99%置信区间(0.33,0.53)。次级谱方向确定了北美航线网络中东西向的地理位置[与空港城市纵坐标呈负相关，Pearson相关系数为99%置信区间(0.66,0.50)]。另一方面，基于边缘的方法结合了地理和枢纽结构。例如，使用基于边缘的方法(图3D)将大型中心Atlanta嵌入到非中心Salina旁边(图3D)。
我们的高阶网络聚类框架将网络科学中的两个基本工具模体分析和网络划分结合起来，揭示了复杂系统中新的组织模式和模块。先前在这些方面所做的工作并没有为所获得的集群提供最坏情况下的性能保证(24)，也没有揭示哪些模体组织了网络(25)，而是依赖于扩展网络的大小(26,27)。补充材料(13)中的理论结果也解释了为什么超图划分方法的类比之前假设的更一般，以及基于模体的聚类如何为有向图划分的特殊情况提供了一个严格的框架。最后，高阶网络集群框架通常适用于多种网络类型，包括有向网络、无向网络、加权网络和有符号网络。

今天的文章复杂网络的高阶组织分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。