Graph downsizing: a fast heuristic for querying closely connected subgraphs
研究了在给定大小约束下最大化顶点连通性的图缩减问题，提出了一种基于嵌套树结构的启发式算法，能在百万级顶点数据集上快速找到接近最优的紧密连接子图。
Abstract The vertex connectivity of a graph is the minimum number of vertices whose removal disconnects the graph, and it is a fundamental notion that measures the level of interconnectedness of vertices. Mining subgraphs with high vertex connectivity has wide applications in robust and efficient communication networks and the organization of task groups. However, existing approaches often neglect size constraints, leading to subgraphs that are either too large or too small for practical use. Therefore, in this paper, we introduce the size constraint and formulate the graph downsizing problem: Given a graph G with n vertices and a positive integer $$\tau <n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>τ</mml:mi> <mml:mo><</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> , find an induced subgraph of size $$n-\tau $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mi>τ</mml:mi> </mml:mrow> </mml:math> that maximizes vertex connectivity. We first analyze the computational complexity of the graph downsizing problem and show that the problem is hard in several aspects. To solve the problem in practice, we use a nesting tree structure to represent relations between maximal cohesive subgraphs in G . This structure allows us to develop an efficient heuristic, called inundation downsizing algorithm, to find highly vertex-connected subgraphs of different sizes. Experimental results reveal that our heuristic is able to produce almost optimal solutions on real-world datasets with up to 1 million vertices while incurring small time costs.