Efficient Dense Structure Mining Using MapReduce

Structure mining plays an important part in the researches in biology, physics, Internet and telecommunications in recently emerging network science. As a main task in this area, the problem of structure mining on graph has attracted much interest and been studied in variant avenues in prior works. However, most of these works mainly rely on single chip computational capacity and have been constrained by local optimization. Thus it is an impossible mission for these methods to process massive graphs. In this paper, we propose an unified distributed method in solving some critical graph mining problems on top of a cluster system with the help of MapReduce. These problems include graph transformation, subgraph partition, maximal clique enumeration, connected component finding and community detection. All of these methods are implemented to fully utilize MapReduce execution mechanism, namely the ¿map-reduce¿ process. Moreover, considering how our algorithms can be applied in further ¿cloud¿ service, we employ several large scale datasets to demonstrate the efficiency and scalability of our solutions.

1. Introduction

Recent link mining on graphs has been emerging as a prevailing interest and produced many practical applications, whose emphasis points are on designing novel algorithms and revealing underlying patterns of real-world graphs. Among most of the applications in graph mining, maximal clique enumeration and community detection are two well-studied problems, not only for their efficiency requirement [8], [11], [2] but also for extensive engineering applications [9]. Besides those locally optimized algorithms, there are also some parallel or distributed solutions, such as [6], [7]. However, most of these works are based on theoretical distributed methods and do not provide systematic ones.