Discovery of top-k dense subgraphs in dynamic graph collections

Abstract. Dense subgraph discovery is a key issue in graph mining, due to its importance in several applications, such as correlation analysis, community discovery in the Web, gene co-expression and protein-protein interactions in bioinformatics. In this work, we study the discovery of the top-k dense subgraphs in a set of graphs. After the investigation of the problem in its static case, we extend the methodology to work with dy-namic graph collections, where the graph collection changes over time. Our methodology is based on lower and upper bounds of the density, resulting in a reduction of the number of exact density computations. Our algorithms do not rely on user-dened threshold values and the only input required is the number of dense subgraphs in the result (k). In addition to the exact algorithms, an approximation algorithm is pro-vided for top-k dense subgraph discovery, which trades result accuracy for speed. We show that a signicant number of exact density compu-tations is avoided, resulting in ecient monitoring of the top-k dense subgraphs.