Graph Sampling Algorithm Based on Representative Node Expansion to Maintain Community Structure
Graph sampling is widely used in real life as a method to simplify large-scale graphs and retain specified properties.However,most of the current research focuses on preserving node-level properties,such as degree distribution,while ignoring more important information such as the community structure of graphs.To solve this problem,a graph sampling algorithm is pro-posed to maintain the community structure.The algorithm is divided into two steps.The first step is to initialize the community representative points,and the node importance is calculated according to the proposed node importance calculation formula,and then the representative nodes of each community are selected.The second step is to expand the community structure.For each community,it selects the node that can introduce the least additional neighbors to join the community until the upper limit of the community node is reached.Comparative experiments are conducted on a number of real data sets,and multiple evaluation indica-tors are adopted to evaluate the experimental results.Experimental results show that the proposed sampling algorithm can well maintain the overall community structure,and provides a feasible solution for sampling community structure of large-scale graphs.
NETL
NSTL
万方数据
