A novel green algorithm for sampling complex networks

Researches of complex networks such as social networks are becoming popular in recent years. Due to the large scale and complex structure of these networks, analysis and studies on a complete network require a lot of computational resources and storage space, which will also consume a large amount of energy. Sampling algorithms provide a new green approach for this problem. Especially some researches related to network communities with high energy consumption can be directly conducted on the sampled networks, which maintain the community structure of original networks. In this paper, we propose a sampling algorithm named Improved Forest Fire Sampling algorithm based on PageRank (IFFST-PR) based on the idea of Forest Fire Sampling and PageRank algorithm. IFFST-PR can maintain the community structure of original networks. We select a set of key nodes called community cluster center, according to a coefficient named community coefficient. Besides, we adopt PageRank to decide the order of initiative sampling nodes. To make a comprehensive comparison of IFFST-PR with other 6 algorithms, we use network community profile and Kolmogorov-Smirno D statistics to prove the consistency between sampled networks and original networks. Experiments applied on 3 different data sets show that IFFST-PR has better performance in terms of most parameters defined in network community profile than those of the other 6 algorithms.