Few days ago I uploaded on Arxiv our preprint “Novel Dense Subgraph Discovery Primitives: Risk Aversion and Exclusion Queries”.  This is joint work with Tianyi, Nao, and Jakub.

In this paper we study the following extension of the densest subgraph problem (DSP) that is known to be solvable exactly in polynomial time on graphs with non-negative edge weights:

How do we solve the DSP when there exist negative edges in the graph?

     This question was motivated by two applications that we also introduce in this paper. The first application is finding dense subgraphs in multilayer networks that exclude certain types of edges. For example, consider Twitter. Different layers of user interactions are naturally associated with it, including the follow, mention, quote, reply, like, favorite layers. How do we find a dense subgraph that excludes replies? The second application is finding dense subgraphs in uncertain graphs with small risk. You can read more about the applications, and our contributions here. The code and the uncertain graph datasets are available on Github:

https://github.com/negativedsd/Negative-Densest-Subgraph-Discovery