Research On Approximate Closest Community Search Based On K-truss

Given a set of query nodes,closest community search is find a densely connected community containing all the query nodes.Closest community is based on the k-truss structure.The k-truss with a lage value of k,and fewer the redundant nodes,signifies the densely the community is.This paper we study the problem of finding high quality closest community,and the specific research content is as follows.Firstly,the existing algorithms is divided into two phases: In the first phase,find the initial k-truss community that contains all the query nodes and the k-value as large as possible and existing algorithm added too many invalid nodes during the expansion process,resulting in a small k value for the initial k-truss community.The second stage is to remove the redundant nodes in the initial k-truss community that are affected by the “free rider effect”.After the bulk delete,there are still a lot of useless nodes.Secondly,in order to solve the problem of adding invalid nodes in the first stage,an edge-based expansion strategy is proposed.The strategy determines the candidate nodes through two adjacent nodes.Compared with the existing expansion strategy,the candidate nodes of the extended subgraph are more stringent.In the case of the upper limit of the initial community size,more effective nodes can be added to the initial k-truss community with greater k value.Thirdly,In order to solve the problem of poor delete nodes,we proposed BulkDelete++ algorithm.Delete the set with maximum query distance of the nodes,Until the community is not satisfied with the k-truss nature.At this time,delete the maximum query distance nodes one by one,and this strategy can delete more nodes.Finally,experiments based on multiple real-world networks data,and compare in community k value,expansion operation time consuming and node number of result,show the effectiveness of our search algorithm.