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/

Global: Zendy Tools annual

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

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

A central problem in graph mining is finding dense subgraphs, with severalapplications in different fields, a notable example being identifyingcommunities. While a lot of effort has been put on the problem of finding asingle dense subgraph, only recently the focus has been shifted to the problemof finding a set of densest subgraphs. Some approaches aim at finding disjointsubgraphs, while in many real-world networks communities are often overlapping.An approach introduced to find possible overlapping subgraphs is the Top-kOverlapping Densest Subgraphs problem. For a given integer k >= 1, the goal ofthis problem is to find a set of k densest subgraphs that may share somevertices. The objective function to be maximized takes into account both thedensity of the subgraphs and the distance between subgraphs in the solution.  The Top-k Overlapping Densest Subgraphs problem has been shown to admit a1/10-factor approximation algorithm. Furthermore, the computational complexityof the problem has been left open. In this paper, we present contributionsconcerning the approximability and the computational complexity of the problem.For the approximability, we present approximation algorithms that improves theapproximation factor to 1/2 , when k is bounded by the vertex set, and to 2/3when k is a constant. For the computational complexity, we show that theproblem is NP-hard even when k = 3.

Top-k Overlapping Densest Subgraphs: Approximation and Complexity