For personalized recommendation in graphs, random walks starting from the user’s interest node are known as a general-purpose and fast analysis method. Specifically, Personalized PageRank (PPR), which quantifies the importance of each node by the distribution of visited nodes in random walks, determines nodes with high global importance and source proximity. However, it is difficult to balance both influences monotonically. This paper clarifies that the random walks length is effective to monotonically control the balance of both influences on PPR vectors. In particular, we exploit the fact that correlation between PPR and PageRank values monotonically changes depending on PPR parameter that controls the average random walk length. Here, PageRank is a metric that quantifies the global importance by the probability of random walks from all nodes visiting each node. A case study using the movie rating dataset showed that nodes that are considered to be directly related to the source node get high PPR value by shortening the average random walk length. Moreover, statistical evaluation on nine real-world datasets revealed that changing the average random walk length from 1.01 to 100 resulted in a monotonic increase of the cosine similarity between PPR and PageRank vectors from 0.002 to 0.76 at the maximum.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Balancing Global Importance and Source Proximity for Personalized Recommendations Using Random Walk Length

  • Tsuyoshi Yamashita,
  • Kunitake Kaneko

摘要

For personalized recommendation in graphs, random walks starting from the user’s interest node are known as a general-purpose and fast analysis method. Specifically, Personalized PageRank (PPR), which quantifies the importance of each node by the distribution of visited nodes in random walks, determines nodes with high global importance and source proximity. However, it is difficult to balance both influences monotonically. This paper clarifies that the random walks length is effective to monotonically control the balance of both influences on PPR vectors. In particular, we exploit the fact that correlation between PPR and PageRank values monotonically changes depending on PPR parameter that controls the average random walk length. Here, PageRank is a metric that quantifies the global importance by the probability of random walks from all nodes visiting each node. A case study using the movie rating dataset showed that nodes that are considered to be directly related to the source node get high PPR value by shortening the average random walk length. Moreover, statistical evaluation on nine real-world datasets revealed that changing the average random walk length from 1.01 to 100 resulted in a monotonic increase of the cosine similarity between PPR and PageRank vectors from 0.002 to 0.76 at the maximum.