2019/07/23 by Atsushi Suzuki, Hideaki Ishii, Suzuki, Atsushi +1
Computer Science · Decision Sciences · Engineering · Physics and Astronomy · #Complex Network Analysis Techniques #Expert finding and Q&A systems #FOS: Electrical engineering #Game Theory and Applications #Systems and Control (eess.SY) #cs.SY #eess.SY #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1907.09979
16 pages, 8 figures
arxiv created 2019/07/23 · openalex publication_date 2019/07/23 · arxiv updated 2019/07/24 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28
PageRank is a well-known centrality measure for the web used in search engines, representing the importance of each web page. In this paper, we follow the line of recent research on the development of distributed algorithms for computation of PageRank, where each page computes its own PageRank value by interacting with pages connected over hyperlinks. Our approach is novel in that it is based on a reinterpretation of PageRank, which leads us to a set of algorithms with exponential convergence rates. We first employ gossip-type randomization for the page selections in the update iterations. Then, the algorithms are generalized to deterministic ones, allowing simultaneous updates by multiple pages. Finally, based on these algorithms, we propose a clustering-based scheme, in which groups of pages make updates by locally interacting among themselves many times to expedite the convergence. In comparison with other existing techniques, significant advantages can be exhibited in their convergence performance, as demonstrated via numerical examples using real web data, and also in the limited amount of communication required among pages.