Mining top-k dense subgraphs from uncertain graphs

This paper investigates the problem that mining top-k dense subgraphs from uncertain graphs. Since uncertainties are inherent in graph data, traditional concepts and algorithms on mining dense subgraphs are not applicable to uncertain graphs. Hence, this paper firstly purposes the expected density concept and show the computing method to compute it in polynomial time. Based on this definition, we define a partial order on all induced subgraphs in uncertain graphs. Through this partial order, all induced subgraphs are organized to be an enumeration tree. It's carefully proved that each induced subgraph will occur in this enumeration tree exactly once. We give out a branch and bound search algorithm DS on this tree that produces top-k dense subgraphs. Meanwhile, we purpose the definition of disjoint top-k dense subgraphs and show a heuristic approximation algorithm LS based on beam search. Extensive experiments on multiple datasets indicates that the DS algorithm are both efficient and scalable, which can be used to process large graph data. The approximation algorithm LS holds an excellent performance both in efficiency and approximate quality.