arXiv preprint ·
Constant-Factor Local Approximation for Bipartite Densest Subgraph
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Given a vertex $v$ in a large bipartite graph $G$, can one quickly find a small densely connected region near $v$? This is the algorithmic core of many fraud detection, community detection, and recommender systems. One would like a local algorithm, i.e., an algorithm that probes $G$ in only a small number of locations to find such a region. Our main contribution is the first constant-factor local approximation, independent of the maximum degree of the graph, for the classical notion of bipartite density: if the sides of a bipartite subgraph are $S$ and $T$, its density is $d(S,T):=e(S,T)/\sqrt{|S||T|}$, where $e(S,T)$ is the number of edges between $S$ and $T$. We consider cohesive dense subgraphs, since every dense subgraph contains a cohesive core of at least the same density. For such a cohesive dense subgraph $S\mathbin{\dot\cup}T$ with at most $k$ vertices per side, our algorithm, starting from any vertex in $S\mathbin{\dot\cup}T$, uses $O_ε(k^{4+ε})$ neighbor queries to find a subgraph $X\mathbin{\dot\cup}Y$ of density $Ω_ε(d(S,T))$ on $O_ε(k^{2+ε})$ vertices, for every fixed $ε>0$. Our result improves upon the result of Andersen (2010), whose approximation guarantee depends logarithmically on the maximum degree. We complement our positive result with information-theoretic and computational limitations showing that the quadratic dependence on $k$ in the output size is essentially unavoidable for constant-factor approximation. Our main technical innovation is an adaptation of the Lovász-Simonovits curve to the bipartite density problem, based on weak-$\ell_p$ norm bounds.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Competitive Online Clustering with Movement Cost
Near-Linear Time Maximum Clique in Circular Arc Graphs
On the Metric Distortion of the Minimum Spanning Tree Problem
Computing faster with a full memory: Catalytic algorithms break time-space lower bounds
Online geometric matching and segments block points
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.