CS224W 3.2-Motifs and Structural Roles in Networks

上一节课 CS224W 3.1-Motifs and Structural Roles in Networks, 学习到了配置用于对比作用的随机图，

还有一种配置方式

img

• 从一个给定的初始图开始
• 每一步随机挑选一对edges然后改变edge所对应的终止节点
• 重复下去

比如将

img

A-B,C-D改为A-D,C-B（做一个cross）

• 迭代次数（做cross次数）足够多的话可以保证收敛。
• 整个过程所有节点保持不变的degree，但是图变得越来越random

那么我们怎么确定得到的model是一个足够好的model？--取决于你要做什么。

这里我们kept节点个数、边个数等去match真实网络。

现在我们回顾一下找模块的步骤：

img

那么需要生成多少个随机图？---基本上是成千上万，甚至更多（也取决于真实图的大小）

当然对于模块的定义和度量形式也有很多其他的表示方式：

img

Graphlet：node feature vectors

前面学习了模块，用来从局部来窥探整个图的结构，在学习整个图的结构之前，我们现在开始看看一个节点周围(neiborhood)网络的结构是什么样的，学习用graphlets来描述节点的特征，描述给定节点周围的网络结构。

什么是graphlet？--连通的非同构子图

• 同构图：如果能够通过重新标记图G的顶点而产生图H，则称两个图G和H是同构图
• 可以理解为两个图之间存在双向映射
• 如果两个图是同构的，不取决于两个图是怎么画的，也不取决于如何标记顶点。
• 图G和H是同构的，那么它们的阶相同，大小相同，各顶点度数也对应相同
• 可以理解edges是具有弹性的绳子，同构表示，节点固定，对G“扯一扯”绳子即可变换成H#

img

我们用graphlets来作为一个在节点层面的子图度量

我们回顾一下什么是degree

degree是一个节点上的边的个数

现在把degree的概念推广到graphlets上--graphlet degree vector：一个节点touch的graphlets的个数。

graphlets考虑的是连通的非同构子图，非同构指的是不同子图之间的关系，但是我们要考虑子图自身的性质--自同构

自同构可以视为图G和G的同构

最初等的理解：对称

img

• 看上图中给定节点v，v所touch的子图为形式a的有两个，b的有一个，注意到c是0个（因为G中节点之间是连接的，并不像c这样），将v作为d节点的子图有两个
• 所以graphlet度向量表示的是给定节点touch的给定轨迹的子图个数

现在学习如何找motifs和graphlets

这里涉及两个步骤：（1）列举所有size-k连通的子图 （2）数每一个子图类型出现的次数

look at这两个步骤就可以看出来工作量很大

所以基本上可行的模块(motif)规模是比较小的：3--8

首先看第一步：列举

这里主要介绍exact subgraph enumeration（参见Wernicke2006的paper）

ESU的步骤

这张树结构图很明了的介绍了esu的思想

完成了第一步：列举，下面就是第二步：数每个类型子图出现次数

img

在数个数这一个步骤存在一个问题：如何分类---即要把子图分为不同构的类型（同构的图属于一个类型）---用的是McKay的nauty algorihtm，具体参见以下网站

The nauty Traces pageusers.cecs.anu.edu.au

这节课也提到了同构：

图G和图H是同构的，如果存在双射f，使得在G中相邻的节点在H中也是相邻的。

从定义上看检验两个图是否同构核心在于找到这个映射f，但是实际操作上等于要对每两两节点要去判断，计算量是很大的。

Structural Roles in Networks

这节课的最后一部分：关于roles。

如同在公司里根据每个人的职责和工作性质决定了每个人的角色那么在网络中也需要根据节点的结构表现来决定其角色（role）

img

这里要注意区分role（角色）和group的概念：

• role是根据在network中相似的功能来决定：例如公司中作为测试工程师的每个人，因为做着相似的工作所以扮演相同的role，可是在公司这个network中，这些人不一定互相连接。即role取决于相似性而不是相互连接性
• group/community则是互相连接的个体（节点），核心在于连接性

举个例子：学生、教师这是role，AI实验室、 Info实验室这是group/community

roles和groups是一种互补的概念

img

更正式的描述

结构等价性（structural equivalence)--两个节点称为结构等价的，如果它们和所有其他节点都有着相同的关系

这是从社会网络中引用过来的一个概念

img

发现网络中的结构角色(roles)

为什么roles重要？下图给了很详细的说明

img

那么怎么去发现网络中的roles？这里介绍RoIX

RoIX是一种无监督学习方式来自动探测网络中节点的结构角色，具备以下优点：

• 无需先验信息
• 给每个节点分配a mixed-membership of roles

img

根据上图来分析

• step 1：输入节点信息
• step 2: 递归特征提取
• step 3: 得到节点特征矩阵（例如度、平均权重等）
• step 4: 提取role
• step 5: 输出节点角色矩阵和角色特征矩阵

下图展示了输入和输出

img

那么要重点讲解的就是第二步的递归特征提取和第四步的角色提取

（1） 递归特征提取(recursive feature extraction)