public class PageRank
extends Object
The first implementation uses the standalone Graph
interface and runs PageRank
for a fixed number of iterations:
var PR = Array.fill(n)( 1.0 )
val oldPR = Array.fill(n)( 1.0 )
for( iter <- 0 until numIter ) {
swap(oldPR, PR)
for( i <- 0 until n ) {
PR[i] = alpha + (1 - alpha) * inNbrs[i].map(j => oldPR[j] / outDeg[j]).sum
}
}
The second implementation uses the Pregel
interface and runs PageRank until
convergence:
var PR = Array.fill(n)( 1.0 )
val oldPR = Array.fill(n)( 0.0 )
while( max(abs(PR - oldPr)) > tol ) {
swap(oldPR, PR)
for( i <- 0 until n if abs(PR[i] - oldPR[i]) > tol ) {
PR[i] = alpha + (1 - \alpha) * inNbrs[i].map(j => oldPR[j] / outDeg[j]).sum
}
}
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
.
Constructor and Description |
---|
PageRank() |
Modifier and Type | Method and Description |
---|---|
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)
Run PageRank for a fixed number of iterations returning a graph
with vertex attributes containing the PageRank and edge
attributes the normalized edge weight.
|
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)
Run Personalized PageRank for a fixed number of iterations, for a
set of starting nodes in parallel.
|
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)
Run a dynamic version of PageRank returning a graph with vertex attributes containing the
PageRank and edge attributes containing the normalized edge weight.
|
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)
Run a dynamic version of PageRank returning a graph with vertex attributes containing the
PageRank and edge attributes containing the normalized edge weight.
|
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)
Run PageRank for a fixed number of iterations returning a graph
with vertex attributes containing the PageRank and edge
attributes the normalized edge weight.
|
public 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)
graph
- the graph on which to compute PageRanknumIter
- the number of iterations of PageRank to runresetProb
- the random reset probability (alpha)
evidence$1
- (undocumented)evidence$2
- (undocumented)public 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)
graph
- the graph on which to compute PageRanknumIter
- the number of iterations of PageRank to runresetProb
- the random reset probability (alpha)srcId
- the source vertex for a Personalized Page Rank (optional)
evidence$3
- (undocumented)evidence$4
- (undocumented)public 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)
graph
- The graph on which to compute personalized pageranknumIter
- The number of iterations to runresetProb
- The random reset probabilitysources
- The list of sources to compute personalized pagerank fromevidence$5
- (undocumented)evidence$6
- (undocumented)public 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)
graph
- the graph on which to compute PageRanktol
- the tolerance allowed at convergence (smaller => more accurate).resetProb
- the random reset probability (alpha)
evidence$7
- (undocumented)evidence$8
- (undocumented)public 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)
graph
- the graph on which to compute PageRanktol
- the tolerance allowed at convergence (smaller => more accurate).resetProb
- the random reset probability (alpha)srcId
- the source vertex for a Personalized Page Rank (optional)
evidence$9
- (undocumented)evidence$10
- (undocumented)