04-网络中的主题和结构角色
最后更新于
这有帮助吗？
最后更新于
这有帮助吗？
子图(subnetworks/subgraph)是网络的局部组成，可以用来辨别和区分网络。
子图的结构可以有很多种，比如有向图的三节点子图$(n-node subgraphs$，这里$n=3)$就有如下几种形式：
对于一个网络来说，可以得到很多个子图，那么什么样的子图是有意义的呢？这就需要一些参数，来衡量子图的重要性。这样，不同的网络就可以表示为以这些子图为基的特征向量。
对于每个子图:假设有一个能够对子图“重要性”进行分类的度量。
负值表示表示不足
正值表示过度表示
创建一个网络重要性概要:具有所有子图类型值的特征向量
接下来:比较不同网络的概况:
调控网络(基因调控)
神经元网络(突触连接)
万维网(网页间超连结)
社交网络(友谊)
首先看这张图最底下，横坐标，是前面讲到的13种子图的类型，上面的每一行就是不同网络关于这13种子图的一些特征值。可以看到，同领域的网络，它的特征向量其实是相似的。比如最后一行的语言网络，对于英语、发育、西班牙语、日语等不同的语言来说，他们尽管语法不尽相同、词语不同，但是它们的特征是一致的。
网络主题Network motifs：反复出现的，重要的相互联系的模式。
如何定义一个网络主题？
pattern ：小结构的子图
recurring：小结构被发现的次数
Significant：在随机网络中比预测的多得多的频率
关键思想：在真实网络中出现的频率要比在随机图中出现的频率要高得多
网络主题的作用：
帮助我们了解网络是如何工作的
帮助我们预测网络在特定情况下的运行和反应
Motifs的一些例子：
Feed-forward loops 前馈环路
这种Motifs会在神经元网络中出现，会用来中和“生物噪音（biological noise）”。（这应该是属于生物信息学中的相关概念）
Parallel loops 平行环路
会在食物链网络中出现
Single-input modules
在基因控制网络中发现
与随机网络相比，定义的motifs在真实网络中出现的频率要比在随机图中出现的频率要高得多。怎样去计算这个significance（显著性）呢？设$Z_i$表示motif $i$的统计显著性。
这里$N_i^{real}$是指在真实网络$G^{real}$中motif$i$出现的次数，$N_i^{rand}$是指在随机网络$G^{rand}$中motif $i$出现的次数。
那么，网络的motif $i$的显著性(Network Significance Profile, SP)由标准化后的$Z_i$表示：
$SP$更强调不同子图之间的相对显著性，这对于不同规模的网络比较十分有意义，因为一般来说网络规模越大，Z-score越高，而标准化处理则可以降低尺度效应的影响。
这里有个问题，就是我们怎么得到随机网络$G^{rand}$呢（Configuration model）？并且这个随机网络需$G^{rand}$要和真实网络有相同的 结点，边以及度分布。
这里介绍两种方式：
第一种方式，我们可以通过给定的节点数量和节点的度序列（degree sequence$ k_1,k_2,\cdots,k_N$）来生成随机图：
第二种方式称为Switching。
我们从一个给定的图开始（这个图和真实的网络有相同的度），重复以下步骤$ Q \cdot |E|$次，$Q$会取一个较大的值（如100）来使整个过程达到收敛：
随机选取一条边（例如$A \rightarrow B$，$C \rightarrow D$）
将边的终点随机改变。注意的是新生成的边不能构成自环或者双边。
获取具有相同节点数，边数，节点度数的随机图之后，就可以计算子图$i$的$Z$值。高值说明该子图是图G的一个Motif。
Graphlets(图元，connected non-isomorphic subgraphs)是指大规模网络中那些节点数目较少的连通诱导子图。且Graphlets反映了网络的局部拓扑，所以它是重要的网络特征。
非同构子图单元，是一类特殊的子图。Graphlets是对motif的扩展。它与motifs的区别：
motif是从全局的角度来描述图的。用不同motifs来构成一个图的向量表示。
而Graphlet是从局部(节点)的角度出发来描述节点。用不同graphlet中的节点相对位置（局部信息），来形成一个节点的向量表示。
图元通常会用来比较网络之间的相似和差异。基于图元，来介绍Graphlet Degree Vector(GDV） 方法。
Graphlet Degree Vector(GDV）方法是Przulj在2003年提出的利用图元及图元向量来刻画网络中节点邻域关系的方法，具体指在小连通非同构子图中计算每个节点的自同构轨道，即每个节点所接触的图形数量。这种方法基于网络拓扑和邻域定义了一系列非同构子图和图向量，用于识别网络中结构相似的模块。——宋祥帅, 杨伏长, 谢江,等. Graphlet Degree Vector方法的优化与并行[J]. 计算机应用, 2020, 40(2):398-403.
Graphlet Degree Vector(GDV）是一个向量，表示每个轨道位置具有该节点的频率。它刻画的是每个节点接触的图元数量。
这里有三种不同的轨道（orbit），轨道上有a、b、c、d四种节点位置（orbit position）。对于节点$v$来说，其在轨道位置a上有2个图元，在轨道位置b上有1个图元，在轨道位置c上没有图元，在轨道位置d上有2个图元。这里需要注意的是图元是诱导子图。
因此，Graphlet Degree Vector(GDV）的实际意义在于：
刻画了某个节点所接触的图元（某个特殊的轨道位置的图元）的数量
刻画了网络中节点的局部属性
可将问题拆解为两步：
枚举所有大小为$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算法的伪代码如下：
该算法通过递归实现的，算法过程可以看做是深为$k$的递归树：
第二步：对找到的子图进行统计：Count the graphs
将ESU树叶子节点上的子图分成k阶不同构的各种类别。这里涉及到怎么判断图之间是否同构，$n$个节点的两个同构图判断，需要$n!$次计算，计算量很大。常用算法的是McKay的方法，即若图G中任意一对邻接的节点$u$ 和$ v $，在图H中都有$f(u)$和$f(v)$邻接，则图$G$和图$H$同构。
通过上面两步可以得到图的 motifs 和 graphlet和对应GDV。
角色是对节点在网络里的功能的描述。角色可以通过测量节点在网络里的结构特征来衡量，比如 星型结构的中心、紧密相连的节点之一、边缘节点等等。
这里要注意的是角色和社区的区别。角色是一些具有相同结构特征的节点，它们不一定是要相互连接的。而社区则是指的一些相互密集连接的节点群所构成的一个元件。
为了正式地定义角色，需要先定义网络里的结构等价：节点$u$和节点$v$ 是结构等价的，如果它们与网络里的所有其他节点有相同的关系。
从上面的定义可以看出，节点的结构等价要求是非常严格的。而这对于无论是计算量还是实际价值都没有太大的意义，所以下面会使用近似的方法，即聚类的方法来找到结构等价的节点，从而得到具有相同结构特征的节点，即角色。
role：在网络中具有相似位置的节点的集合，并且基于节点子集之间关系的相似性。
group/community则是互相连接的个体（节点），核心在于连接性。
属于相同role的节点具有结构等价性
RoIX算法是一个无监督的学习方法，不需要先验知识，能多角色分类，同时可以做到线性扩展。
整个算法过程虽然看着复杂，但是对于有一定机器学习基础的同学来说也很正常。基本是把一个$N \times N$的节点相邻矩阵，按照连接关系提取出节点的特征，转换成$ N \times M$的节点特征矩阵。然后使用特征间的相似度再次计算节点之间的相似性，然后使用层次化的聚类方法把节点按照相似的距离组合成不同的类，相同的类就成为了同一个角色，并最终形成节点角色矩阵和角色特征矩阵。
这里面最核心的部分就是图中红色框的部分：递归特征提取。这里所谓的递归就是指的从一个节点自身开始，获取它自己的本地的特征，并聚合起来，比如mean和sum它们。随后从这个节点扩展到本我网络(egonetwork)，即与自己相邻的所有节点以及由它们之间的边构成的子网络。然后再提取这个本我网络里的特征，比如网络的总度、总入度数、总出度数等。按照这个思路，继续迭代下去，对本我网络里的每个节点再提取特征。注意这些迭代提取的特征都还是初始那个节点的特征。
用这种方法可以提取非常多的特征，相当于一个节点一跳(one-hop)和多跳(two, three...-hop)范围的特征。
