Improving Random Walk Sampling, Inspired by Two Methods of Choosing Seed Node And No-Retracing With Combination of them with Page Rank Algorithm

One of the algorithms used for sampling complex networks is the classical random walk algorithm, which has been considered due to its good performance. But speed and energy consumption can also be improved by reducing size of input data. In this study, two random walk algorithms inspired by two methods, choosing seed node, and no-retracing algorithm which obtained by changing the classical random walk algorithm, and combining these three algorithms with google page rank algorithm, are discussed. This is done to preserve important nodes and reduce the size of the input data. This sampling was done from the United States flight network database. Also, important characteristics obtained in sampling, such as sampling efficiency, degree distribution, average degree, and average clustering coefficient have been investigated. The algorithms studied in this research each have their own advantages and disadvantages. For example, the no-retracing shows better performance in terms of time and average clustering coefficient. This efficiency is even greater when we use a combination of no-retracing algorithm with google page ranking algorithm. These algorithms can be used when speed is important in decision making, such as deciding on airlines and public transportation, etc. These algorithms are also more energy efficient than the studied algorithms.