Publications
CONFERENCE (INTERNATIONAL) Boosting PageRank Scores by Optimizing Internal Link Structure
Naoto Ohsaka (UTokyo), Tomohiro Sonobe (NII), Naonori Kakimura (UTokyo), Takuro Fukunaga (Riken AIP), Sumio Fujita, Ken-ichi Kawarabayashi (NII)
The 29th International Conference on Database and Expert Systems Applications (DEXA 2018)
September 03, 2018
We consider and formulate problems of PageRank score boosting motivated by applications such as eff ective web advertisements. More precisely, given a graph, our problem requires to nd a xed-size set of missing edges that maximizes the minimum PageRank score among a given set of vertices. We also provide two variants of the formulated problem. Then we analyze theoretical properties of the three problems to show that all of them are NP-hard. To overcome these diculties, we propose heuristic-based algorithms for them. Finally, we perform experiments on several real-world webgraphs to verify the eff ectiveness of the proposed algorithms compared to baseline algorithms. Speci cally, our algorithm achieves 100 times improvements of the minimum PageRank score among selected 100 webpages by adding only dozens of hyperlinks.
Paper :
Boosting PageRank Scores by Optimizing Internal Link Structure
(external link)