Keyword Search Based On Dense Subgraph

In recent years,with the development of information technology and the universalization of Internet socialization,the daily social production and user socialization will generate a large amount of information data.In many realistic scenarios,these information data can be organized among themselves in the form of graph data.Therefore,mining and analyzing the target structures embedded in the corresponding graph data has important application value.Graph keyword search technology is one of the popular graph data analysis direction in recent years.Users can query the corresponding target graph structure only by giving the target keyword of the query,without knowing the underlying structure of graph data and mastering the structured graph query language in advance.The traditional keyword search problem focuses only on the connection relations between keyword vertices,while ignoring the connection relations between non-keyword vertices.However,in some cases,users want to obtain the target substructure of the graph covering all query keywords,which is a tightly connected structure in the whole.To address the shortcomings of the existing techniques,this paper proposes a keyword query problem based on dense subgraphs,which combines the keyword query problem in the field of graph data mining with the dense subgraph search problem,and requires that the returned query results not only contain all query keywords but also have high consistency.The research work in this paper can be summarized as follows:1.The problem of minimal dense graphs with the largest core-number covering all query keywords is proposed.Inputting a set of query keywords Q,we require to return the dense subgraph with the largest core-number covering all query keywords in the set Q,and there does not exist one of its subgraphs that can also cover all keywords and have the same core-number.In this way,this not only reflects the connection between the keywords,but also ensures the relevance of the query results.2.The search problem of minimal dense graphs with the largest core-number covering all query keywords is decomposed into two subproblems,one is to search the dense subgraph covering all query keywords with the largest core-number,and the other is to prune the above dense subgraph to obtain the minimal dense core covering all query keywords.For the first subproblem,a basic greedy algorithm is first proposed,and then a top-down search method and an index tree based optimization method are proposed.For the second subproblem,the basic algorithm of iterative deletion is proposed,and the concept of "k related group" is proposed to optimize the algorithm by calculating the set of vertices to be associated with deletion when the degree constraint k is satisfied offline,and then the optimization strategy of local extension is proposed.3.For the above algorithms,experiments were conducted on three real data sets to test the effect of different numbers of query keywords on the efficiency of the algorithms,and the results show that several algorithms proposed in this paper are very effective.