Index-Based Densest Clique Percolation Community Search in Networks.

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 k<alternatives><inline-graphic xlink:href="yuan-ieq1-2783933.gif"/> </alternatives>-clique percolation community model was proposed and has been proven effective in many applications. Motivated by this, in this paper, we adopt the k <alternatives><inline-graphic xlink:href="yuan-ieq2-2783933.gif"/></alternatives>-clique percolation community model and study the densest clique percolation community search problem which aims to find the k<alternatives> <inline-graphic xlink:href="yuan-ieq3-2783933.gif"/></alternatives>-clique percolation community with the maximum k<alternatives> <inline-graphic xlink:href="yuan-ieq4-2783933.gif"/></alternatives> 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 k<alternatives> <inline-graphic xlink:href="yuan-ieq6-2783933.gif"/></alternatives>- \mathsf Index<alternatives> <inline-graphic xlink:href="yuan-ieq7-2783933.gif"/></alternatives>, to preserve the maximal cliques and their connectivity information of the input graph. With \mathsf DCPC<alternatives><inline-graphic xlink:href="yuan-ieq8-2783933.gif"/></alternatives>- \mathsf Index<alternatives> <inline-graphic xlink:href="yuan-ieq9-2783933.gif"/></alternatives>, we can answer the densest clique percolation community query efficiently. Besides, we also propose an index construction algorithm based on the definition of \mathsf DCPC<alternatives> <inline-graphic xlink:href="yuan-ieq10-2783933.gif"/></alternatives>- \mathsf Index<alternatives> <inline-graphic xlink:href="yuan-ieq11-2783933.gif"/></alternatives> 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. [ABSTRACT FROM AUTHOR]