Index-Based Densest Clique Percolation Community Search in Networks

© 1989-2012 IEEE. Community search is important in graph analysis and can be used in many real applications. In the literature, various community models have been proposed. However, most of them cannot well identify the overlaps between communities which is an essential feature of real graphs. To address this issue, the κ-clique percolation community model was proposed and has been proven effective in many applications. Motivated by this, in this paper, we adopt the κ-clique percolation community model and study the densest clique percolation community search problem which aims to find the κ-clique percolation community with the maximum K value that contains a given set of query nodes. We adopt an index-based approach to solve this problem. Based on the observation that a κ-clique percolation community is a union of maximal cliques, we devise a novel compact index, DCPC - Index, to preserve the maximal cliques and their connectivity information of the input graph. With DCPC- Index, we can answer the densest clique percolation community query efficiently. Besides, we also propose an index construction algorithm based on the definition of DCPC-Index and further improve the algorithm in terms of efficiency and memory consumption. We conduct extensive performance studies on real graphs and the experimental results demonstrate the efficiency of our index-based query processing algorithm and index construction algorithm