《Higher-order organization of complex networks》-论文学习笔记

本文主要是介绍《Higher-order organization of complex networks》-论文学习笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0.前言：

最近阅读了Benson等人发表在science上的论文《Higher-order organization of complex networks》，在该论文中作者提出了一种通用的框架，可在网络中基于高阶连接模式进行聚类。和以往接触的聚类方法（K-means，层次聚类， DBSCAN，或者OPRICS）等不同的是： K-means等在对item进行聚类的时候，使用的是item的特征，并且item之间是没有连边的。比如，对于二维平面上的点进行聚类，那么对于每一个点来说有两个特征（即x和y），或者在MovieLen数据集上对用户进行聚类，那么每个用户的特征就是看过的电影。而在该论文中提出的高阶聚类框架是针对连通的网络（甚至要在运行算法之前做预处理，去除掉网络中的孤立的点）。

1 . 网络是理解和调控复杂系统的基本工具。为了挖掘网络化数据连接模式，揭示出功能组织，仅考虑简单描述符号是不够的，比如每个实体(即节点)和其他实体的相互作用数量（节点度），因为在这种简单描述符号层面，两个网络可能等同，但它们的连接结构非常不同。本文提出了一种通用的框架，基于高阶连接模式对网络进行聚类。这个高阶连接模式包含了出现在数据中的所有交互作用，通过该框架鉴别出富含某个特定高阶模式实例的网络区域。如果这种高阶连接模式是预先指定的，那么这种方法就能发现通过这个模式互连的节点，作者等人通过该方法将线虫神经元网络中的20个神经元成功地组织在一起。

2 . 最常见的高阶结构是小网络子图，称为模体，网络模体被认为构建了复杂网络中的块。需要说明的是：不同的网络模体揭示不同的高阶聚类，也就是说，基于不同的模体，可以发现不同的组织模式。下图给出了所有的三节点的有方向的模体：（13种）

3 .算法思想：

对于给定网络和感兴趣的模体M，寻找满足以下两个目标的节点的聚类S，使得S满足以下的两个目标：

1. S中的节点尽量多的包括模体M

2. S应该尽量避免破坏模体

更准确的说，对于给定的模体M，本文所提出的高阶聚类框架的目标是找到一个聚类S，使得下式取得最小值：

其中cut(S, ~S):表示将整个网络分为S和~S(S的补集)时被破坏的模体M的个数， vol(S)则是集合S中属于模体的节点的数量。

4. 算法过程描述：

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的前缀集合。

针对下左图的网络基于右边给出的模体进行聚类得到的\sigma的排序如下：

5. 应用：

该框架可以应用于有向图，无向图和加权图中。也可以应用于边上有正，负信息的网络，这是在社会网络中常见的类型（例如是敌是友，信任还不信任）或者在新城代谢网络中表现为活跃还是抑制。在特定的领域中，对感兴趣的模体,可是使用该框架获得网络中的高阶结构。当某个特定领域中的高阶模式未知，该框架也可用于判断哪个模体对于给定网络的模块化结构是重要的。

在秀丽隐杆线虫神经元网络上使用高阶聚类框架，在该网络中，四节点双扇形模体被过度表达，这个模体描述了从左边节点向右边节点传递合作繁殖信息的过程。该框架基于上述模体发现了由20个神经元组成的聚类。该聚类展示了瞬眼调节器被调控的一种途径。这个聚类包含了作为信源的3个带有多个外向连接的环状运动神经元（REML，-V，和-R），6个作为信息目的地的带有多个内向连接的内唇感觉神经元（IL2DL，-VR，-R，-DR，和-L），4个作为中介的URA运动神经元。该高阶聚类揭示了它们的组织。