Abstract | ||
---|---|---|
PageRank is a core component in search engine. In a wide range of PageRank applications, only few pages often need to be evaluated in some scenarios. In this paper, we propose Markov chain Monte Carlo (MCMC) method for solving reverse PageRank problem. Different from the previous MCMC method that solves the problem via simulating surfing the internet forward, we adopt MCMC method to solve PageRank problem via simulating surfing the internet backward, called reverse PageRank. For a selected page, the MCMC method can be used to simulate the network to find all the possible paths from any other page to the selected page. The major advantage of the proposed method is that only one page is evaluated, instead of computing the whole pages. Following this method, we can independently evaluate the importance of the selected page. As MCMC method has parallelism and robustness in nature, it is suitable to be implemented and optimized on GPU. We have simulated the real world networks to evaluate the performance of the method. The results demonstrate that our MCMC method can be implemented efficiently on GPU and outperforms the other existing methods when few pages are evaluated. We then discuss and analyze the important properties of the MCMC method for reverse PageRank problem based on the experiment results. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1109/BDCloud-SocialCom-SustainCom.2016.22 | 2016 IEEE International Conferences on Big Data and Cloud Computing (BDCloud), Social Computing and Networking (SocialCom), Sustainable Computing and Communications (SustainCom) (BDCloud-SocialCom-SustainCom) |
Keywords | Field | DocType |
PageRank,reverse,paralleling,GPU,Monte Calro method | PageRank,Search engine,Markov process,Markov chain Monte Carlo,Upper and lower bounds,Computer science,Parallel computing,Theoretical computer science,Robustness (computer science),Google matrix,Distributed computing,The Internet | Conference |
ISBN | Citations | PageRank |
978-1-5090-3937-1 | 0 | 0.34 |
References | Authors | |
2 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Siyan Lai | 1 | 6 | 2.13 |
Yang Yi | 2 | 207 | 14.62 |
Menghan Guo | 3 | 0 | 0.34 |
Xiaola Lin | 4 | 1099 | 78.09 |