Key-core: cohesive keyword subgraph exploration in large graphs

Keyword search in graphs has been extensively studied in the literature. Given a keyword query, existing solutions mainly focus on finding all/top-k individual answers. Each individual answer is a subgraph/subtree that contains some structural information regarding a certain subset of nodes containing the keywords. Nevertheless, from the individually answers, it is difficult for a user to see the big picture and identify how the answers are correlated to each other. In this paper, we define a new structure, named key-core, to find cohesive subgraphs for a keyword query. Briefly speaking, a key-core is a cohesive subgraph that contains many highly correlated keyword search answers. A key-core is not only cohesive structurally, but also closely related to the user given keywords. In order to make the keyword search more flexible, we also define four key-operators, namely key-intersection, key-union, key-difference, and key-association, to manipulate the key-cores. The key-operators enable users to form complex queries and refine the queries on demand. We propose algorithms to compute the key-cores and key-operators efficiently. We conduct extensive performance studies on large real datasets to demonstrate the effectiveness and efficiency of our approach.