Персонализированная проблема вычисления PageRank - PullRequest
Новая
       9

Персонализированная проблема вычисления PageRank

0 голосов
/ 27 января 2020

Я написал пользовательскую функцию, которая вычисляет PageRank из матрицы смежности (на основе решения в https://en.wikipedia.org/wiki/PageRank#Algebraic, где я изменяю вектор столбцов единиц на вектор персонализации), и сравнил ее с igraph version page_rank ().

  • они дают идентичные результаты, когда нет персонализации
  • , если я использую персонализированный и все вершины имеют хотя бы один исходящий край, они все равно дают идентичные результаты
  • Однако, если я использую персонализированный, но некоторые узлы не имеют исходящих ребер, , тогда результаты будут отличаться .

В чем причина того, что результаты моей реализации отличаются от что за игра? Спасибо! 

library(igraph)

# Create an adjacency matrix for illustration:
  n_nodes <- 5
  adj_mat <- matrix(nrow = n_nodes, ncol = n_nodes)
  adj_mat[2:3,1] <- 1
  adj_mat[3:4,2] <- 1

  adj_mat[is.na(adj_mat)] <- 0

# Create a vector for "personalization" (called pers_vec)
  a <- rbeta(n = n_nodes, 1, 1)
  pers_vec <- a/sum(a) # I want "pers_vec" to sum up to 1.

# Create igraph object, calculate personalized pagerank
  g <- graph_from_adjacency_matrix(adj_mat, "directed", diag = F)
  pr1 <- page_rank(g, "prpack", directed = T, personalized = pers_vec)$vector

# Create custom pagerank function based on this solution: https://en.wikipedia.org/wiki/PageRank#Algebraic
  page_rank1 <- function(adjmat, d = 0.85, personalized = rep(1, n_nodes) , n_nodes){
    if(n_nodes == 1){
      return(1)
    } else {
      # create "i" identity matrix
      i<-  diag(n_nodes)
      # create "M" column-stochastic matrix where columns sum up to 1
      M <- t(adjmat) / matrix( nrow = n_nodes, ncol = n_nodes, rep(rowSums(adjmat, na.rm = T), n_nodes), byrow = T)
      M[is.nan(M) | is.na(M) | is.infinite(M)] <- 0
      # Use the algebraic formula from wikipedia
      pr <- solve(i - (d * M)) %*% ( ((1-d) / n_nodes) * personalized)
      # Normalize so they sum up to 1
      pr <- pr/sum(pr)
      return(as.numeric(pr))
    }
  }

# use the custom function on the adjacency matrix:
  pr2 <- page_rank1(adjmat = adj_mat, personalized = pers_vec, n_nodes = n_nodes)

# They don't give the same results
  print(pr1)
  print(pr2)

# BUT:

# When we make sure that all nodes haveat least one outgoing edge,
  # the functions give identical results

  # add outgoing edges to node 1 and node 5
  adj_mat[1,2] <- 1
  adj_mat[5,3] <- 1

  # recalculate
  g <- graph_from_adjacency_matrix(adj_mat, "directed", diag = F)
  pr1 <- page_rank(g, "prpack", directed = T, personalized = pers_vec)$vector
  pr2 <- page_rank1(adjmat = adj_mat, personalized = pers_vec, n_nodes = n_nodes)

  print(pr1)
  print(pr2)

# Same is true when pageranks are not personalized, for both versions of the graph
  # (even when not all nodes have outgoing edges)

  # e.g. delete the edges of node 1 and node 5
  adj_mat[1,2] <- 0
  adj_mat[5,3] <- 0

  # recalculate
  g <- graph_from_adjacency_matrix(adj_mat, "directed", diag = F)
  pr1 <- page_rank(g, "prpack", directed = T)$vector
  pr2 <- page_rank1(adjmat = adj_mat, n_nodes = n_nodes)

  print(pr1)
  print(pr2)
...