Polynomial-Time Algorithm for Finding Densest Subgraphs in Uncertain Graphs

摘要

This paper studies the problem of finding the densest subgraph in an uncertain graph. Due to uncertainty in graphs, the traditional definitions of dense subgraphs are not applicable to uncertain graphs. In this paper, we introduce the expected density of an uncertain graph. Based on the expected density, we formalize the problem that, given an uncertain graph G = (V, E, P) and a set of vertices R {is contained in} V, finds an induced subgraph G' = (V', E', P') of G of the maximum expected density such that R {is contained in} V'. We show that the optimal solution can be found in O(nmlog(n~2/m)) time using maximum flow techniques, where n = |V| and m = |E|. Moreover, unlike the existing models of uncertain graphs, the model used in this paper is quite general, which doesn't assume the existence of edges is mutually independent.