近期读论文，进入到了子图学习的分支里。

我们试图区分三个概念。subgraph, graphlet, and motifs.

Subgraph子图

例子：3个节点的有向子图的不同形态

对于每一个subgraph：

    假设我们有一度量工具可以用于对subgraph的表示效果进行评估：

       负值表示under-representation 

       正值表示over-representation

何谓motif？ 图中反复出现的相互连接的模式，有以下三个特点：

- Pattern：小的能导出的子图；

- Recurring：频繁出现；

- Significant：模式的出现明显高于预期，如类似的random genderated networks中的模式；

为什么需要Motifs？

• 帮助我们理解网络如何工作

• 特定情况下预测网络

Motif: Induced Subgraphs

Induced Subgraph如下图所示，图中红色框虽然也是3个节点构成的子图，但是该子图与待匹配的子图不匹配（连接不一致），而蓝色的三角框中的子图与待匹配的子图匹配， 匹配的意思是指必须是出现在待匹配子图里所有节点的边，如果不是待匹配节点之间的边，则不匹配；

Motifs: Recurrence

如下图，右侧图中出现了4个待匹配的motif，motif之间可以相互重叠；

Motif： Significance

如下图， 该motif在真实的网络中出现的频率要对类似的随机网络出现的频率要高的多， 我们成为其显著性明显；

显著性通常是和随机性网络做对比，通常使用 来描述motif i的显著性， 其中  表示真实网络中motif i的数量，  表示在随机网络中motif i的数量：

上面的计算会随着网络规模的不同而有数值的变化，而大的网络会倾向于有更大的Z-score， 归一化处理之后，使用Net significance profile来表示，motif i的SP计算公式如下：

Configuration Model

配置一个和真实网络相同的度序列的随机图可以分为三步：

1. 按节点的度序列生成Node spokes；

2. 随机从nodes spokes中挑选两个连接起来；

3. 根据源节点和目标节点，将步骤2中聚合起来，即形成和真实网络相同度序列的随机网络；

Alternative for Spokes: Switching

另一个产生于源图类似的图的方法就是随机做边交换，具体步骤如下：

1. 从源图中随机找出边如，A->B, C->D，随机交换边的终点产生边A->D, C->B， 如果交换导致自己指向自己，则不交换；

2. 重复1中，Q次， 当Q足够大时，即可生成随机图；

本节总结

经过上面的定义与解释之后，我们就可以定义如何检测一个motif：

1. 在真实图中，统计induced subgraph的个数；

2. 统计生成的随机网络中的induced subgraph的个数， 这里随机生成的网络，可以生成多个做对比；

3. 计算Z-score， 那些高的Z-score就是我们需要的motif；

motif也有相应的变种， 如不同的频率概念、不同的显著性计算标准、null model的不同约束等等，但基本上都是万变不离其宗；

Graphlets: Node Feature Vectors

Graphlets是对motif的扩展，motif是从全局的角度来描述图的，全局的图有哪些motif，而Graphlet是从局部(节点)的角度出发来描述，关注这个节点和它邻居的情况，利用局部信息来对每个节点表示。

如下图所示，为n=2,3,4时的graphlets，其中编号代表第几类节点。比如说，当n=2时，有1个graphlets，只有一类节点0，两个节点是同构的。n=3时，有两个graphlets，对应三种节点，  中有节点1，2，最下面的节点等价于节点1，在图  中三个节点都是等价的。n=4时，有6个graphlets，11种节点，比如在  中有两类节点，节点7有三个邻居，而剩余三个节点同构，都可认为是节点6。可以看出Graphlet也是一种子图，但是更关注局部节点的性质。

怎样表示Graphlet中的节点呢？

可以利用Graphlet Degree Vector(GDV)，描述节点的“orbit”（轨迹），节点表示向量中的每个值对应的这一类节点出现的次数。如下图所示，对于图G，我们假定用节点个数为2，3的graphlet表示（即上图的  ) ，有4类节点abcd（分别对应上图中的0321节点），我们要对节点v表示，a类型出现了2次，即vx,vy，b类型出现了1次，即vxy，c类型没有出现过，注意在vxy中不能算作c类型，因为在c类型对应的graphlet中，下面并没有边相连，即vxy不可以看作是  的子图，d类型出现了两次，即vxz,vyw，所以节点 v的表示为：

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

Exact Subgraph Enumeration

ESU从一个节点 开始，算法分为两个集合：  :表示当前构造的子图， ：表示能够扩展motif的候选节点， 将满足以下两个条件的节点 加入到  ：

1.  的节点id要大于v的id；

2.  只能是新加入加点 的邻居，而不能是  里的节点邻居；

伪代码逻辑如下：

拼接自如下文章：

https://www.cnblogs.com/combfish/p/12271464.html

https://zhuanlan.zhihu.com/p/261418085

https://zhuanlan.zhihu.com/p/138560010

【斯坦福CS224W 图与机器学习 3】：Motifs and Structural Roles in Networks http://web.stanford.edu/class/cs224w/slides/03-motifs.pdf