課程三主要是講解了圖的組成部分的定義，這些部分的性質(zhì)，以及由此產(chǎn)生的對(duì)圖的結(jié)構(gòu)化的定性的影響。主要內(nèi)容包括：
- 子圖(subgraph)及其性質(zhì)
- Motif及其性質(zhì)
- Graphlet及其性質(zhì)
- 檢測(cè)Motif和Graphlet的算法，及其應(yīng)用
- 節(jié)點(diǎn)的結(jié)構(gòu)角色(Structure Role)——RolX算法。
對(duì)于5種不同的網(wǎng)絡(luò)的子圖顯著性的比較，可以發(fā)現(xiàn)：相同領(lǐng)域的子圖顯著性特征向量具有相同的模式(pattern)（例如來(lái)自不同生物的神經(jīng)元網(wǎng)絡(luò)），不同領(lǐng)域的圖則有著明顯不同的子圖顯著性特征向量，且來(lái)自相同領(lǐng)域的不同圖的子圖顯著性特征向量的相似度也更高。從而表明了對(duì)子圖顯著性的研究可以幫助對(duì)圖進(jìn)行定性和區(qū)分。
Motif
recurring, significant patterns of interconnections
為什么要研究motif ？
- Help us understand how networks work
- Help us predict operation and reaction of the network in a given situation
pattern:small induced subgraph
導(dǎo)出子圖:V' 屬于 V， E'就是在原圖中V'這幾個(gè)點(diǎn)連在一起的邊
recurrence：Found many times, i.e., with high frequency
這個(gè)模式出現(xiàn)了很多次, 并且motif之間允許存在公共節(jié)點(diǎn)。
significance：Subgraphs that occur in a real network much more often than in a random network have functional significance
這個(gè)pattern在源圖中出現(xiàn)的次數(shù)要比在類(lèi)似的隨機(jī)網(wǎng)絡(luò)中出現(xiàn)的次數(shù)要多的多的多（隨機(jī)網(wǎng)絡(luò)可以有成千上萬(wàn)個(gè)）
我們?cè)鯓尤ビ?jì)算這個(gè)significance（顯著性）呢？設(shè) (取絕對(duì)值高的)表示
顯著性。
-
is #(subgraphs of type ??) in network
-
is #(subgraphs of type ??) in randomized network
Network significance profile (SP): 經(jīng)過(guò)標(biāo)準(zhǔn)化后
總結(jié)一下上面的內(nèi)容：
關(guān)于Motifs也有很多其他形式表示的定義：
生成隨機(jī)網(wǎng)絡(luò)的兩種方式
- Configurantion Model
- Switching
Graphlets
Graphlets(圖元，connected non-isomorphic subgraphs)是指大規(guī)模網(wǎng)絡(luò)中那些節(jié)點(diǎn)數(shù)目較少的連通導(dǎo)出子圖（非同構(gòu)）。
Graphlet degree vector
- Graphlet degree vector counts #(graphlets) that anode touches at a particular orbit
- Graphlet degree vector counts #(graphlets) that a node touches
例子：
我們有三種不同的軌道（orbit），軌道上有a、b、c、d四種節(jié)點(diǎn)位置（orbit position，圖6中節(jié)點(diǎn)旁邊標(biāo)的數(shù)字）。對(duì)于節(jié)點(diǎn)v來(lái)說(shuō)，其在軌道位置a上有2個(gè)圖元，在軌道位置b上有1個(gè)圖元，在軌道位置c上沒(méi)有圖元，在軌道位置d上有2個(gè)圖元。這里需要注意的是圖元是導(dǎo)出子圖。
例如把V節(jié)點(diǎn)放在c的位置，而在原圖中 這個(gè)圖不是導(dǎo)出子圖，故圖元為0.
對(duì)于GDV的理解是：它提供了對(duì)于一個(gè)節(jié)點(diǎn)的本地網(wǎng)絡(luò)拓?fù)涞亩攘浚@樣可以比較兩個(gè)節(jié)點(diǎn)的GDV來(lái)度量它們的相似度。由于Graphlet的數(shù)量隨著節(jié)點(diǎn)的增加可以很快變得非常大，所以一般會(huì)選擇2-5個(gè)節(jié)點(diǎn)的Graphlet來(lái)標(biāo)識(shí)一個(gè)節(jié)點(diǎn)的GDV。
搜索motifs和graphlets的算法:Exact subgraph enumeration(ESU)
ESU算法的偽代碼如下：
按照上面的思路，ESU算法采用遞歸的方式計(jì)算。構(gòu)成遞歸的樹(shù)型數(shù)據(jù)結(jié)構(gòu)叫做ESU-Tree:
對(duì)找到的子圖進(jìn)行統(tǒng)計(jì)：Count the graphs
將ESU樹(shù)葉子節(jié)點(diǎn)上的子圖分成不同構(gòu)的各種類(lèi)別。這里涉及到怎么判斷圖之間是否同構(gòu)，采用的是McKay的方法。
網(wǎng)絡(luò)里節(jié)點(diǎn)的結(jié)構(gòu)角色(Structural Roles)
區(qū)別Role和Group/Communities:
- role是指在網(wǎng)絡(luò)中具有相似功能的節(jié)點(diǎn)：例如不同項(xiàng)目組中的研究員，這些研究員在網(wǎng)絡(luò)中可能并沒(méi)有連接（互不認(rèn)識(shí)），但他們從事同樣的一份工作。即role取決于相似性而不是相互連接性。
- group/community則是互相連接的個(gè)體（節(jié)點(diǎn)），核心在于連接性。
我們來(lái)給role一個(gè)更嚴(yán)謹(jǐn)?shù)亩x。屬于相同role的節(jié)點(diǎn)具有結(jié)構(gòu)等價(jià)性（structural equivalence）——Nodes u and v are structurally equivalent if they have the same relationships to all other nodes.
Discovering Structural Role in Networks
Why are Roles important?
搜索Role的算法(RolX)
RolX: Automatic discoveryof nodes’ structural roles in networks
- Unsupervised learning approach 無(wú)監(jiān)督學(xué)習(xí)方法
- No prior knowledge required 不需要任何先驗(yàn)知識(shí)
- Assigns a mixed-membership of roles to each node 為每個(gè)節(jié)點(diǎn)分配角色的混合成員關(guān)系
- Scales linearly in #(edges) 算法的復(fù)雜度隨著網(wǎng)絡(luò)中的邊的數(shù)量線性增長(zhǎng)
Rolx算法流程(以后再理解吧）：
