Residential Collegefalse
Status已發表Published
Distributed PageRank computation with improved round complexities
Luo, Siqiang1; Wu, Xiaowei2; Kao, Ben3
2022-07
Source PublicationInformation Sciences
ISSN0020-0255
Volume607Pages:109-125
Abstract

PageRank is a classic measure that effectively evaluates the importance of nodes in large graphs. It has been applied in numerous applications spanning data mining, Web algorithms, recommendation systems, load balancing, search and connectivity structures identification. Computing PageRank for large graphs is challenging and this has motivated the studies of distributed algorithms to compute PageRank. Previously, little works have been spent on the distributed PageRank algorithms with strong guarantees on both complexity and accuracy. In this paper, we focus on the theoretical aspect and study the complexity of distributed PageRank computation based on the well-known congested-clique model with a bandwidth generalization. An existing algorithm proposed by Sarma et al. (2015) can be applied in this model, which estimates PageRanks in an n-node graph using, with high probability, O(logn) communication rounds and a bandwidth of O((logn)) bits. We present Radar-Push (RP), which is a distributed PageRank algorithm that is strictly better in round complexities. Specifically, Radar-Push uses O(loglogn) communication rounds and an edge bandwidth of O((logn)) bits. We further show that Radar-Push can be adapted to efficiently compute an important variant of PageRank, namely, the batch one-hop personalized PageRank, in O(loglogn) communication rounds.

KeywordAlgorithms Distributed Computation Graph Pagerank
DOI10.1016/j.ins.2022.05.108
URLView the original
Indexed BySCIE
Language英語English
WOS Research AreaComputer Science
WOS SubjectComputer Science, Information Systems
WOS IDWOS:000817892200007
PublisherELSEVIER SCIENCE INCSTE 800, 230 PARK AVE, NEW YORK, NY 10169
Scopus ID2-s2.0-85131464446
Fulltext Access
Citation statistics
Document TypeJournal article
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Corresponding AuthorLuo, Siqiang; Wu, Xiaowei; Kao, Ben
Affiliation1.Nanyang Technological University, Singapore
2.IOTSC, University of Macau, China
3.University of Hong Kong, China
Corresponding Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Luo, Siqiang,Wu, Xiaowei,Kao, Ben. Distributed PageRank computation with improved round complexities[J]. Information Sciences, 2022, 607, 109-125.
APA Luo, Siqiang., Wu, Xiaowei., & Kao, Ben (2022). Distributed PageRank computation with improved round complexities. Information Sciences, 607, 109-125.
MLA Luo, Siqiang,et al."Distributed PageRank computation with improved round complexities".Information Sciences 607(2022):109-125.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Luo, Siqiang]'s Articles
[Wu, Xiaowei]'s Articles
[Kao, Ben]'s Articles
Baidu academic
Similar articles in Baidu academic
[Luo, Siqiang]'s Articles
[Wu, Xiaowei]'s Articles
[Kao, Ben]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Luo, Siqiang]'s Articles
[Wu, Xiaowei]'s Articles
[Kao, Ben]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.