public class PageRank
extends java.lang.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
.
Note that this is not the "normalized" PageRank and as a consequence pages that have no inlinks will have a PageRank of alpha.
Constructor and Description |
---|
PageRank() |
Modifier and Type | Method and Description |
---|---|
protected static void |
initializeLogIfNecessary(boolean isInterpreter) |
protected static boolean |
isTraceEnabled() |
protected static org.slf4j.Logger |
log() |
protected static void |
logDebug(scala.Function0<java.lang.String> msg) |
protected static void |
logDebug(scala.Function0<java.lang.String> msg,
java.lang.Throwable throwable) |
protected static void |
logError(scala.Function0<java.lang.String> msg) |
protected static void |
logError(scala.Function0<java.lang.String> msg,
java.lang.Throwable throwable) |
protected static void |
logInfo(scala.Function0<java.lang.String> msg) |
protected static void |
logInfo(scala.Function0<java.lang.String> msg,
java.lang.Throwable throwable) |
protected static java.lang.String |
logName() |
protected static void |
logTrace(scala.Function0<java.lang.String> msg) |
protected static void |
logTrace(scala.Function0<java.lang.String> msg,
java.lang.Throwable throwable) |
protected static void |
logWarning(scala.Function0<java.lang.String> msg) |
protected static void |
logWarning(scala.Function0<java.lang.String> msg,
java.lang.Throwable throwable) |
static <VD,ED> Graph<java.lang.Object,java.lang.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<java.lang.Object,java.lang.Object> |
runUntilConvergence(Graph<VD,ED> graph,
double tol,
double resetProb,
scala.reflect.ClassTag<VD> evidence$5,
scala.reflect.ClassTag<ED> evidence$6)
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<java.lang.Object,java.lang.Object> |
runUntilConvergenceWithOptions(Graph<VD,ED> graph,
double tol,
double resetProb,
scala.Option<java.lang.Object> srcId,
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<java.lang.Object,java.lang.Object> |
runWithOptions(Graph<VD,ED> graph,
int numIter,
double resetProb,
scala.Option<java.lang.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<java.lang.Object,java.lang.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<java.lang.Object,java.lang.Object> runWithOptions(Graph<VD,ED> graph, int numIter, double resetProb, scala.Option<java.lang.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<java.lang.Object,java.lang.Object> runUntilConvergence(Graph<VD,ED> graph, double tol, double resetProb, scala.reflect.ClassTag<VD> evidence$5, scala.reflect.ClassTag<ED> evidence$6)
graph
- the graph on which to compute PageRanktol
- the tolerance allowed at convergence (smaller => more accurate).resetProb
- the random reset probability (alpha)
evidence$5
- (undocumented)evidence$6
- (undocumented)public static <VD,ED> Graph<java.lang.Object,java.lang.Object> runUntilConvergenceWithOptions(Graph<VD,ED> graph, double tol, double resetProb, scala.Option<java.lang.Object> srcId, 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)srcId
- the source vertex for a Personalized Page Rank (optional)
evidence$7
- (undocumented)evidence$8
- (undocumented)protected static java.lang.String logName()
protected static org.slf4j.Logger log()
protected static void logInfo(scala.Function0<java.lang.String> msg)
protected static void logDebug(scala.Function0<java.lang.String> msg)
protected static void logTrace(scala.Function0<java.lang.String> msg)
protected static void logWarning(scala.Function0<java.lang.String> msg)
protected static void logError(scala.Function0<java.lang.String> msg)
protected static void logInfo(scala.Function0<java.lang.String> msg, java.lang.Throwable throwable)
protected static void logDebug(scala.Function0<java.lang.String> msg, java.lang.Throwable throwable)
protected static void logTrace(scala.Function0<java.lang.String> msg, java.lang.Throwable throwable)
protected static void logWarning(scala.Function0<java.lang.String> msg, java.lang.Throwable throwable)
protected static void logError(scala.Function0<java.lang.String> msg, java.lang.Throwable throwable)
protected static boolean isTraceEnabled()
protected static void initializeLogIfNecessary(boolean isInterpreter)