Research On The Discovery Methed Of Steiner Components Bsased On Data Graph

Given a data graph G,the Steiner components with the maximum connectivity(SMCC)is a subgraph of G,which has the maximum connectivity and the maximum number of vertices.The SMCC contained query q has been widely used in many fields in real life,e.g,in social network,can find the most closely linked social groups;in E-commerce network,can recommend products for users with close contact;in Collaboration network,can find the teams that are close and able to work well together.This paper researches the query problem of Steiner components with the maximum connectivity SMCC from the following several aspects.Firstly,by conducting an analysis of the existing algorithms,we found the problems of the existing algorithms are much time to contruct the indexes,the large indexes and inefficient.Secondly,based on the properties of the k-edge connected components,we proposed the efficient index structure ST(Set Tree),such that to make a hierarchaical index for the part of k-edge connected components and the part of not k-edge connected components which were contained in the same(k-1)-edge connected components for the graph G.Every subtree rooted at the node of ST was corresponded to a k-edge connected component,compared to the existing spanning tree index,ST index reduces the number of index nodes and the time of index constructing.Thirdly,the algorithm SMCC-ST of computing SMCC and the algorithm SMCC_L-ST of computing SMCC_L which the SMCC contrained with the numbers of vertexes are proposed based on ST index,such that to avoid the large indexs and reduce the number of vertexes that need visited in computing SMCC,SMCC_L and the connectivity,so the query efficiency is improved.Finally,our experimental results on 9 real datasets verify the efficiency of our method in terms of different metrics,including indexing time,index size,query processing time,the number of visited vertexes.