面向大规模时态图的紧密子图维护算法

面向大规模时态图的紧密子图维护算法

车鑫恺, 陈雅迪, 胡淼, 吴迪

Cohesive subgraph maintenance algorithms for large⁃scale temporal graphs

Xinkai Che, Yadi Chen, Miao Hu, Di Wu

表1 文中使用的数学符号表

Table 1 Mathematical symbols used in this article

符号	描述
$E (G)$	时态图 $G$ 的边的集合
$F (k, h)$	$\hat{T} (S_{i}, G_{c}, k, h)$ 的候选插入子图
$G$	一张时态图
$G_{p}$	上一时刻的时态图
$G_{c}$	当前时刻的时态图
$P (k, h)$	部分 $(k, h)$ ⁃核
$S_{i}$	插入子图
$S_{r}$	删除子图
$S_{i} (G_{c})$	$S_{i}$ 在 $G_{c}$ 上的扩展图
$T (G, k, h)$	时态图 $G$ 的 $(k, h)$ ⁃核
$\hat{T} (S_{i}, G_{c}, k, h)$	$S_{i}$ 在 $G_{c}$ 上的类似 $(k, h)$ ⁃核
$V (G)$	时态图 $G$ 的顶点的集合
$u$	时态图中任意一个顶点
$v$	时态图中任意一个顶点
$(u, v, t_{s}, t_{e})$	时态图中任意一条边
$ϕ (G, v)$	图 $G$ 中任意一个顶点 $v$ 的邻居顶点集合
$ψ (G, u, v)$	图 $G$ 中任意两个顶点 $u$ 和 $v$ 之间边的集合
$\|ϕ (G, v)\|$	图 $G$ 中任意一个顶点 $v$ 的邻居顶点的数目
$\|ψ (G, u, v)\|$	图 $G$ 中任意两个顶点 $u$ 和 $v$ 之间边的数目
$\|ϕ (G)\|$	图 $G$ 中顶点的最大度数
$\|ψ (G)\|$	图 $G$ 中两个邻接顶点之间最大多重边个数