More Like this

1. Differentially Private Densest Subgraph Detection

   Nguyen, Dung; Vullikanti, Anil (January 2021, ICML)
2. Differentially Private Densest Subgraph Detection

   Nguyen, Dung; Vullikanti, Anil (January 2021, 38th International Conference on Machine Learning)

   null (Ed.)
3. The Generalized Mean Densest Subgraph Problem

   https://doi.org/10.1145/3447548.3467398  

   Veldt, Nate; Benson, Austin R.; Kleinberg, Jon (August 2021, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2021)
4. Near-optimal fully dynamic densest subgraph

   https://doi.org/10.1145/3357713.3384327  

   Sawlani, Saurabh; Wang, Junxing (June 2020, Proccedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020})
5. A New Dynamic Algorithm for Densest Subhypergraphs

   https://doi.org/10.1145/3485447.3512158  

   Bera, Suman K.; Bhattacharya, Sayan; Choudhari, Jayesh; Ghosh, Prantar (April 2022, WWW '22: Proceedings of the ACM Web Conference 2022)

   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. 

   more » « less