تقرير
A New Dynamic Algorithm for Densest Subhypergraphs
| العنوان: | A New Dynamic Algorithm for Densest Subhypergraphs |
|---|---|
| المؤلفون: | Bera, Suman K., Bhattacharya, Sayan, Choudhari, Jayesh, Ghosh, Prantar |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
| الوصف: | Computing a dense subgraph is a fundamental problem in graph mining, with a diverse set of applications ranging from electronic commerce to community detection in social networks. In many of these applications, the underlying context is better modelled as a weighted hypergraph that keeps evolving with time. This motivates the problem of maintaining the densest subhypergraph of a weighted hypergraph in a {\em dynamic setting}, where the input keeps changing via a sequence of updates (hyperedge insertions/deletions). Previously, the only known algorithm for this problem was due to Hu et al. [HWC17]. This algorithm worked only on unweighted hypergraphs, and had an approximation ratio of $(1+\epsilon)r^2$ and an update time of $O(\text{poly} (r, \log n))$, where $r$ denotes the maximum rank of the input across all the updates. We obtain a new algorithm for this problem, which works even when the input hypergraph is weighted. Our algorithm has a significantly improved (near-optimal) approximation ratio of $(1+\epsilon)$ that is independent of $r$, and a similar update time of $O(\text{poly} (r, \log n))$. It is the first $(1+\epsilon)$-approximation algorithm even for the special case of weighted simple graphs. To complement our theoretical analysis, we perform experiments with our dynamic algorithm on large-scale, real-world data-sets. Our algorithm significantly outperforms the state of the art [HWC17] both in terms of accuracy and efficiency. Comment: Extended abstract appears in TheWebConf (previously WWW) 2022 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2204.08106 |
| رقم الأكسشن: | edsarx.2204.08106 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |