目录
引入
Subgraphs
Network motifs
1.定义
2. 检测motifs
3.motifs 概念的变体
graphlets
如何找到modifs与graphlets
引入
Subnetworks是构建网络的模块，它们可以表征网络的结构与区分不同的网络。
下图中的子图是(每一个和其他的都不同)异构的，且都是连通的、有不同数量的边、边的方向不同
1.对于每一个子图：想象有一个矩阵可以区分子图的”significance“
- 负值表明 under-representation
- 正值表明 over-representation
2.创建一个network significance profile
是一个具有所有子图significance值的feature vector
3.通过比较network significance profile区分不同的图
从图中可以看出来自相同领域的网络有相似的significance profile；不同领域的significance profile值不同
Subgraphs
Network motifs
1.定义
network motifs:
- pattern：小的诱导子图(图 G 的诱导子图是由图 G 的顶点的子集 X 和连接子集 X 中顶点对的所有边组成的图。)
- Recurring:出现的频率很高
- Significant:比预期出现的更频繁(预期是指和null model相比，最简单的null model可能就是ER随机图等，但更好的是和图中的度数保持一致)
（1)pattern小的诱导子图：
图中红色三角形里不是motifs因为它不是诱导子图
(2)Recurrence:
允许重叠的overlapping motifs,图中感兴趣的motif有四次occurrences
(3)Significance
(3.1)思想：在真实世界中比随机网络中出现更频繁的子图有功能significance
图中的motif在真是网络中出现比随机图中出现频繁——overprep're'se
(3.2)计算significance
- Motifs在真实网络和随机网络(null model)相比是overrepresented
定义了统计意义的motif i的重要性
SP是一个归一化的Z-scores向量，为什么归一化？因为SP强调了子图的相对significance：
比较不同规模网络的importance，通常网络规模越大Z-score的分数越大(则比较两个网络的significance不知道是因为本来motifs频率大还是网络规模大)
- Configuration Model——在计算significance时如何构造null model(零模型)
- 构造方法一：随机连接
构造出与真实网络有相同degree sequence的null model
忽略随机连节点对时可能出现double边或self-loops，虽然可能产生degree sequence不同了，但当网络规模很大时，可以近似相等。
- 构造方法二：随机交叉
随机选择一对边，然后重连两个边，交叉两个点。 生的随机图的节点的度，不发生改变。但计算的代价会较高，运行慢。 为了保证随机图的随机性，需要运行的次数为 Q * E 次，其中Q应尽可能的大，如100。
2. 检测motifs
- 计算真实网络中子图i
- 计算构造的随机图中子图i(有多个随机图，每个随机图和真实网络有i谢娜沟通的节点边数和度分布)
- 计算Z-score，进一步归一化为SP,得分高的为网络的modif
3.motifs 概念的变体
graphlets
motifs是描述整个网络，整个网络有什么组成
graphlets是在一个给定节点周围描述整个网络
graphlets：rooted(基于给定节点)连通的异构子图与motifs区分
引入GDV：计算一个节点参与的小图的数量
GDV——是一个根植于给定节点的子图的数量向量
因为graphlets是诱导子图( induced subgraph 节点的所有连接都要包含在内)，所以节点在位置c不行，另两个节点必须要连接。
GDV提供了一种测量节点局部网络拓扑的方法，通过比较两个节点的GDV提供了一种比node degree和聚类系数更细节的测量局部拓扑相似性的方法。
如何找到modifs与graphlets
- 困难
找到size-k的modifs/graphlets需要解决两个挑战：枚举与计数。这两个计算很困难，计算时间久，因此只能找到小型的modifs/graphlets
- 使用ESU枚举所有k-size modifs/graphlets
- Use ESU-Tree to Count Subgraphs
