PROJECT TITLE :

Index-based Intimate-Core Community Search in Large Weighted Graphs

ABSTRACT:

On a number of different kinds of graphs, community search that locates communities dependent on a query has been investigated. Intimate-core group (community) search is an example of community search that is performed over a weighted graph. The goal of this type of community search is to locate a connected k-core that contains all query nodes and has the lowest group weight. However, the existing methods that are considered state-of-the-art begin the process of refining an answer from the maximal k-core, which is practically inefficient for large networks. In this paper, we develop an efficient framework for finding intimate-core groups in graphs. We refer to this as the local exploration k-core search (LEKS) algorithm. After connecting query nodes with a small-weighted spanning tree, which we propose, we expand the tree level by level until we reach a connected k-core, which is then further refined into an intimate-core group. In addition, we develop a weighted-core index (WC-index) and two new algorithms for expansion and refinement phases in LEKS that are based on the WC-index. This is done to support the intimate group search over large weighted graphs. To be more specific, we propose a WC-index-based expansion that makes use of a two-level expansion consisting of k-breadth and 1-depth in order to locate a candidate graph of an intimate-core group in a time-efficient manner. We suggest two approaches to the removal of graphs: the first, coarse-grained refinement, is intended for large graphs and can delete a batch of nodes in a few iterations; the second, fine-grained refinement, is intended for small graphs and can remove nodes carefully while achieving high-quality answers. Extensive testing on operational networks containing ground-truth communities has shown that the proposed methods are both effective and efficient.