Class PageRank
Object org.apache.spark.graphx.lib.PageRank
PageRank algorithm implementation. There are two implementations of PageRank implemented.
The first implementation uses the standalone Graph interface and runs PageRank for a fixed number of iterations:
1
var PR = Array.fill(n)( 1.0 )
2
val oldPR = Array.fill(n)( 1.0 )
3
for( iter <- 0 until numIter ) {
4
swap(oldPR, PR)
5
for( i <- 0 until n ) {
6
PR[i] = alpha + (1 - alpha) * inNbrs[i].map(j => oldPR[j] / outDeg[j]).sum
7
}
8
}
Copied!
The second implementation uses the Pregel interface and runs PageRank until convergence:
1
var PR = Array.fill(n)( 1.0 )
2
val oldPR = Array.fill(n)( 0.0 )
3
while( max(abs(PR - oldPr)) > tol ) {
4
swap(oldPR, PR)
5
for( i <- 0 until n if abs(PR[i] - oldPR[i]) > tol ) {
6
PR[i] = alpha + (1 - \alpha) * inNbrs[i].map(j => oldPR[j] / outDeg[j]).sum
7
}
8
}
9
​
Copied!
alpha is the random reset probability (typically 0.15), inNbrs[i] is the set of neighbors which link to i and outDeg[j] is the out degree of vertex j.
Note: This is not the "normalized" PageRank and as a consequence pages that have no inlinks will have a PageRank of alpha.
Methods:
1
static <VD,ED> Graph<Object,Object> run(Graph<VD,ED> graph, int numIter, double resetProb, scala.reflect.ClassTag<VD> evidence$1, scala.reflect.ClassTag<ED> evidence$2)
2
​
3
Run PageRank for a fixed number of iterations returning a graph with vertex
4
attributes containing the PageRank and edge attributes the normalized edge weight.
5
static <VD,ED> Graph<Vector,Object> runParallelPersonalizedPageRank(Graph<VD,ED> graph, int numIter, double resetProb, long[] sources, scala.reflect.ClassTag<VD> evidence$5, scala.reflect.ClassTag<ED> evidence$6)
6
​
7
Run Personalized PageRank for a fixed number of iterations, for a set of starting nodes in parallel.
8
​
9
static <VD,ED> Graph<Object,Object> runUntilConvergence(Graph<VD,ED> graph, double tol, double resetProb, scala.reflect.ClassTag<VD> evidence$7, scala.reflect.ClassTag<ED> evidence$8)
10
​
11
Run a dynamic version of PageRank returning a graph with vertex attributes containing the PageRank and edge attributes containing the normalized edge weight.
12
​
13
static <VD,ED> Graph<Object,Object> runUntilConvergenceWithOptions(Graph<VD,ED> graph, double tol, double resetProb, scala.Option<Object> srcId, scala.reflect.ClassTag<VD> evidence$9, scala.reflect.ClassTag<ED> evidence$10)
14
​
15
Run a dynamic version of PageRank returning a graph with vertex attributes containing the PageRank and edge attributes containing the normalized edge weight.
16
​
17
static <VD,ED> Graph<Object,Object> runWithOptions(Graph<VD,ED> graph, int numIter, double resetProb, scala.Option<Object> srcId, scala.reflect.ClassTag<VD> evidence$3, scala.reflect.ClassTag<ED> evidence$4)
18
​
19
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
20
​
Copied!
Last modified 1yr ago
Copy link