Local Breadth-first Expansion and Shrinking for Densest Subgraph Detection
Sun He-l · Journal of Chinese Computer Systems · 2014
The densest subgraph detection is an important graph-mining problem which has been applied in many fields. In this paper,we explore the densest subgraph detection problem,and propose a new algorithm,called local breadth-first expansion and shrinking for densest subgraph detection,which is designed on the basis of the existing algorithms. First,an optimal vertex is selected,and expanded to its neighbor vertices to be expanded. Second,shrink the resultant vertex set to get the local densest subgraph in this iteration. Third we remove the subgraph that is gotten in the second step from the graph,and iteratively execute the above operations in the remaining graph until the complement graph has no vertex,in each iteration,we record the subgraph which has maximal average density. We propose the advantages of local neighborhood improve the average density of the optimal vertex set effectively. According to the experimental results,we can find the average density is greater than the existing algorithms. Our method achieves a higher stability and feasibility compared with other proposed approaches.