English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Given an undirected graph, the Densest-k-Subgraph problem (DkS) seeks to finda subset of k vertices such that the sum of the edge weights in thecorresponding subgraph is maximized. The problem is known to be NP-hard, and isalso very difficult to approximate, in the worst-case. In this paper, wepresent a new convex relaxation for the problem. Our key idea is to reformulateDkS as minimizing a submodular function subject to a cardinality constraint.Exploiting the fact that submodular functions possess a convex, continuousextension (known as the Lov\'asz extension), we propose to minimize theLov\'asz extension over the convex hull of the cardinality constraints.Although the Lov\'asz extension of a submodular function does not admit ananalytical form in general, for DkS we show that it does. We leverage thisresult to develop a highly scalable algorithm based on the AlternatingDirection Method of Multipliers (ADMM) for solving the relaxed problem. Coupledwith a pair of fortuitously simple rounding schemes, we demonstrate that ourapproach outperforms existing baselines on real-world graphs and can yield highquality sub-optimal solutions which typically are a posteriori no worse than65-80\% of the optimal density.

Exploring the Subgraph Density-Size Trade-off via the Lov\'asz Extension