Please use this identifier to cite or link to this item: http://cmuir.cmu.ac.th/jspui/handle/6653943832/63686
Title: Impact of minimum-cut density-balanced partitioning solutions in distributed webpage ranking
Authors: Sumalee Sangamuang
Pruet Boonma
Juggapong Natwichai
Wanpracha Art Chaovalitwongse
Keywords: Mathematics
Issue Date: 1-Jan-2019
Abstract: © 2019, Springer-Verlag GmbH Germany, part of Springer Nature. This paper presents a new mathematical programming model and a solution approach for a special class of graph partitioning problem. The problem studied here is in the context of distributed web search, in which a very large world-wide-web graph is partitioned to improve the efficiency of webpage ranking (known as PageRank). Although graph partitioning problems have been widely studied and there have been several computational algorithms and mathematical programming models in the literature, the graph partitioning problem for PageRank imposes unique constraints on the density balance. This problem is called the min-cut density-balanced partitioning problem. In this paper, we propose a new mathematical programming model and a solution approach to efficiently solve this min-cut density-balanced partitioning problem. As the objective on the minimum cut and the constraint on the density balance are not the direct performance measure of PageRank, we also investigate the performance of the solutions obtained from a MIP solver and our approach on the ranking’s accuracy and the local ranking’s computation times. The experiment results show both solutions are comparable in terms of the ranking’s accuracy and the local ranking’s computation times whereas it is much faster to obtain the partitioning solutions using our approach.
URI: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85062696480&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/63686
ISSN: 18624480
18624472
Appears in Collections:CMUL: Journal Articles

Files in This Item:
There are no files associated with this item.


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