Numerous graph mining applications rely on detecting subgraphs which are large near-cliques. Since formulations that are geared towards finding large near-cliques are hard and frequently inapproximable due to connections with the Maximum Clique problem, the poly-time solvable densest subgraph problem which maximizes the average degree over all possible subgraphs "lies at the core of large scale data mining" [10]. However, frequently the densest subgraph problem fails in detecting large near-cliques in networks.
No takes yet. Share an insight, caveat, or question.
Charalampos E. Tsourakakis (2015) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: