Research And Application Of Cohesive Subgraph Search Algorithm In Large Temporal Graphs

Temporal graph contains nodes and temporal edges,which are generally used to represent the time-varying relationship between entities and are widely used in the real world.The problem of CohesiveSubgraph Mining(CSM)is a basic and important work in the field of graph theory,and it is also widely studied in the temporal graph.However,most of the existing researches focus on the problem of cohesive subgraph detection(CSD),i.e.,finding out all defined subgraphs in the whole temporal graph.When the size of the temporal graph is too large,solving the problem will take a large amount of time and space,and cause too many results with poor interpretability.This study focuses on the cohesive subgraph search(CSS)problem in large temporal graphs.Specifically,given a query node,find the cohesive subgraph that satisfies certain conditions and contains a query node.To this end,first,this research quote a model as a kind of cohesive temporal graph called(?,?)-continual k-core and proves that the search problem of this model is NP-hard.Then,based on enumeration strategy,two different search algorithms are proposed,which are called Exact-VD and Exact-VE.Exact-VD uses the depth-first strategy to find the target subgraph from top to down by gradually deleting the vertices from the initially reduced subgraph;Exact-VE starts from the query vertices and continuously expands the enumeration vertices in the neighborhood until it reaches the target subgraph.At the same time,the two algorithms have several different reduction rules to make the enumeration algorithm more efficient.In addition,this study also proposes an approximate algorithm Approx-LS,and proves the approximate ratio of the algorithm.Approx-LS algorithm uses greedy strategy to extend candidate subgraphs until the results are obtained,which greatly improves the search speed.Finally,a large number of experimental analyses are carried out on the proposed algorithms,and the effectiveness and efficiency of the three algorithms are verified on four real world datasets,and an application case is given.