本节开篇从subgraph出发，指出subgraph是一个非常重要的概念，能够描述一个network的特征。于是，顺水推舟地讲解了两个利用到subgraph的度量指标：motifs and graphlets；
最后又讲解了如何提取network中每个node的structural roles；
但是很奇怪的是老师似乎并未将
motifs，graphlets和structural roles之间的联系讲解清楚🤔
前导知识：Subnetworks
概念及其研究意义
- 你可以想象一个network是像搭乐高一样，由一个一个subnetworks搭起来的。
- 从小至大的思想（或者称为分解思想）：
较大的问题=若干个小问题之和，
较难的问题=若干个简单的子问题之和
如同乐高- subgraph的好处在于能够刻画和区分网络，所以它是十分有用的，这也是这节课的出发点所在。后面讲的
motif和graphlet都是基于subgraph的！！！
Example
non-isomorphic：非同构的
Subgraphs’ Significance
我们接下来会给每种类型的子图赋予上一个值，这个值刻画了这个子图在这个图中的重要性：
在上图中：
- 横坐标是前面提到的13个subgraph；
- 纵坐标是significance profile，比如对于第一个subgraph，它在Language networks是over-representation（表现充足），而在Web and social是under-representation（表现不足）；
- 右边表示的是在对应domain里面选择不同的networks，可以发现只要是在相同的domain里面，即使是不同的networks也表现出大致相同的significance profile。
通过上面的例子，我们知道subgraph及其significance是非常重要的，那么如何计算significance呢？接下来我们来学习如何去计算significance。
下图是这节课的安排：
首先给出两个notion——motifs和graphlets，然后利用这两个notion来得到structural roles of nodes，最后讲解structural roles 的应用~
Motifs
motif的中文意思是模块
What is Motifs？
- 网络主题(Motifs)是网络中反复出现的重要的连接模式（recurring, significant patterns of interconnections ）（有点抽象~）
- 从上面的定义中，我们可以抽取3个重要部分：
Pattern：指induced subgraph，也就是离散数学中学的导出子图~Recurring：意味着出现的频率很高；Significant：这是一个通过比较出来的概念，需要一些图模型作为baseline~- 随机图的概念再次出现，后续可以发现随机图给我们研究现实网络提供了一个很好的参照作用
Why Do We Need Motifs？
motif的用途：
- 弄明白网络如何工作；
- 在给定情境下预测网络的操作和反应
上图中展示了几种不同类型的motifs：
- Feed-forward loops ：老师说有点像ResNet中的skip connection
- Parallel loops：在food web中发现的，说明这个motif在food web中是非常常见的！
- Single-input modules：在基因控制网络中发现的，说明它在其中非常重要！
Pattern: induced subgraph
下面讲解一下啥叫induced subgraph：
首先，我们事先定义了我们想要研究的一个motif——aka motif，然后在图中寻找，寻找的方式严格按照导出子图来定义：
Recurrence
最重要的概念是允许overlap
Significance
下图再次说明了significance的出现就是一个比较的概念！！！：
从上图中可以看出，在real network中feed-forward loop是比randomized networks更加over-representation的！
既然说到significance是通过和随机图的对比来看出现频率的，那么如何转换为数学语言来表示这个significance？
接下来是计算significance的算法：
Significance计算方法📊
首先是计算z-score^1：
z-score：# of $\sigma$s from $\mu$ for a particular data point.
- 这个$SP_i$的公式是人为定义的，不必过于纠结。
- 注意$SP_i$的作用~这是算法继z-score后的第二次normalized！
现在还有一个问题就是randomized networks是怎么生成的？
怎么生成Randomized Networks？
在第2节课中，我们学习了Erdös-Rényi随机图模型（我们知道这个随机图模型与现实中的网络还是有所差别的），所以我们想能不能认为对这个随机图加一些限制，使其更能够模拟现实网络的模型？
我们想增加的限制有：
- $G^{rand}$具有和$G^{real}$相同点的数量
- $G^{rand}$具有和$G^{real}$相同边的数量
- $G^{rand}$中每个点具有和$G^{real}$相同的度数
Algorithm 1
- steps：
- 给定节点和其“触角”
- 随机配对
- 产生图
- 注意上面的操作过程，最后的图中B只有3个度，老师说实验证明，这样的噪声结果不会太影响实验效果！即
ignore double edges and self-loops对实验结果没影响！
Algorithm 2
接下来是另外一种生成随机图的方法：
其实就是一个
cross的操作~如果做了很多次这样的cross操作，那么就能够生成random graph。老师说
cross是操作非常耗时的，cross操作的起点是原图。其实建模随机图主要看你的问题是什么，老师说他这里只是考虑了度，你当然可以考虑更多，只要你认为是有意义的即可！
上图使用的是switching的方式生成的random graph。
Motif小节
那么需要生成多少个随机图？—基本上是成千上万，甚至更多（也取决于真实图的大小）
其实motif是一个研究甚多的领域，比如它的定义就有很多的变体：
- canonical definition：规范定义
skip this：
Graphlets
接下来讲解motif的一个扩展——graphlets。
motif和graphlet的联系：
- 我们使用
motif来描述一个图； - 而我们使用
graphlets来描述每一个node；
也就是说我们之前在讨论整个network的性质，现在我们讨论每个node的性质，主要的考虑是每个node的neighborhood。
Graphlet：连通的非同构子图
在上图中，注意其中的标号，每个标号代表一个新的点的位置，即后面会提到的
orbit！graphlet同样是induced subgraph
结合上图，我们的研究点就是：
如果我现在是一个node，那么我就要想，我在哪个graphlets上呀，我在哪个graphlets的哪个位置上呢？
Graphlet Degree Vector（GDV）
之前我们用motif得到了一个度量指标——significance，现在我们用graphlets来作为一个在节点层面的子图度量。
- graphlets的作用就是作为计算
node-level subgraph metric的输入。 - 通过类比Degree，得到Graphlet degree vector的概念：
- degree是一个节点上的边的个数
- 一个节点touch的graphlets的个数
注意是导出子图！！！
所以graphlet度向量表示的是给定节点touch的给定轨迹的子图个数：
1个73维的向量，实际描述的是1个node的邻居信息。
现在学习如何找motifs和graphlets：
Finding Motifs and Graphlets
这里涉及两个步骤：
（1）列举所有size-k连通的子图
（2）数每一个子图类型出现的次数
look at这两个步骤就可以看出来工作量很大
所以基本上可行的模块(motif)规模是比较小的：3–8
Counting Subgraphs——ESU
我们讲解ESU（exact subgraph enumeration）
id大的原因在于不想重复之前产生的subgraph
be neighbored to some newly added node的原因也是为了不做重复的事情！
主要还是看下面的图说话：
如何counting呢？步骤如下：
bijection：双射
在数个数这一个步骤存在一个问题：如何分类—即要把子图分为不同构的类型（同构的图属于一个类型）—用的是McKay的nauty algorihtm，具体参见以下网站
https://link.zhihu.com/?target=http%3A//users.cecs.anu.edu.au/~bdm/nauty/
图G和图H是同构的，如果存在双射f，使得在G中相邻的节点在H中也是相邻的。
从定义上看检验两个图是否同构核心在于找到这个映射f，但是实际操作上等于要对每两两节点要去判断，计算量是很大的。
Structural roles in networks
What are Roles？
关于role这个idea的来源也是来自于我们的生活的：
在接下来的讲解中，我们主要考虑3中role：
- center of stars： Are you a center of a star？
- member of cliques： Are you a member of fully connected graph？
- peripheral nodes：是否是外围节点？
一个无向图的一个派系是指：这个无向图的顶点集有这样一个子顶点集，子顶点集里的任意两个顶点都有一条边相连（也即子顶点集中的任意两个顶点都是相邻的），那么这个子顶点集及其边构成的图就是这个无向图的一个派系。如果这个派系的顶点有k个，就称这个派系为k-派系（k-clique）。
其实也就是一个无向图里的一个子完全图就是这个无向图的一个派系。
我们首先来区分一下role和groups，虽然它们都是集合，但是它们还是有很大区别的！
这里要注意区分role（角色）和group的概念：
- role是根据在network中相似的功能来决定：例如公司中作为测试工程师的每个人，因为做着相似的工作所以扮演相同的role，可是在公司这个network中，这些人不一定互相连接。即role取决于相似性而不是相互连接性
- group/community则是互相连接的个体（节点），核心在于连接性
举个例子：学生、教师这是role，AI实验室、 Info实验室这是group/community
roles和groups是一种互补的概念
结构等价性（structural equivalence)——两个节点称为结构等价的，如果它们和所有其他节点都有着相同的关系
这是从社会网络中引用过来的一个概念
上面的定义很严格，要求的是all other nodes，必须要一模一样的nodes关系！
RolX
那么怎么去发现网络中的roles？这里介绍RoIX
RoIX是一种无监督学习方式来自动探测网络中节点的结构角色，具备以下优点：
- 无需先验信息
- 给每个节点分配a mixed-membership of roles（这个的最终体现就是一个概率分布）
根据上图来分析：
step 1：输入节点信息
step 2: 递归特征提取
step 3: 得到节点特征矩阵（例如度、平均权重等）
step 4: 提取role
step 5: 输出节点角色矩阵和角色特征矩阵
Recursive Feature Extraction
这里的
feature列自左到右，所summarize的范围越来越大！local->egonet->recursiveegonet的定义：ego network is simply if u have a node it’s a network composed of the node its neighbors and the edges between them.
具体的思想和算法如下：
递归特征提取的基本思想是聚合节点的特征，并使用它们生成新的递归特征。通过这种方式，我们可以将网络连接变成结构化的功能。
节点的邻域特征的基本集合包括：
- 局部特征，它们都是节点度的度量。
- Egonet功能是在节点的egonet上计算的，可能包括在egonet内的边数量以及进入/离开egonet的边数量。这里节点的egonet包括节点本身，其邻居和这些节点上的诱导子图中的任何边。
- 为了生成递归特征，首先我们从节点特征的基本集合开始，然后使用当前节点特征的集合来生成其他特征并迭代此操作。每次递归迭代时，可能的递归特征的数量呈指数增长。
- graphlet degree vector也可以作为feature
Role Extraction
RoleX使用的聚类算法是
non-negative matrix factorization，这个算法老师在之后的课程会讲解。
Application：Structural Similarity
注意得到的是一个distribution！
Gray rectangle是排除其他三种节点之后的任意节点。
