Top-k overlapping densest subgraphs: approximation algorithms and computational complexity

给定图GVE，令GV1和GV2是G的两个子图。当V1∩V2∅V1∖V2∅且V2∖V1∅时，称GV1和GV2是G的交叉子图。

夏荷影

322人浏览 · 2023-04-23 21:40:22

夏荷影 · 2023-04-23 21:40:22 发布

概念

交叉子图

给定图 $G = (V, E)$ ，令 $G[ V_{1} ]$ 和 $G[V_{2}]$ 是 $G$ 的两个子图。当 $V1∩V2≠∅V_{1} \cap V_{2} \neq \varnothing$ ， $V1∖V2≠∅V_{1} \setminus V_{2} \neq \varnothing$ 且 $V2∖V1≠∅V_{2} \setminus V_{1} \neq \varnothing$ 时，称 $G[ V_{1} ]$ 和 $G[V_{2}]$ 是G的交叉子图

子图的稠密度 dense of subgraph

$\in V，G[V']的稠密度为 dens(G[V'])=\frac{|E'|}{|V'|}$ 。

densest subgraph

$图 G = (V, E) 中 d e n s (G [U]) 最大的子图 G [U]$

一组子图的稠密度

$给定图G(V,E)和一组k个不同的子图W={G[W1],…,G[Wk]}，W的稠密度定义为给定图G(V,E)和一组k个不同的子图W=\{G[W_{1}], \ldots , G[W_{k}]\}，W的稠密度定义为$
$\sum_{i=1}^kdens(G[W_i])$

两个子图间距离函数

给定图 $G = (V, E)$ 和两个不同的子图 $G [U], G [Z]$ ，其中 $U,Z⊆V,两个子图间距离定义为U,Z\subseteq V,两个子图间距离定义为$
$\{\begin{matrix} 2 - \frac{|U\cap Z|^2}{|U||Z|} & if U \neq Z\\ 0 & else \\ \end{matrix}$

引理1 两子图间距离的上下界

给定图 $G = (V, E)$ 的两个不同的子图 $G [U], G [Z]$ ，有 $\leqslant d(U,Z) \leqslant 2$

问题1 Top-k-overlapping Densest Subgraphs

输入：

图 $G = (V, E)$ ,参数 $λ>0\lambda>0$

输出：

k对不同的子图集 $\{ G[W_1],\ldots , G[W_k] \}$ ，其中 $\leqslant k \leqslant |V|$ 且 $Wi⊆V,1⩽i⩽kW_i \subseteq V, 1 \leqslant i \leqslant k$ ，使下式达到最大。
$dens(W)+\lambda \sum_{i=1}^{k-1}\sum_{j=i+1}^{k}d(W_i,W_j)$

近似k重叠最稠密子图

当 $k$ 是固定值时，提供一个 $23\frac{2}{3}$ -近似的算法；当 $k$ 不是固定值时，提供一个 $12\frac{1}{2}$ -近似的算法

常数k的近似算法

性质2

考虑一个图 $G = (V, E)$ 和子图集合 $W={G[W1],…,G[Wt]}W=\{G[W_1], \ldots , G[W_t]\}$ ，其中 $\leqslant t \leqslant k-1$ 。给定一个和 $W$ 中的子图不同的子图 $G [Z]$ 。存在k个顶点 $u1,…,utu_1,\ldots ,u_t$ ，这 $t$ 个顶点可以有重叠，其中 $ui∈V，1⩽i⩽tu_i \in V，1 \leqslant i \leqslant t$ 。这 $t$ 个顶点可以划分为两个集合 $U_1,U_2$ ，使得 $\supseteq U_1，Z \cap U_2 = \emptyset$ 且 W 中不存在 $G[Wj]，1⩽j⩽tG[W_j]，1\leqslant j \leqslant t$ 使得 $WJ⊇U1,Wj∩U2=∅W_J \supseteq U_1, W_j \cap U_2 = \emptyset$ 。

算法1 计算出一个密度不同子图的最优解

在这里插入图片描述

定理1

令 $G [Z]$ 是算法1的解。那么 $G [Z]$ 是实例 $(G, W)$ 上的Densest-Distinct-Subgraph的最优解。

$23\frac{2}{3}$ 近似算法

在这里插入图片描述
引理3 令 $\{ G[W_1],\ldots,G[W_K]\}$ 是算法2返回的子图集合， $W0={G[W10],…,G[WK0]}W^0 = \{ G[W_1^0],\ldots,G[W_K^0]\}$ 是实例 $(G,λ)(G,\lambda)$ 上重叠k最稠密子图(Top-k-Overlapping Densest Subgraphs)的最优解，有：
$\geqslant dens(W^0), \\ \lambda \sum_{i=1}^{k-1}\sum_{j=i+1}^{k}d(G[W_i],G[W_j]) \ge \frac{1}{2} \lambda \sum_{i=1}^{k-1}\sum_{j=i+1}^{k}d(G[W_i^0],G[W_j^0])$