Guaranteed Recovery of Planted Cliques and Dense Subgraphs by Convex Relaxation

Brendan P. W. Ames ()
Additional contact information
Brendan P. W. Ames: University of Alabama

Journal of Optimization Theory and Applications, 2015, vol. 167, issue 2, No 12, 653-675

Abstract: Abstract We consider the problem of identifying the densest k-node subgraph in a given graph. We write this problem as an instance of rank-constrained cardinality minimization and then relax using the nuclear norm and one norm. Although the original combinatorial problem is NP-hard, we show that the densest k-subgraph can be recovered from the solution of our convex relaxation for certain program inputs. In particular, we establish exact recovery in the case that the input graph contains a single planted clique plus noise in the form of corrupted adjacency relationships. We also establish analogous recovery guarantees for identifying the densest subgraph of fixed size in a bipartite graph, and include results of numerical simulations for randomly generated graphs to demonstrate the efficacy of our algorithm.

Keywords: Planted clique; Densest subgraph; Nuclear norm minimization; $$l_1$$ l 1 norm minimization; 90C25; 90C59; 65K05; 68Q25 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-015-0777-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:167:y:2015:i:2:d:10.1007_s10957-015-0777-x

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-015-0777-x

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().