No icon

Index-based Densest Clique Percolation Community Search in Networks

Index-based Densest Clique Percolation Community Search in Networks

Abstract:

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, k-clique percolation community model was proposed and has been proven effective in many applications. Motivated by this, in this paper, we adopt the k-clique percolation community model and study the densest clique percolation community search problem which aims to find the k-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 k-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.

Existing System:

Predicting potential customers for a new product is essential for marketing. Social networks (e.g., Facebook) provide a promising way to do the suggestion by utilizing the friend relationship among users. Given a set of users who are already interested in a certain product, it is highly possible that other users in the community that contains the given users will be interested in the product as well. This problem can be modeled as a community search problem in the social network.

 

Proposed System:

The first work for the densest clique percolation community search. In this paper, we aim to find the densest clique percolation community which contains a given set of query nodes. To the best of our knowledge, this is the first work to study the problem of the densest clique percolation community search.

A compact index for answering the densest clique percolationcommunity query. We devise a compact index, DCPC-Index, by analyzing the structural properties of k-clique percolation communities.

An efficient index construction algorithm. Based on the definition of DCPC-Index, we can derive a straightforward approach to construct DCPC-Index.

Extensive performance studies on large real graphs. We conduct extensive performance studies on real graphs. The experimental results show the efficiency of our proposed algorithms.

Comment As:

Comment (0)