Bera, Suman, Bhattacharya, Sayan, Choudhari, Jayesh and Ghosh, Prantar (2022) A new dynamic algorithm for densest subhypergraphs. In: WWW '22: The ACM Web Conference, Online, hosted Lyon, France, 25–29 Apr 2022. Published in: WWW '22: Proceedings of the ACM Web Conference 2022 pp. 1093-1103. ISBN 9781450390965. doi:10.1145/3485447.3512158
Preview |
PDF
WRAP-new-dynamic-algorithm-densest-subhypergraph-Bhattacharya-2022.pdf - Accepted Version - Requires a PDF viewer. Download (1MB) | Preview |
Abstract
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 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. [19]. This algorithm worked only on unweighted hypergraphs, and had an approximation ratio of (1 +ϵ)r2 and an update time of O(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 +ϵ) that is independent of r, and a similar update time of O(poly(r, log n)). It is the first (1 +ϵ)-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 [19] both in terms of accuracy and efficiency.
| Item Type: | Conference Item (Paper) |
|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Library of Congress Subject Headings (LCSH): | Graph algorithms, Hypergraphs |
| Journal or Publication Title: | WWW '22: Proceedings of the ACM Web Conference 2022 |
| Publisher: | ACM |
| ISBN: | 9781450390965 |
| Official Date: | 25 April 2022 |
| Dates: | Date Event 25 April 2022 Published 13 January 2022 Accepted |
| Page Range: | pp. 1093-1103 |
| DOI: | 10.1145/3485447.3512158 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Re-use Statement: | © ACM 2022. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in WWW '22: The ACM Web Conference Proceedings, http://dx.doi.org/10.1145/3485447.3512158 |
| Access rights to Published version: | Restricted or Subscription Access |
| Date of first compliant deposit: | 16 March 2022 |
| Date of first compliant Open Access: | 18 March 2022 |
| Conference Paper Type: | Paper |
| Title of Event: | WWW '22: The ACM Web Conference |
| Type of Event: | Conference |
| Location of Event: | Online, hosted Lyon, France |
| Date(s) of Event: | 25–29 Apr 2022 |
| Related URLs: | |
| URI: | https://wrap.warwick.ac.uk/163772/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |