Computes the personalized pagerank for specified seeds using the ApproximatePageRank algorithm of Andersen et al. (2006). Computes degree-adjustments and degree-regularization of personalized pagerank vectors as described in Algorithms 3 and 4 of Chen et al. (2019). These algorithms are randomized; if results are unstable across multiple runs, decrease epsilon.

appr(
  graph,
  seeds,
  ...,
  alpha = 0.15,
  epsilon = 1e-06,
  tau = NULL,
  verbose = TRUE
)

# S3 method for igraph
appr(graph, seeds, ...)

# S3 method for rtweet_graph
appr(graph, seeds, ...)

Arguments

graph

An abstract_graph() object, such as those created by rtweet_graph() and twittercache_graph(), and igraph::igraph() object. This argument is required.

seeds

A character vector of seeds for the personalized pagerank. The personalized pagerank will return to each of these seeds with probability alpha at each node transition. At the moment, all seeds are given equal weighting. This argument is required.

...

Ignored. Passing arguments to ... results in a warning.

alpha

Teleportation constant. The teleportation constant is the probability of returning to a seed node at each node transition. alpha must be a valid probabilty; that is, between zero and one. Defaults to 0.15. This is the inverse of the "dampening factor" in the original PageRank paper, so alpha = 0.15 corresponds to a dampening factor of 0.85. Runtime is proportional to 1 / (epsilon * alpha), so small alpha can result in long runtimes.

epsilon

Desired accuracy of approximation. epsilon must be a valid probabilty; that is, between zero and one. Defaults to 1e-6. Runtime is proportional to 1 / (epsilon * alpha), so small epsilon can result in long runtimes.

tau

Regularization term. Additionally inflates the in-degree of each observation by this term by performing the degree adjustment described in Algorithm 3 and Algorithm 4, which are described in vignette("Mathematical details"). Defaults to NULL, in which case tau is set to the average in-degree of the observed nodes. In general, setting it's reasonable to set tau to the average in-degree of the graph.

verbose

Logical indicating whether to report on the algorithms progress. Defaults to TRUE.

Value

A Tracker() object. Most relevant is the stats field, a tibble::tibble() with the following columns:

  • name: Name of a node (character).

  • p: Estimated personalized pagerank of a node.

  • r: Estimated error of pagerank estimate for a node.

  • in_degree: Number of incoming edges to a node.

  • out_degree: Number of outcoming edges from a node.

  • degree_adjusted: The personalized pagerank divided by the node in-degree.

  • regularized: The personalized pagerank divide by the node in-degree plus tau.

When computing personalized pageranks for Twitter users (either via rtweet_graph() or twittercache_graph()), name is given as a user ID, not a screen name, regardless of how the seed nodes were specified.

References

Chen, F., Zhang, Y. & Rohe, K. Targeted sampling from massive Blockmodel graphs with personalized PageRank. 23. http://arxiv.org/abs/1910.12937

Andersen, R., Chung, F. & Lang, K. Local Graph Partitioning using PageRank Vectors. in 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) 475–486 (IEEE, 2006). doi:10.1109/FOCS.2006.44. http://ieeexplore.ieee.org/document/4031383/

Examples

library(aPPR) library(igraph)
#> #> Attaching package: 'igraph'
#> The following object is masked from 'package:aPPR': #> #> neighborhood
#> The following objects are masked from 'package:stats': #> #> decompose, spectrum
#> The following object is masked from 'package:base': #> #> union
set.seed(27) graph <- rtweet_graph() if (FALSE) { appr(graph, "alexpghayes") } graph2 <- sample_pa(100) # this creates a Tracker object ppr_results <- appr(graph2, seeds = "5") # the portion of the Tracker object you probably care about ppr_results$stats
#> # A tibble: 2 x 7 #> name r p in_degree out_degree degree_adjusted regularized #> <chr> <dbl> <dbl> <dbl> <dbl> <dbl> <dbl> #> 1 5 0.000000833 0.150 2 1 0.0750 0.0300 #> 2 4 0.000000667 0.127 4 1 0.0319 0.0182