图的表示
-
G
r
a
p
h
Graph
Graph的定义
G
=
{
V
,
E
}
G=\{V,E\}
G={V,E}，
V
=
{
v
1
,
.
.
.
,
v
n
}
{V=\{v_1,...,v_n\}}
V={v1?,...,vn?}是大小为
N
=
∣
V
∣
N=|V|
N=∣V∣的点集，
E
=
{
e
1
,
.
.
.
,
e
m
}
E=\{e_1,...,e_m\}
E={e1?,...,em?}是长度为
M
M
M的边集。
- 邻接矩阵的定义
G
=
{
V
,
E
}
G=\{V,E\}
G={V,E}的邻接矩阵
A
∈
{
0
,
1
}
N
×
N
A\in\{0,1\}^{N\times N}
A∈{0,1}N×N。
A
i
,
j
A_{i,j}
Ai,j?表示节点
v
i
,
v
j
v_i,v_j
vi?,vj?之间的邻接关系。相邻为1，不相邻为0。
- 关联（
i
n
c
i
d
e
n
t
incident
incident）的定义 节点
v
i
v_i
vi?和
v
j
v_j
vj?相邻当且仅当它们之间存在一条边，此时也认为边
e
i
e_i
ei?和顶点
v
e
i
v_{e_i}
vei??（或
v
e
j
v_{e_j}
vej??）相关联
图的性质
度
-
度（
D
e
g
r
e
e
Degree
Degree）表示该节点与其它节点相邻的次数 度
d
(
v
i
)
d(v_i)
d(vi?)的两种计算方法
-
通过图中相邻边的数目
d
(
v
i
)
=
∑
v
j
∈
V
1
ε
(
{
v
i
,
v
j
}
)
,
1
ε
(
{
v
i
,
v
j
}
)
=
{
1
,
(
v
i
,
v
j
)
∈
ε
0
,
(
v
i
,
v
j
)
?
ε
d(v_i)=\sum_{v_j\in V}\mathbb{1}\varepsilon(\{v_i,v_j\}),\\ \mathbb{1}\varepsilon(\{v_i,v_j\})=\left\{ \begin{aligned} 1,(v_i,v_j)\in \varepsilon \\ 0,(v_i,v_j)\notin \varepsilon \end{aligned} \right.
d(vi?)=vj?∈V∑?1ε({vi?,vj?}),1ε({vi?,vj?})={1,(vi?,vj?)∈ε0,(vi?,vj?)∈/?ε? -
通过图的邻接矩阵
d
(
v
i
)
=
∑
j
=
1
N
A
i
,
j
d(v_i)=\sum_{j=1}^NA_{i,j}
d(vi?)=j=1∑N?Ai,j?
-
度的相关定理 图中所有节点的度之和是图中边的数量的两倍
∑
v
i
∈
V
d
(
v
i
)
=
2
?
∣
ε
∣
\sum_{v_i\in V}d(v_i)=2\cdot|\varepsilon|
vi?∈V∑?d(vi?)=2?∣ε∣
相关推论：无向图邻接矩阵的非零元素的个数是边的数量的两倍
连通度
-
途径（
W
a
l
k
Walk
Walk） 图的途径是节点和边的交替序列，从一个节点开始，以一个节点结束，其中每条边与紧邻的节点相关联 从节点
u
u
u到节点
v
v
v结束的途径称为
u
?
v
u-v
u?v途径。途径长度即为途径中包含的边的数量。
u
?
v
u-v
u?v途径并不一定唯一。 -
迹（
T
r
a
i
l
Trail
Trail） 迹是边各不相同的途径 -
路（
P
a
t
h
Path
Path） 路是节点各不相同的途径，也称路径 -
途径相关定理
A
n
A^n
An表示图邻接矩阵的n次幂，则
A
n
A_n
An?的第
i
i
i行第
j
j
j列 的元素等于长度为
n
n
n的
v
i
?
v
j
v_i-v_j
vi??vj?途径的个数 -
子图（
S
u
b
G
r
a
p
h
SubGraph
SubGraph）图
G
=
{
V
,
E
}
G=\{V,E\}
G={V,E}的子图
G
′
=
{
V
′
,
E
′
}
G'=\{V',E'\}
G′={V′,E′}由节点集的子集
V
′
∈
V
V'\in V
V′∈V和边集的子集
E
∈
E
′
E\in E'
E∈E′组成。此外，集合
V
′
V'
V′必须包含集合
E
′
E'
E′设计的所有节点 -
连通分量（
C
o
n
n
e
c
t
e
d
C
o
m
p
o
n
t
e
n
t
Connected Compontent
ConnectedCompontent） 给定一个图
G
=
{
V
,
E
}
G=\{V,E\}
G={V,E},如果一个子图
G
′
=
{
V
′
,
E
′
}
G'=\{V',E'\}
G′={V′,E′}中任意一对节点之间都存在至少一条路，且
V
′
V'
V′中的节点不与任何
V
/
V
′
V/V'
V/V′中的节点相连，那么
G
′
G'
G′就是一个连通分量。 -
连通图（
C
o
n
n
e
c
t
e
d
G
r
a
p
h
Connected Graph
ConnectedGraph） 如果一个图
G
=
{
V
,
E
}
G=\{V,E\}
G={V,E}只有一个连通分量，那么
G
G
G是连通图 -
最短路（
S
h
o
r
t
P
a
t
h
Short Path
ShortPath） 给定图
G
G
G中的一对节点
v
s
,
v
t
∈
V
v_s,v_t\in V
vs?,vt?∈V,且
P
s
t
P_st
Ps?t表示节点
v
s
v_s
vs?到节点
v
t
v_t
vt?的路的集合。那么节点
v
s
v_s
vs?和节点
v
t
v_t
vt?间的最短路定义为：
p
s
t
s
p
=
a
r
g
m
i
n
p
∈
P
s
t
∣
p
∣
p_{st}^{sp}=arg min_{p\in P_{st}}|p|
pstsp?=argminp∈Pst??∣p∣
其中
p
p
p表示
P
s
t
P_{st}
Pst?中一条长度为
∣
p
∣
|p|
∣p∣的路；
p
s
t
s
p
p_{st}^{sp}
pstsp?表示最短路。任意给定的节点对之间可能有很多条最短路 -
直径（
D
i
a
m
e
t
e
r
Diameter
Diameter） 给定一个连通图
G
=
{
V
,
E
}
G=\{V,E\}
G={V,E},它的直径定义为
d
i
a
m
e
t
e
r
(
G
)
=
m
a
x
v
s
,
v
t
∈
V
m
i
n
p
∈
P
s
t
∣
p
∣
diameter(G)=max_{v_s,v_t\in V}min_{p\in P_{st}}|p|
diameter(G)=maxvs?,vt?∈V?minp∈Pst??∣p∣
即为最长的最短路
中心性
-
度中心性（
D
e
g
r
e
e
C
e
n
t
r
a
l
i
t
y
Degree\quad Centrality
DegreeCentrality） 节点
v
i
v_i
vi?的度中心性为
c
d
(
v
i
)
=
d
(
v
i
)
=
∑
j
=
1
N
A
i
,
j
c_d(v_i)=d(v_i)=\sum_{j=1}^NA_{i,j}
cd?(vi?)=d(vi?)=j=1∑N?Ai,j? -
特征向量中心性（
E
i
g
e
n
v
e
c
t
o
r
C
e
n
t
r
a
l
i
t
y
Eigenvector \quad Centrality
EigenvectorCentrality） 节点
v
i
v_i
vi?的特征向量中心性用它的相邻节点的中心性来定义，为
c
e
(
v
i
)
=
1
λ
∑
j
=
1
N
A
i
,
j
?
c
e
(
v
j
)
c_e(v_i)=\frac{1}{\lambda}\sum_{j=1}^NA_{i,j}\cdot c_e(v_j)
ce?(vi?)=λ1?j=1∑N?Ai,j??ce?(vj?)
矩阵形式表示为
c
e
=
1
λ
A
?
c
e
λ
?
c
e
=
A
?
c
e
c_e=\frac{1}{\lambda}A\cdot c_e\\ \lambda\cdot c_e=A\cdot c_e
ce?=λ1?A?ce?λ?ce?=A?ce?
c
e
∈
R
N
c_e\in\mathbb{R}^N
ce?∈RN是一个包含所有节点的特征向量中心性的向量。 可以选择最大的特征值
λ
\lambda
λ，将它的相应的特征行了作为中心性向量。 -
K
a
t
z
Katz
Katz中心性（
K
a
t
z
C
e
n
t
r
a
l
i
t
y
Katz\quad Centrality
KatzCentrality）
K
a
t
z
Katz
Katz中心性是特征向量中心性的变形，除了邻居节点，它还通过一个常数来考虑节点本身。节点
v
i
v_i
vi?的
K
a
t
z
Katz
Katz中心性可以定义为：
c
k
(
v
i
)
=
α
∑
j
=
1
N
A
i
,
j
c
k
(
v
j
)
+
β
c_k(v_i)=\alpha\sum_{j=1}^NA_{i,j}c_k(v_j)+\beta
ck?(vi?)=αj=1∑N?Ai,j?ck?(vj?)+β
矩阵形式表示为
c
k
=
α
A
c
k
+
β
(
I
?
α
?
A
)
c
k
=
β
c_k=\alpha Ac_k+\beta\\ (I-\alpha\cdot A)c_k=\beta
ck?=αAck?+β(I?α?A)ck?=β
若
α
=
1
λ
m
a
x
\alpha=\frac{1}{\lambda_{max}}
α=λmax?1?和
β
=
0
\beta=0
β=0时，则
K
a
t
z
Katz
Katz中心性等价于特征向量中心性。
α
\alpha
α的选择对
K
a
t
z
Katz
Katz中心性的选择非常关键：大的
α
\alpha
α值可能使矩阵
I
?
α
?
A
I-\alpha\cdot A
I?α?A变成病态矩阵，而小的
α
\alpha
α可能使得中心性变得没有意义，因为总是使得节点分配相同的分数。实践中，经常令
α
<
1
λ
m
a
x
\alpha<\frac{1}{\lambda_{max}}
α<λmax?1?，从而保证矩阵
I
?
α
?
A
I-\alpha\cdot A
I?α?A的可逆性。则
c
k
c_k
ck?为
c
k
=
(
I
?
α
?
A
)
?
1
β
c_k=(I-\alpha\cdot A)^{-1}\beta
ck?=(I?α?A)?1β -
介数中心性（
B
e
t
w
e
e
n
n
e
s
s
C
e
n
t
r
e
l
i
t
y
Betweenness\quad Centrelity
BetweennessCentrelity） 介数中心性度量节点是否处于图中的重要位置。如果有很多路通过该节点，则该节点在图中处于一个重要位置。节点
v
i
v_i
vi?的介数中心性可以定义为：
c
b
(
v
i
)
=
∑
v
s
≠
v
i
≠
v
t
σ
s
t
(
v
i
)
σ
s
t
c_b(v_i)=\sum_{v_s\neq v_i \neq v_t} \frac{\sigma_{st}(v_i)}{\sigma_{st}}
cb?(vi?)=vs??=vi??=vt?∑?σst?σst?(vi?)?
其中，
σ
s
t
\sigma_{st}
σst?表示所有从节点
v
s
v_s
vs?到节点
v
t
v_t
vt?的最短路的数目；
σ
s
t
(
v
i
)
\sigma_{st}(v_i)
σst?(vi?)表示这些路中经过节点
v
i
v_i
vi?的路的数目。介数中心性会随着图的增大而增大，为了使介数中心性在不同图中有可比性，需要对其进行归一化。一种有效的方法是将所有节点的中心性除以其中的最大值。
c
n
b
(
v
i
)
=
2
×
∑
v
s
≠
v
i
≠
v
t
σ
s
t
(
v
i
)
σ
s
t
(
N
?
1
)
(
N
?
2
)
c_nb(v_i)=\frac{2\times \sum_{v_s\neq v_i \neq v_t} \frac{\sigma_{st}(v_i)}{\sigma_{st}}} {(N-1)(N-2)}
cn?b(vi?)=(N?1)(N?2)2×∑vs??=vi??=vt??σst?σst?(vi?)??
谱图论
-
谱图论是通过分析图的拉普拉斯矩阵的特征值和特征向量研究图的性质。 -
拉普拉斯矩阵（
L
a
p
l
a
c
i
a
n
M
a
t
r
i
x
Laplacian\quad Matrix
LaplacianMatrix ） 对于给定图
G
=
{
V
,
E
}
G=\{V,E\}
G={V,E}及其邻接矩阵
A
A
A，其拉普拉斯矩阵为
L
=
D
?
A
L=D-A
L=D?A
其中
D
D
D是对角矩阵，
D
=
d
i
a
g
(
d
(
v
i
)
,
.
.
.
,
d
(
v
N
)
)
D=diag(d(v_i),...,d(v_N))
D=diag(d(vi?),...,d(vN?))，其归一化形式为
L
=
D
?
1
2
(
D
?
A
)
D
?
1
2
=
I
?
D
?
1
2
A
D
?
1
2
L=D^{-\frac{1}{2}}(D-A)D^{-\frac{1}{2}}=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}
L=D?21?(D?A)D?21?=I?D?21?AD?21?
归一化的原因：采用加法规则时，对于度大的节点特征越来越大，而对于度小的节点却相反，这可能导致网络训练过程中梯度爆炸或者消失的问题。 相关证明参见：https://www.zhihu.com/question/42678425 -
拉普拉斯矩阵的性质
- 拉普拉斯矩阵是对称半正定矩阵
- 对于图
G
=
{
V
,
E
}
G=\{V,E\}
G={V,E}，其拉普拉斯矩阵的特征值是非负的
- 对于图
G
G
G，其拉普拉斯矩阵的特征值为0的数目（特征值0的重数）等于图中的连通分量的数目
证明与更多关于拉普拉斯矩阵参见：https://zhuanlan.zhihu.com/p/362416124
图信号处理
-
图信号由图
G
=
{
V
,
E
}
G=\{V,E\}
G={V,E}和在节点域上定义的将节点映射为实数值的映射函数
f
f
f构成。该映射函数可表示为：
f
:
v
→
R
N
×
d
f:v\to \mathbb{R}^{N\times d}
f:v→RN×d
其中
d
d
d是属性向量的维度。 接下来定义
d
d
d为一维，所以可用
f
[
i
]
f[i]
f[i]表示节点
v
i
v_i
vi?的映射值 传统的信号处理中，信号可以表示在两个域——时域和频域。图信号也可以表示为两个域，即空间域和谱域。 -
平滑度（或频率） 如果某个图中相邻的节点的值是相似的，那么这个图被认为是平滑的（
s
m
o
o
t
h
smooth
smooth），一个平滑的图信号是低频率的，因为这些值通过图中的边在缓慢地变化。具体的来说，一个图信号越平滑，
f
T
L
f
f^TLf
fTLf的值也越小。因此
f
T
L
f
f^TLf
fTLf的值也被称为信号的平滑度。 -
图信号的谱域基础是。（
G
r
a
p
h
F
o
u
r
i
e
r
T
r
a
n
s
f
o
r
m
,
G
F
T
Graph\quad Fourier\quad Transform,GFT
GraphFourierTransform,GFT），它是建立在谱图论之上的。一个图
G
G
G上的信号
f
f
f的图傅里叶变换可表示为
h
^
[
l
]
=
<
f
,
u
l
>
=
∑
i
=
1
N
f
[
i
]
u
l
[
i
]
\hat{h}[l]=<f,u_l>=\sum_{i=1}^Nf[i]u_l[i]
h^[l]=<f,ul?>=i=1∑N?f[i]ul?[i]
其中
u
l
u_l
ul?表示图的拉普拉斯矩阵
L
L
L的第
l
l
l个特征向量，其对应的特征值
λ
l
\lambda_l
λl?表示
u
l
u_l
ul?的频率（或平滑度）。向量
f
^
\hat{f}
f^?是
f
f
f的图傅里叶变换，
f
^
[
l
]
\hat{f}[l]
f^?[l]表示它的第
l
l
l个元素。这些特征向量是图
G
G
G上傅里叶基。
f
f
f的图傅里叶基的矩阵表示
f
^
=
U
T
f
\hat{f}=U^Tf
f^?=UTf
其中
U
U
U的第
l
l
l列为
u
l
u_l
ul? 由于
u
l
T
L
u
l
=
λ
l
?
u
l
T
u
l
=
λ
l
u_l^TLu_l=\lambda_l\cdot u_l^{T}u_l=\lambda_l
ulT?Lul?=λl??ulT?ul?=λl?
可知特征值
λ
l
\lambda_l
λl?度量对应的特征向量
u
l
u_l
ul?的平滑度。这些特征向量是图
G
G
G上傅里叶基，其对应的特征值表示它们的频率。图傅里叶变换是将图信号
f
f
f分解到不同频率的傅里叶基的过程 -
图上同样存在这图傅里叶逆变换（
I
n
v
e
r
s
e
G
r
a
p
h
F
o
u
r
i
e
r
T
r
a
n
s
f
o
r
m
,
I
G
F
T
Inverse \quad Graph \quad Fourier \quad Transform,IGFT
InverseGraphFourierTransform,IGFT），它将信号的谱域转成空间域表示
f
[
i
]
=
∑
l
=
1
N
f
^
[
l
]
u
l
[
i
]
f[i]=\sum_{l=1}^N\hat{f}[l]u_l[i]
f[i]=l=1∑N?f^?[l]ul?[i]
矩阵表示为
f
=
U
f
^
f=U\hat{f}
f=Uf^?
复杂图
- 异构图（
H
e
t
e
r
o
g
e
n
e
o
u
s
G
r
a
p
h
s
Heterogeneous \quad Graphs
HeterogeneousGraphs）一个异质图
G
G
G由一组节点
V
=
{
v
1
,
.
.
.
,
v
N
}
V=\{v1,...,v_N\}
V={v1,...,vN?}和一组边
ε
=
{
e
1
,
.
.
.
,
e
N
}
\varepsilon=\{e_1,...,e_N\}
ε={e1?,...,eN?}构成。其中每个节点和每条边都对应着一个类型。用
T
n
T_n
Tn?表示节点类型的集合，
T
e
T_e
Te?表示边类型的集合。一个异质图右两个映射函数，分别是将每个节点映射到对应类型的
?
n
:
V
→
T
n
\phi_n:V\to T_n
?n?:V→Tn?，及将每条边映射到对应类型的
?
e
:
ε
→
T
e
\phi_e: \varepsilon \to T_e
?e?:ε→Te?
- 二分图（
B
i
p
a
r
t
i
t
e
G
r
a
p
h
s
Bipartite \quad Graphs
BipartiteGraphs） 给定一个图
G
=
{
V
,
E
}
G=\{V,E\}
G={V,E}，
G
G
G是二分图当且仅当
V
=
V
1
∪
V
2
,
V
1
∩
V
2
=
?
V=V_1\cup V_2,V_1 \cap V_2=\emptyset
V=V1?∪V2?,V1?∩V2?=?，并且对于所有的边
e
=
(
v
e
1
,
v
e
2
)
∈
ε
e=(v_e^1,v_e^2)\in\varepsilon
e=(ve1?,ve2?)∈ε，都有
v
e
1
∈
V
1
v_e^1\in V_1
ve1?∈V1?和
v
e
2
∈
V
2
v_e^2\in V_2
ve2?∈V2?
- 多维图（
M
u
l
t
i
?
d
i
m
e
n
s
i
o
n
a
l
G
r
a
p
h
s
Multi-dimensional \quad Graphs
Multi?dimensionalGraphs） 一个多维图由于一个节点集
V
=
{
v
1
,
?
?
,
v
N
}
V=\{v_1,\cdots,v_N\}
V={v1?,?,vN?}和
D
D
D个边集
{
ε
1
,
?
?
,
ε
D
}
\{\varepsilon_1,\cdots,\varepsilon_D\}
{ε1?,?,εD?}构成。每个边集
ε
d
\varepsilon_d
εd?描述了节点之间的一种关系。这
D
D
D种关系也可以表示为
D
D
D个邻接矩阵
A
(
1
)
,
?
?
,
A
(
D
)
A^{(1)},\cdots,A^{(D)}
A(1),?,A(D)。第
d
d
d维对应着邻接矩阵
A
(
d
)
∈
R
N
×
N
A^{(d)}\in\mathbb{R}^{N\times N}
A(d)∈RN×N,描述了节点之间的边
ε
D
\varepsilon_D
εD?。
A
(
d
)
A^{(d)}
A(d)的第
i
,
j
i,j
i,j项，即
A
i
,
j
(
d
)
A_{i,j}^{(d)}
Ai,j(d)?，等于1当且仅当
v
i
v_i
vi?和
v
j
v_j
vj?在第
d
d
d维存在一条边（或者
(
v
i
,
v
j
)
∈
ε
d
(v_i,v_j)\in\varepsilon_d
(vi?,vj?)∈εd?）,否则为0。
- 符号图（
S
i
g
n
e
d
G
r
a
p
h
s
Signed \quad Graphs
SignedGraphs） 用
G
=
{
V
,
ε
+
,
ε
?
}
G=\{V,\varepsilon^{+},\varepsilon^{-}\}
G={V,ε+,ε?}表示一个符号图，其中
V
=
{
v
1
,
?
?
,
v
N
}
V=\{v_1,\cdots,v_N\}
V={v1?,?,vN?}是一个包含
N
N
N个节点的集合，而
ε
+
?
V
×
V
\varepsilon^{+} \subset V\times V
ε+?V×V和
ε
?
?
V
×
V
\varepsilon^{-} \subset V\times V
ε??V×V分别表示正边和负边集合。且
ε
+
∩
ε
?
=
?
\varepsilon^{+}\cap \varepsilon^{-}=\emptyset
ε+∩ε?=?。正边和负边也可以用符号邻接矩阵
A
A
A表示，其中
A
i
,
j
=
1
A_{i,j}=1
Ai,j?=1表示当且仅当
v
i
v_i
vi?和
v
j
v_j
vj?存在一条正边，
A
i
,
j
=
?
1
A_{i,j}=-1
Ai,j?=?1表示负边，
A
i
,
j
=
0
A_{i,j}=0
Ai,j?=0表示没有边
- 超图
- 动态图（
D
y
n
a
m
i
c
G
r
a
p
h
s
Dynamic\quad Graphs
DynamicGraphs）
图的计算任务
- 侧重节点的任务 节点分类、链接预测、节点排序和社区检测
- 侧重于图的任务 图分类、图匹配和图生成
|