Scholarlink

<p>Finding the densest subgraph (DS) from a graph is a fundamental problem in graph data management and mining. The DS reveals closely connected entities and has been found to be useful in various application domains such as e-commerce, social science, and biology. However, in a big graph containing billions of edges, it is desirable to find more than one subgraph cluster that is not necessarily the densest, as each dense cluster reveals closely related vertices. In this paper, we study the locally densest subgraph (LDS), a recently proposed variant of DS. An LDS is a subgraph which is the densest among the “local neighbors”. Given a graph <i>G</i>, a number of LDSs can be returned, reflecting different dense regions of <i>G</i> and thus giving more information than the DS. Existing solutions for LDS suffer from low efficiency. We thus develop a convex-programming-based solution that enables powerful pruning. We also extend our algorithm to handle triangle-based density and solve the triangle density-based LDS (LTDS) problem. Based on both existing and our proposed algorithms, we propose a unified framework for the LDS and LTDS problems. Extensive experiments on thirteen real large graph datasets show that our proposed algorithm is up to four orders of magnitude faster than the state-of-the-art.</p>

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

Finding Locally Densest Subgraphs: Convex Programming with Edge and Triangle Density

  • 期刊论文

  • 发表日期：

    2026年1月4日

查看全文
  • Yi Yang,
  • Chenhao Ma,
  • Reynold Cheng,
  • Laks V. S. Lakshmanan,
  • Xiaolin Han

摘要

Finding the densest subgraph (DS) from a graph is a fundamental problem in graph data management and mining. The DS reveals closely connected entities and has been found to be useful in various application domains such as e-commerce, social science, and biology. However, in a big graph containing billions of edges, it is desirable to find more than one subgraph cluster that is not necessarily the densest, as each dense cluster reveals closely related vertices. In this paper, we study the locally densest subgraph (LDS), a recently proposed variant of DS. An LDS is a subgraph which is the densest among the “local neighbors”. Given a graph G, a number of LDSs can be returned, reflecting different dense regions of G and thus giving more information than the DS. Existing solutions for LDS suffer from low efficiency. We thus develop a convex-programming-based solution that enables powerful pruning. We also extend our algorithm to handle triangle-based density and solve the triangle density-based LDS (LTDS) problem. Based on both existing and our proposed algorithms, we propose a unified framework for the LDS and LTDS problems. Extensive experiments on thirteen real large graph datasets show that our proposed algorithm is up to four orders of magnitude faster than the state-of-the-art.