Abstract: In large scale graph,finding densest subgraph has a wide range of applications,such as community discovery,spam detection and reference relation extraction．Based on tagged undirected graph,we introduced the concept of QLS and designed an approximation algorithm DSFLC which can quickly find the densest subgraph:users submit a QLS and the algorithm will return the densest subgraph under QLS within the time that user can accept．For any ε＞0,DSFLC only needs to scan large-scale data sets O(log1+εn)times,and can ensure the approximation algorithm is a 2(1＋ε)－approximation algorithm．After analyzing DSFLC,we found this algorithm is easy to parallelize,so we chose Twitter Storm platform to parallel DSFLC algorithm．Finally,the test data sets extracted from the DBLP database verify DSFLC’ practicality and scalability.

Key words: Densest subgraph finding,QLS,DSFLC algorithm,Twitter storm platform