第3課主要介紹了 子圖的幾個表征參數： motifs， graphlets，structural roles
（1）首先，什麼是子圖？
比如節點數為3的非同構有向圖有13種：
（2）什麼是motifs？ 中文翻譯有 圖案、主題。
解釋：網絡中不斷出現的重要互連模式。其中模式，意味着小的誘導子圖。
注意：誘導子圖是由圖的頂點的子集和連接配接子集中頂點對的所有邊組成的圖。
比如：
這裡的關鍵思想是，不斷出現，意味着比預期的要頻繁。如何定義這個頻繁呢
就是在實際網絡中出現的子圖比在随機網絡中發生的頻率要高得多。 （是否可以了解成某種事件環）
這裡的随機網絡是指 和實際網絡有着相同的 #(nodes), #(edges), #(degree distribution)
這裡的#代表數目。
可以用Z分數進行motif的定義。
motif這個概念的定義：
有向/無向，有顔色/無顔色，變化的/靜止的
motif這個概念的變量：
不同頻率概念，不同重要性名額，欠表達，對于空模型的不同限制
不同網絡的私有motif的Z得分不同。 22/60 ppt
（3）什麼是graphlets：節點級别的特征
graphlets是被非同構子圖連接配接的，進而獲得節點級的子圖衡量名額。
上圖的29的子圖 分别是節點數為2、3、4、5的graphlets。
GDV（graphlet degree vector）是在每個軌道位置具有節點頻率的向量，它計算節點觸摸的graphlet的數量。
GDV可衡量節點的本地網絡拓撲。
舉例如下：
下圖中 a 這個 graphlet 在圖G中圍繞着 節點 v v v 出現的次數為 2次。
GDV的實際意義：
1）計算了 每種graphlet（子圖）在大圖中圍繞着某節點 的數目 #(graphlets)，其中當子圖節點數量為2-5時，覆寫了73種graphlets
2）将其互連捕捉到4跳的距離
3）可衡量本地拓撲網絡
4）比較兩個節點的向量可極大地限制兩個節點之間的局部拓撲相似性
（4）知道了motifs 和 graphlets的定義和計算公式， 那如何對圖進行整體計算呢？
找到大小為k的圖案/小圖需要我們：1）列舉所有大小為k的相連子圖； 2）計算每種子圖類型的出現次數。
僅知道圖中是否存在某個子圖是一個艱巨的計算問題。 而且，計算時間随着主題/小圖的大小增加而呈指數增長。
存在很多算法，本節課隻介紹 ESU算法（Exact subgraph enumeration，2016）
（5）ESU算法 邏輯和示例：
（6）判斷兩個圖是否同構的原則是，是否存在函數f，使得G的相鄰節點u、v變換後，f（u）、f（v）也在圖H的相鄰。
（7）structural roles in network 網絡中的節點角色定義
什麼是角色？ 在網絡中有相同位置的節點集合。
我們可以将角色視為網絡中節點的功能，可以通過結構行為對其進行度量。 注意角色與組/社群不同。 角色基于節點子集之間關系的相似性。 具有相同角色的節點具有相似的結構屬性，但是它們之間不必直接或間接地互動。 組/社群是基于鄰接關系，鄰近性或可達性而形成的，同一社群中的節點之間互相連接配接良好。
什麼是結構等效？
我們說節點u和v在結構上是等效的，如果它們之間具有相同的關系。 結構上等效的節點可能以許多不同的方式相似。 例如，節點u和v在圖4中在結構上等效，因為它們以相同的方式連接配接其他節點。
如：
角色使我們能夠識别網絡中節點的不同屬性。
（8） 如何發現網絡中的節點角色？
在這裡，我們将介紹一種稱為RolX的自動結構角色發現方法。 這是一種沒有先驗知識的無監督學習方法。 圖5是RoIX方法概述。
遞歸特征抽取：
遞歸特征提取的基本思想是聚合節點的特征，并使用它們生成新的遞歸特征。 通過這種方式，我們可以将網絡連接配接變成結構化的功能。
節點的鄰域功能的基本集包括：a. 局部特征，它們都是節點度的度量。 b. Egonet功能是在節點的egonet上計算的，可能包括egonet内邊緣的數量以及進入/離開egonet的邊緣數量。 這裡節點的自我網包括節點本身，其鄰居和這些節點上的誘導子圖中的任何邊。
為了生成遞歸特征，首先我們從節點特征的基本集合開始，然後使用目前節點特征的集合來生成其他特征并重複。 每次遞歸疊代時，可能的遞歸特征的數量呈指數增長。