CS- and GA-based hybrid evolutionary sampling algorithm for large-scale social networks

Social networks analysis (SNA) has been prevalent in the research community for decades. The challenges of SNA study include the massive quantity and often incomplete availability of the network. Therefore, researchers have to estimate and/or predict the behavior, structure and topology of the network using sampling techniques. In this way, the trends and probable patterns of the massive network are predicted or identified. The existing sampling techniques, e.g., topology-based sampling, random walk sampling and random selection sampling, have critical issues on the performance on representativeness and consistent over different networks. In this paper, an efficient hybrid evolutionary sampling algorithm named GA-CS is presented for large-scale networks. Based on three measures of degree, clustering coefficient, and betweenness centrality of the nodes of the network, the proposed algorithm is compared with classical network sampling methods (BFS, SRW, MHRW, SBS, FF, RN and RE). The quality of the sampled data is assessed based on Kolmogorov–Smirnov D statistics, normalized mean square error (NMSE) and Friedman’s test. According to the results, the generated samples using the proposed sampling algorithm are more similar to the original networks compared to the other sampling methods; also, the representativeness and consistency of the proposed algorithm are high over different large-scale networks.