CS224W 3.1-Motifs and Structural Roles in Networks

这部分开始讲网络中的模块(motifs)和结构性角色，首先介绍模块。

在此课之前有一个实践课，关于snappy的用途，具体参照以下这个文件就讲述的很详细了

http://web.stanford.edu/class/cs224w/slides/CS224W-snappy-tutorial.pdfweb.stanford.edu

• 子网络（用来刻画和区别网络）

从小至大的思想（或者称为分解思想）：较大的问题=若干个小问题之和，较难的问题=若干个简单的子问题之和如同乐高 举个简单例子，当有三个节点的时候，会有以下可能的子图：

这里考虑了有向图 子图的概念是很容易理解，那么我们需要什么样的子图？很自然的想法是--包含能够具有刻画整体图的性质且容易分析

（STEP 1）对于给定degree的所有可能子图，我们需要一个度量能够衡量子图的“重要程度”（正值表示过表示，负值表示欠表示） 感觉这里“表示”展现了子图能够反应整体图的一个表示能力（代表性） （STEP 2）有了这个度量的概念，下面建立一个对所有子图类型的重要程度profile来进行对比 （STEP 3）拿真实的网络来对比不同网络的profile水平 还是前面那个三个节点的例子，下图最下方横坐标表示的是三个节点对应的不同的子图，纵坐标是“重要程度”度量的值，测试了四种不同的网络（每个网络中也选取了不同的case），纵坐标正的值表示过表示，负的对应欠表示

基于这样的步骤，首先来看第一个概念： 模块(MOTIF) 定义：网络模块是指反复出现的重要的连接模式（recurring, significant patterns of interconnections ） 这里有几个关键词：模式（pattern)、反复出现(recurring)、重要的(significant) pattern意味着小的诱导的子图--给定了节点，“诱导”表示节点之间的连接都包含在内 recurring意味着出现的频率很高 significant---相比随机图，出现的频率更高 随机图再次出现后续可以发现随机图给我们研究现实网络提供了一个很好的参照作用 用途：模块的用途比较显然--（1）弄明白网络如何工作（2）在给定情境下预测网络的操作和反应

这里值得注意的是，“诱导”包含节点的连接，如下图的例子

红色的子图不匹配就是因为连接的edges不对。 既然说到significance是通过和随机图的对比来看出现频率的，那么如何转换为数学语言来表示这个significance？

这里用到的是对比同样的子图类型下，真实网络和随机网络的出现次数，并且最后做一个正态化。（如果不对比，仅仅看出现次数，有些网络非常的大且密度很高，可是其实某个子图并不具有代表性，但是因为图过大，所以这个子图出现次数也能有较大的数字，所以还是要和随机图来进行对比，并且要正态化） 有了这个数学计算公式，就可以知道如何衡量子图的significance，那么在给定了degree的时候如何去配置这个用来做对比的随机图呢？

【注意】（1）为什么不遍历所有的搭配可能性？--因为那样就失去了randomness，我们需要的是随机图 （2）节点B本来有四个“触角”，怎么最后生成的图上只有三个edges？--忽略双边和自环的

• 给定节点和其“触角”
• 随机配对
• 产生图