The Research On K-core Subgraph Query Algorithm

Given a graph G,a query node v and a value k specified by the user,k-core subgraph query is to find a subgraph concluding the query node,in which each degree of the vertices is not less than k.K-core subgraph query is applied to friend recommendation,advertising on social networks,disease control and semantic expansion and so on.K-core subgraph query is deeply studied in the paper from the following respects.Firstly,through the analysis of the existing algorithms,we find the common problem that there are a lot of redundant queries when the k-core subgraph is constructed.Secondly,we propose an algorithm named pre_CST in which the given graph is pretreated.The algorithm proposes that the neighbor nodes of each node are sorted according to their degrees.At the same time,the number of neighbor nodes whose degrees are more than k is recorded in the algorithm.The result of pre_CST will be used later.Thirdly,we propose an efficient algorithm about k-core subgraph query,named CST.The result of pre_CST is utilized and three methods are proposed to avoid redundant queries in the algorithm.The first one is when traversing the neighbor nodes of a node,if the degree of some neighbor node is less than k,the node after this neighbor will not be traversed.The second one is when the number of neighbor nodes whose degrees are no less than k is less than k,the current node will not be added into the candidate graph.The third one is sorting the candidate nodes which will be added into the k-core subgraph by priority queue and adding the node with the largest number of edges between candidate nodes and the candidate graph into the candidate graph and reducing the adding of invalid nodes.The methods proposed above can avoid dealing with invalid nodes,thus reducing redundant queries and improving the efficiency.Finally,based on real data sets,we verify the efficiency of the algorithm proposed in this paper through different evaluation criteria.