Novel Dense Subgraph Discovery Primitives: Risk Aversion and Exclusion Queries.

In the densest subgraph problem, given an undirected graph G(V, E, w) with non-negative edge weights we are asked to find a set of nodes \(S\subseteq V\) that maximizes the degree density w(S)/|S|, where w(S) is the sum of the weights of the edges in the graph induced by S. This problem is solvable in polynomial time, and in general is well studied. But what happens when the edge weights are negative? Is the problem still solvable in polynomial time? Also, why should we care about the densest subgraph problem in the presence of negative weights?