04-网络中的主题和结构角色

子图及其性质

子图(subnetworks/subgraph)​是网络的局部组成，可以用来辨别和区分网络。

image-20210123161233612

子图的结构可以有很多种，比如有向图的三节点子图$(n-node subgraphs$，这里$n=3)$就有如下几种形式：

image-20210123162120177

对于一个网络来说，可以得到很多个子图，那么什么样的子图是有意义的呢？这就需要一些参数，来衡量子图的重要性。这样，不同的网络就可以表示为以这些子图为基的特征向量。

• 对于每个子图:假设有一个能够对子图“重要性”进行分类的度量。

  • 负值表示表示不足

  • 正值表示过度表示

• 创建一个网络重要性概要:具有所有子图类型值的特征向量

• 接下来:比较不同网络的概况:

  • 调控网络(基因调控)

  • 神经元网络(突触连接)

  • 万维网(网页间超连结)

  • 社交网络(友谊)

image-20210123163348962

首先看这张图最底下，横坐标，是前面讲到的13种子图的类型，上面的每一行就是不同网络关于这13种子图的一些特征值。可以看到，同领域的网络，它的特征向量其实是相似的。比如最后一行的语言网络，对于英语、发育、西班牙语、日语等不同的语言来说，他们尽管语法不尽相同、词语不同，但是它们的特征是一致的。

主题

网络主题Network motifs：反复出现的，重要的相互联系的模式。

如何定义一个网络主题？

1. pattern ：小结构的子图

2. recurring：小结构被发现的次数

3. Significant：在随机网络中比预测的多得多的频率

   关键思想：在真实网络中出现的频率要比在随机图中出现的频率要高得多

   

网络主题的作用：

• 帮助我们了解网络是如何工作的

• 帮助我们预测网络在特定情况下的运行和反应

Motifs的一些例子：

Motifs	图例	出现的网络
Feed-forward loops 前馈环路		这种Motifs会在神经元网络中出现，会用来中和“生物噪音（biological noise）”。（这应该是属于生物信息学中的相关概念）
Parallel loops 平行环路		会在食物链网络中出现
Single-input modules		在基因控制网络中发现

与随机网络相比，定义的motifs在真实网络中出现的频率要比在随机图中出现的频率要高得多。怎样去计算这个significance（显著性）呢？设$Z_i$表示motif $i$的统计显著性。

$$Z_i = (N^{real}_i-\bar N_i^{rand}) / std(N_i^{rand})$$

这里$N_i^{real}$是指在真实网络$G^{real}$中motif$i$出现的次数，$N_i^{rand}$是指在随机网络$G^{rand}$中motif $i$出现的次数。

那么，网络的motif $i$的显著性(Network Significance Profile, SP)由标准化后的$Z_i$表示：

$$SP_i=Z_i/\sqrt{\sum_jZ_j^2}$$

$SP$更强调不同子图之间的相对显著性，这对于不同规模的网络比较十分有意义，因为一般来说网络规模越大，Z-score越高，而标准化处理则可以降低尺度效应的影响。

这里有个问题，就是我们怎么得到随机网络$G^{rand}$呢（Configuration model）？并且这个随机网络需$G^{rand}$要和真实网络有相同的 结点，边以及度分布。

这里介绍两种方式：

第一种方式，我们可以通过给定的节点数量和节点的度序列（degree sequence$ k_1,k_2,\cdots,k_N$）来生成随机图：

image-20210215200908931

第二种方式称为Switching。

我们从一个给定的图开始（这个图和真实的网络有相同的度），重复以下步骤$ Q \cdot |E|$次，$Q$会取一个较大的值（如100）来使整个过程达到收敛：

image-20210215201548407

• 随机选取一条边（例如$A \rightarrow B$，$C \rightarrow D$）

• 将边的终点随机改变。注意的是新生成的边不能构成自环或者双边。

获取具有相同节点数，边数，节点度数的随机图之后，就可以计算子图$i$的$Z$值。高值说明该子图是图G的一个Motif。

$$Z_i = (N_i^{real}-\bar N_i^{rand}) / std{N_i^{rand}}$$

Graphlets：Node feature vectors

Graphlets(图元，connected non-isomorphic subgraphs)是指大规模网络中那些节点数目较少的连通诱导子图。且Graphlets反映了网络的局部拓扑，所以它是重要的网络特征。

• 非同构子图单元，是一类特殊的子图。Graphlets是对motif的扩展。它与motifs的区别：

• motif是从全局的角度来描述图的。用不同motifs来构成一个图的向量表示。

• 而Graphlet是从局部(节点)的角度出发来描述节点。用不同graphlet中的节点相对位置（局部信息），来形成一个节点的向量表示。

image-20210303121818714

图元通常会用来比较网络之间的相似和差异。基于图元，来介绍Graphlet Degree Vector(GDV） 方法。

Graphlet Degree Vector(GDV）方法是Przulj在2003年提出的利用图元及图元向量来刻画网络中节点邻域关系的方法，具体指在小连通非同构子图中计算每个节点的自同构轨道，即每个节点所接触的图形数量。这种方法基于网络拓扑和邻域定义了一系列非同构子图和图向量，用于识别网络中结构相似的模块。

——宋祥帅, 杨伏长, 谢江,等. Graphlet Degree Vector方法的优化与并行[J]. 计算机应用, 2020, 40(2):398-403.

Graphlet Degree Vector(GDV）是一个向量，表示每个轨道位置具有该节点的频率。它刻画的是每个节点接触的图元数量。

image-20210303145436906

这里有三种不同的轨道（orbit），轨道上有a、b、c、d四种节点位置（orbit position）。对于节点$v$来说，其在轨道位置a上有2个图元，在轨道位置b上有1个图元，在轨道位置c上没有图元，在轨道位置d上有2个图元。这里需要注意的是图元是诱导子图。

因此，Graphlet Degree Vector(GDV）的实际意义在于：

• 刻画了某个节点所接触的图元（某个特殊的轨道位置的图元）的数量

• 刻画了网络中节点的局部属性

Finding Motifs and Graphlets

可将问题拆解为两步：

• 枚举所有大小为$k$的子图。

• 2.计算这些子图出现的次数

• 这里涉及子图同构的判断，是一个NP-complete问题，计算困难。通常，子图的大小选择在3到8个点。

第一步，找到所有的子图：Counting Subgraphs——Exact subgraph enumeration (ESU)算法

为了枚举所有大小为k的子图，使用ESU算法。ESU算法[Wernicke 2006]中的两个集合：

• $V_{subgrapg}$ : 目前已经构造的子图

• $V_{extension}$ : 用于扩展子图的候选节点集合

算法思想：每个节点分配唯一序号，从一个节点 开始，添加符合以下性质的节点 到：

• $u$的节点编号必须大于$v$

• $u$只能是某个新加入的节点$w$的邻居，不能是任何$V_{subgrapg}$中的节点的邻居

$ESU$算法是一个递归算法，运行过程呈现为一个深度为 k 的树，被称作ESU-tree。

ESU算法的伪代码如下：

image-20210303151012679

该算法通过递归实现的，算法过程可以看做是深为$k$的递归树：

image-20210303151634302

第二步：对找到的子图进行统计：Count the graphs

image-20210303152743233

将ESU树叶子节点上的子图分成k阶不同构的各种类别。这里涉及到怎么判断图之间是否同构，$n$个节点的两个同构图判断，需要$n!$次计算，计算量很大。常用算法的是McKay的方法，即若图G中任意一对邻接的节点$u$ 和$ v $，在图H中都有$f(u)$和$f(v)$邻接，则图$G$和图$H$同构。

通过上面两步可以得到图的 motifs 和 graphlet和对应GDV。

Structural Roles

角色是对节点在网络里的功能的描述。角色可以通过测量节点在网络里的结构特征来衡量，比如 星型结构的中心、紧密相连的节点之一、边缘节点等等。

这里要注意的是角色和社区的区别。角色是一些具有相同结构特征的节点，它们不一定是要相互连接的。而社区则是指的一些相互密集连接的节点群所构成的一个元件。

为了正式地定义角色，需要先定义网络里的结构等价：节点$u$和节点$v$ 是结构等价的，如果它们与网络里的所有其他节点有相同的关系。

从上面的定义可以看出，节点的结构等价要求是非常严格的。而这对于无论是计算量还是实际价值都没有太大的意义，所以下面会使用近似的方法，即聚类的方法来找到结构等价的节点，从而得到具有相同结构特征的节点，即角色。

RoIX算法

• role：在网络中具有相似位置的节点的集合，并且基于节点子集之间关系的相似性。

• group/community则是互相连接的个体（节点），核心在于连接性。

属于相同role的节点具有结构等价性

Why are Roles important?

image-20210303154831462

RolX算法

RoIX算法是一个无监督的学习方法，不需要先验知识，能多角色分类，同时可以做到线性扩展。

image-20210303154912057

整个算法过程虽然看着复杂，但是对于有一定机器学习基础的同学来说也很正常。基本是把一个$N \times N$的节点相邻矩阵，按照连接关系提取出节点的特征，转换成$ N \times M$的节点特征矩阵。然后使用特征间的相似度再次计算节点之间的相似性，然后使用层次化的聚类方法把节点按照相似的距离组合成不同的类，相同的类就成为了同一个角色，并最终形成节点角色矩阵和角色特征矩阵。

这里面最核心的部分就是图中红色框的部分：递归特征提取。这里所谓的递归就是指的从一个节点自身开始，获取它自己的本地的特征，并聚合起来，比如mean和sum它们。随后从这个节点扩展到本我网络(egonetwork)，即与自己相邻的所有节点以及由它们之间的边构成的子网络。然后再提取这个本我网络里的特征，比如网络的总度、总入度数、总出度数等。按照这个思路，继续迭代下去，对本我网络里的每个节点再提取特征。注意这些迭代提取的特征都还是初始那个节点的特征。

用这种方法可以提取非常多的特征，相当于一个节点一跳(one-hop)和多跳(two, three...-hop)范围的特征。

image-20210303155207916