Stratified sampling large relational networks using topologically divided stratums

One challenge of visualizing the relational networks in computer screen is the scale of relational networks is too large. One solution is deriving a representative sample from a huge real graph. The purpose is to select a set of vertices and edges in graph so that the induced graph obeys some general characteristics, and so the sampled graphs can be used for simulations and further analysis. In this paper, we propose a stratified sampling algorithm using topologically divided stratums for large relational networks. In addition, we evaluate our algorithm on several well-known datasets. The experimental results show that our algorithm outperforms the previous methods.