Research And Implementation Of Densest Subgraph Detection Method Based On Local Neighborhood

There exist various multi-class object and various relations between objects in the complex networks, these networks exhibit the aggregation effect based on the average density, provide us opportunities to study the deep relationship between objects. The densest subgraph detection is an important graph-mining problem in various applications, such as computer science, biological sciences, social science and physics. The purpose of the problem is to find a subgraph, with relatively close edges between nodes, and has the maximum average density. To propose improved algorithm with high accuracy and stability, and efficient calculation strategy, is the key to this article.In this paper, we propose a new algorithm; local breadth-first expansion and shrinking for densest subgraph detection in a given graph. First, an optimal node is selected, and expanded to its neighbor nodes until there is no node to be expanded. Second, shrink the resultant node 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 node. In each iteration, we record the subgraph which has higher average density, the remain subgraph will be the densest subgraph at last. Further, in order to solve the problem of densest subgraph detection in big graph, we use the divide and conquer strategy, and propose breadth search combined with minimum cut graph partitioning method to cut the big graph into many subgraphs, next we use single machine and cluster to detect the top-K densest subgraphs. In single machine, we use the parallel sliding partition strategy, subgraphs were loaded into memory to get densest subgraph and write back disk to cover the original partition; in the cluster, we implement the algorithm in Map Reduce based on Hadoop and in BSP based on Giraph respectively.The experimental results shows that the proposed local breadth-first expansion and shrinking algorithm can effectively detect a denser subgraph, and more stable, compared to the existing algorithms. For processing big graph, breadth search combined with minimum cut can effectively partition the big graph, and has good compatibility to the densest subgraph detection algorithm; parallel sliding partition strategy can deal with big graph on a single machine; in the cluster, BSP is more suitable for solving the densest subgraph detection than Map Reduce, cluster can effectively improve the detection efficiency.