2.1 圖統(tǒng)計(jì)和核方法

2.1.1 節(jié)點(diǎn)層次的統(tǒng)計(jì)和特征

節(jié)點(diǎn)的度

$$d_u=\sum _{v\in \mathcal{V}}A(u,v)\text{\hspace{1em}(2.1)}$$

需要說明的是，在有向和加權(quán)圖中，度可以區(qū)分為不同的概念。例如入度和出度之類的。不管怎么說，這個(gè)特征在傳統(tǒng)機(jī)器學(xué)習(xí)中都是十分重要的。

節(jié)點(diǎn)中心度

$$e_u=\frac{1}{\lambda }\sum _{v\in \mathcal{V}}A(u,v)e_v,?u\in \mathcal{V}\text{\hspace{1em}(2.2)}$$

一種常見的方式是利用特征向量中心度，我們定義每個(gè)節(jié)點(diǎn)的中心度為周圍所有中心度的均值，其中$\lambda$是一個(gè)常數(shù)。

求解這一過程，可以寫作如下形式：$$\lambda e=Ae\text{\hspace{1em}(2.3)}$$
如果我們期望所有的中心度都是正的，我們可以應(yīng)用Perron-Frobenius Theorem，即對(duì)A求解特征向量。
此外我們也可以通過迭代法如下：$$e^{(t+1)}=A{e}^{(t)}\text{\hspace{1em}(2.4)}$$

如果我們?cè)O(shè)$e^0=(1,1,...,1{)}^T$那么每次迭代后的結(jié)果是截至T步時(shí)，經(jīng)過的次數(shù)，由此可以得到重要性。

聚類系數(shù)

用于衡量節(jié)點(diǎn)局部鄰域封閉三角形的比例。

$$c_u=\frac{|(v_1,v_2)\in \mathcal{E}:v_1,v_2\in \mathcal{N}(u)|}{C_{d_u}^2}\text{\hspace{1em}(2.5)}$$
其中 N ( u ) = { v ∈ V : ( u , v ) ∈ E } \mathcal{N}(u)=\{v\in \mathcal{V}:(u,v)\in \mathcal{E}\} N(u)={v∈V:(u,v)∈E}也就是所有的相鄰節(jié)點(diǎn)構(gòu)成的集合。

這一特征描述了節(jié)點(diǎn)附近結(jié)構(gòu)的緊密程度。

Closed Triangles, Ego Graphs, and Motifs

略

圖層次的特征和圖的核

節(jié)點(diǎn)袋

單純綜合節(jié)點(diǎn)的特征。

Weisfieler–Lehman核

一種迭代鄰域聚合方法。

Graphlets和基于路徑的方法

Graphlets：計(jì)算不同子圖結(jié)構(gòu)出現(xiàn)次數(shù)。具體方式為，枚舉所有可能的子圖結(jié)構(gòu)，然后統(tǒng)計(jì)出現(xiàn)的次數(shù)。

基于路徑，則是統(tǒng)計(jì)類似于最短路之類的。

鄰域重疊檢測(cè)

未完待續(xù)。