Algorithms And Applications Of Dense Subgraphs Search Based On Keyword

In recent years,the keyword search problem has caused extensive research in the academic world.The purpose is to find the substructure related to the keyword from the original picture for a given set of keywords.However,the existing classical algorithms are mainly devoted to finding a tightly structured tree structure and substructure,ignoring a key measurement method-density,density reflects the firmness and closeness of the relationship between the nodes containing the keywords in the substructure.degree.Therefore,for a given set of keywords,this paper looks for a close subgraph problem that contains these keywords,which has the characteristics of high density and high degree of tightness.The keyword-based compact subgraph search problem can be divided into two types according to the actual application scenario,namely the minimally compact subgraph search problem(min-DTS)for keyword coverage and the great compaction for shared keywords.Graph search problem(max-DTS),the third and fourth chapters of this paper discuss these two issues.For the tight subgraph search problem for keyword coverage,the purpose is to find a compact subgraph containing the query keyword set and the highest truss value.For this problem,this paper first proposes an obvious basic algorithm,but the algorithm is less efficient and does not meet the requirements of online search.Therefore,this paper proposes a new type of KTruss index,and proposes an efficient search algorithm based on the index.According to the observation and analysis,this paper proposes several optimization algorithms from two aspects.For the extremely compact subgraph search problem for shared keywords,the purpose is to find a keyword with a certain ratio of query keywords for all nodes in the subgraph for a given truss constraint value,and meet the truss value requirement.Greatly compact subgraph.For this problem,this paper first analyzes the difficulties and solutions of the problem.Because the intuitive basic algorithm is inefficient,this paper also proposes a unique tree index,EquiTree index.Based on this index,this paper proposes a more advanced search algorithm.Finally,this paper uses the real data set to report the experimental results for the above two problems.It can be seen from the report that the algorithm proposed in this paper can solve the compact subgraph search problem in a good time range.