Research On Maximam (k,r)-core Graph Query Based On Similarity

Given the similarity between vertex degree k and vertex r,the maximum similarity(k,r)-core query based on similarity is used to return the community that meets the condition from the graph.This community satisfies both the k-core condition and the similarity between any vertex in k-core,and when any vertex other than(k,r)-core is added,it does not satisfy(k,r)-core.The solution process of the existing method is divided into three steps: the first step is to calculate the similarity of the vertex pairs corresponding to each edge in the graph and delete the dissimilar edges;the second step is to calculate k-core;the third steps is to validate the k-core subgraph.Through the analysis,it can be seen that the existing methods have the problem of low efficiency caused by repeated calculation of vertices and edges.In this paper,the solution method of k-core is studied,and the specific contents are as follows.Firstly,the analysis shows that the existing methods need to access all the vertices in the two steps of calculation,which is costly.An efficient k-core computing method was proposed to solve the redundant computing problem in the first step and the second step.This method first computes k-core.Then,the similarity of vertex pairs corresponding to each edge is calculated successively,and the dissimilar edges are deleted to quickly obtain the k-core that meets the conditions.Second,existing methods need to access all the vertices in k-core for validation in the third step processing.The lower the query efficiency of the algorithm.To solve this problem,an efficient verification method is proposed.This method firstly verifies the vertices with k and the number of similar vertices is k,and can quickly delete the vertices that do not satisfy(k,r)-core.At the same time,the intermediate results are cached to avoid the cost of multiple verification of the same vertex pair in the verification process.Finally,based on four real data sets with different characteristics,this paper conducts an in-depth comparison and analysis of the methods in this paper and the existing methods.Experimental results verify the efficiency of the proposed algorithm.