上一節課 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)