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

## 子图及其性质

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

![image-20210123161233612](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-c63d7e041be9ba597eca744b2a34a543ee02b891%2Fimage-20210123161233612.png?alt=media)

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

![image-20210123162120177](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-04e0d41585702e674e484fe5305afdc1b27b3e4e%2Fimage-20210123162120177.png?alt=media)

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

* 对于每个子图:假设有一个能够对子图“重要性”进行分类的度量。
  * 负值表示表示不足
  * 正值表示过度表示
* 创建一个网络重要性概要:具有所有子图类型值的特征向量
* 接下来:比较不同网络的概况:
  * 调控网络(基因调控)
  * 神经元网络(突触连接)
  * 万维网(网页间超连结)
  * 社交网络(友谊)

![image-20210123163348962](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-fbcae885ed2e6dc253ca57e045e279cbb3918bb4%2Fimage-20210123163348962.png?alt=media)

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

## 主题

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

如何定义一个网络主题？

1. `pattern` ：小结构的子图
2. `recurring`：小结构被发现的次数
3. `Significant`：在随机网络中比预测的多得多的频率

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

   <img src="https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-7f4cf269cd95cb11a1993dc19d68f78886f367cd%2F202005181103351.png?alt=media" alt="在这里插入图片描述" data-size="original">

网络主题的作用：

* 帮助我们了解网络是如何工作的
* 帮助我们预测网络在特定情况下的运行和反应

`Motifs`的一些例子：

| Motifs                    | 图例                                                                                                                                                                                                                        | 出现的网络                                                                    |
| ------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------ |
| `Feed-forward loops` 前馈环路 | ![在这里插入图片描述](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-1bd35abcd52dc1c2658962b31924fcb877a3f800%2F20200518105126518.png?alt=media) | 这种`Motifs`会在神经元网络中出现，会用来中和“生物噪音（`biological noise`）”。（这应该是属于生物信息学中的相关概念） |
| `Parallel loops` 平行环路     | ![在这里插入图片描述](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-f7a3beb8c6154442b247e85920a033e2afb18d3a%2F20200518105613463.png?alt=media) | 会在食物链网络中出现                                                               |
| `Single-input modules`    | ![在这里插入图片描述](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-f95ef4315462dd0b7f1b4175f86292a3c64ce1fa%2F20200518105715975.png?alt=media) | 在基因控制网络中发现                                                               |

与随机网络相比，定义的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-scor`e越高，而标准化处理则可以降低尺度效应的影响。

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

**这里介绍两种方式：**

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

![image-20210215200908931](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-6b6f967aec897e3692f4bd253116851055efab3e%2Fimage-20210215200908931.png?alt=media)

第二种方式称为`Switching`。

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

![image-20210215201548407](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-cb4616dd31acabbf309313b202df2ea3863b3a3a%2Fimage-20210215201548407.png?alt=media)

* 随机选取一条边（例如$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](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-543a56c8ea1c171e5c9b93dc771a53cd55c3a4dc%2Fimage-20210303121818714.png?alt=media)

图元通常会用来比较网络之间的相似和差异。基于图元，来介绍**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](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-5d87b5badba59009ef2b3344dc61377adf68f850%2Fimage-20210303145436906.png?alt=media)

这里有三种不同的轨道（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](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-e12575caf1a83b7c516663be5dca075e19c757db%2Fimage-20210303151012679.png?alt=media)

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

![image-20210303151634302](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-5b7be452246244723768ca4644d5181ecb349755%2Fimage-20210303151634302.png?alt=media)

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

![image-20210303152743233](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-7247df6db84470534d25edb78b4115d8b80bdfcf%2Fimage-20210303152743233.png?alt=media)

将`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](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-d9e1d900027faee948e197855acdb27db83bb6c9%2Fimage-20210303154831462.png?alt=media)

### RolX算法

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

![image-20210303154912057](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-9a3be1824e190f333e967290661120dc7f153a2b%2Fimage-20210303154912057.png?alt=media)

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

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

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

![image-20210303155207916](https://3869347858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsgMO1H1b3FaZhH1L1Rg6%2Fuploads%2Fgit-blob-96e8d3c8dc963fb8c64cc988b3e9d01677547fbe%2Fimage-20210303155207916.png?alt=media)
