第三课-网络中的主题(motif)和结构角色

课程三主要是讲解了图的组成部分的定义，这些部分的性质，以及由此产生的对图的结构化的定性的影响。主要内容包括：

子图(subgraph)及其性质
Motif及其性质
Graphlet及其性质
检测Motif和Graphlet的算法，及其应用
节点的结构角色(Structure Role)——RolX算法。

对于5种不同的网络的子图显著性的比较，可以发现：相同领域的子图显著性特征向量具有相同的模式(pattern)（例如来自不同生物的神经元网络），不同领域的图则有着明显不同的子图显著性特征向量，且来自相同领域的不同图的子图显著性特征向量的相似度也更高。从而表明了对子图显著性的研究可以帮助对图进行定性和区分。

significance profiles.PNG

Motif

recurring, significant patterns of interconnections

为什么要研究motif ？

Help us understand how networks work
Help us predict operation and reaction of the network in a given situation

pattern:small induced subgraph

导出子图:V' 属于 V， E'就是在原图中V'这几个点连在一起的边

2.PNG

recurrence：Found many times, i.e., with high frequency

这个模式出现了很多次, 并且motif之间允许存在公共节点。

recurrence.PNG

significance：Subgraphs that occur in a real network much more often than in a random network have functional significance

这个pattern在源图中出现的次数要比在类似的随机网络中出现的次数要多的多的多（随机网络可以有成千上万个）

我们怎样去计算这个significance（显著性）呢？设 $Z_i$ (取绝对值高的)表示 $motif_i$ 显著性。

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

$N_i^{real}$ is #(subgraphs of type 𝑖) in network $G^{real}$
$N_i^{rand}$ is #(subgraphs of type 𝑖) in randomized network $G^{rand}$

Network significance profile (SP): $Z_i$ 经过标准化后
$SP_i=Z_i/\sqrt{\sum_{j=1}Z_j^2}$

总结一下上面的内容：

z-score.PNG

关于Motifs也有很多其他形式表示的定义：

motif.PNG

生成随机网络的两种方式

Configurantion Model
Switching

Graphlets

Graphlets(图元，connected non-isomorphic subgraphs)是指大规模网络中那些节点数目较少的连通导出子图（非同构）。

6.png

Graphlet degree vector

Graphlet degree vector counts #(graphlets) that anode touches at a particular orbit
Graphlet degree vector counts #(graphlets) that a node touches

例子：

7.png

我们有三种不同的轨道（orbit），轨道上有a、b、c、d四种节点位置（orbit position，图6中节点旁边标的数字）。对于节点v来说，其在轨道位置a上有2个图元，在轨道位置b上有1个图元，在轨道位置c上没有图元，在轨道位置d上有2个图元。这里需要注意的是图元是导出子图。

例如把V节点放在c的位置，而在原图中这个图不是导出子图，故图元为0.

对于GDV的理解是：它提供了对于一个节点的本地网络拓扑的度量，这样可以比较两个节点的GDV来度量它们的相似度。由于Graphlet的数量随着节点的增加可以很快变得非常大，所以一般会选择2-5个节点的Graphlet来标识一个节点的GDV。

搜索motifs和graphlets的算法:Exact subgraph enumeration(ESU)

ESU算法的伪代码如下：

8.png

按照上面的思路，ESU算法采用递归的方式计算。构成递归的树型数据结构叫做ESU-Tree:

ESU.PNG

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

10.png

将ESU树叶子节点上的子图分成不同构的各种类别。这里涉及到怎么判断图之间是否同构，采用的是McKay的方法。

网络里节点的结构角色(Structural Roles)

区别Role和Group/Communities:

role是指在网络中具有相似功能的节点：例如不同项目组中的研究员，这些研究员在网络中可能并没有连接（互不认识），但他们从事同样的一份工作。即role取决于相似性而不是相互连接性。
group/community则是互相连接的个体（节点），核心在于连接性。

我们来给role一个更严谨的定义。属于相同role的节点具有结构等价性（structural equivalence）——Nodes u and v are structurally equivalent if they have the same relationships to all other nodes.

Discovering Structural Role in Networks

Why are Roles important?

11.png

搜索Role的算法(RolX)

RolX: Automatic discoveryof nodes’ structural roles in networks

Unsupervised learning approach 无监督学习方法
No prior knowledge required 不需要任何先验知识
Assigns a mixed-membership of roles to each node 为每个节点分配角色的混合成员关系
Scales linearly in #(edges) 算法的复杂度随着网络中的边的数量线性增长

12.png

Rolx算法流程(以后再理解吧）：

13.png