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), 2018/9
情報検索 (Information Retrieval) データサイエンス (Data Science)
- We consider and formulate problems of PageRank score boosting motivated by applications such as effective 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 effectiveness of the proposed algorithms compared to baseline algorithms. Specically, our algorithm achieves 100 times improvements of the minimum PageRank score among selected 100 webpages by adding only dozens of hyperlinks.
Boosting PageRank Scores by Optimizing Internal Link Structure（外部サイト／External Site Link）