An Improved PIES By Vertex Degree In Massive Graph Stream Sampling

Graph sampling is important to application areas including social-network, biology and information network research. Most real-world graphs are not only massive in scale, but also changing constantly. While analyzing these graph datasets, certain sampling methods are used to produce representative subgraphs, and make reasonable trade-off between performance and precision. However, traditional methods are targeted at static graphs, the whole graph must be accessible during sampling. If the graph is too large to load into memory or it's changing while analyzing, those methods will not be viable.Unlike static sampling methods, streaming graph sampling assumes that the sampling algorithm cannot access the entire graph at any time, which may cause inaccurate vertex/edge replacement, especially when the replacement policy is unaware of graph topology, thus the resulting subgraph will deviate from original graph on some key properties including degree distribution, k-core distribution etc.This research propose inverse degree based vertex replacement policy, to improve recent streaming graph sampling algorithms, by balancing the vertex replacement among largely differentiated vertexes. In this research, various real-world graph datasets are used to evaluate the efficacy of our proposed methods. According to experimental result, our method is able to generate samples that preserve major graph distributions better than current algorithms in most cases.