| As the data scale grows,graph data mining is used to explore the hidden value in large-scale graph data,and plays an important role in many fields such as physics,biology,and social networks.Dense subgraph mining is an important branch of subgraph query in graph data mining,and truss decomposition algorithm is a basic solution for dense subgraph mining,but the existing truss decomposition algorithm is not efficient enough.This paper focuses on how to efficiently query the largest k-truss subgraph in a connected graph.The existing algorithm has many problems,such as too much iterations,high backtracking cost,redundant calculation,and difficulty in processing large-scale graph data in limited time.This research has the following contribution:Firstly,to solve the problem of too much iterations in the existing truss decomposition algorithm,this paper proposes a subgraph prediction and filtering strategy,and a density determination for the core structure based on the clique structure considering the truss structure as a dense subgraph between the core structure and the clique structure.To solve the problem of redundant calculation,this paper proposes a method of graph-oriented processing,edge deletion termination judgment based on clique structure and triangle false counting.Our method reduces the number of iterations,eliminates some redundant calculation,and saves the query time on largescale graph data.Secondly,to solve the problem of high backtracking cost in existing algorithms,this paper proposes a dynamic step size based on loss model to obtains the appropriate ratio by testing on the graph data for a better proportion.This paper also proposes a parallel implementation based on GPU aiming at the timeliness of processing largescale graph data.The algorithm runs in parallel on GPU to make full use of computer resources for a faster speed to process large-scale graph data.Finally,the experiments shows that our method speeds up 20% compared with the existing algorithm. |
PDF Full Text Request