Scholarlink

<p>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 <i>G</i> with <i>n</i> vertices and a positive integer <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\tau &lt;n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>τ</mi> <mo>&lt;</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, find an induced subgraph of size <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(n-\tau \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mi>τ</mi> </mrow> </math></EquationSource> </InlineEquation> 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 <i>G</i>. 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Graph downsizing: a fast heuristic for querying closely connected subgraphs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月20日

查看全文
  • Yiping Liu,
  • Mengxiao Zhang,
  • Jiamou Liu,
  • Yi Zhou

摘要

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\) τ < n , find an induced subgraph of size \(n-\tau \) n - τ 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.