object PageRank extends Logging
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:
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
.
 Source
 PageRank.scala
 Note
This is not the "normalized" PageRank and as a consequence pages that have no inlinks will have a PageRank of alpha.
 Alphabetic
 By Inheritance
 PageRank
 Logging
 AnyRef
 Any
 Hide All
 Show All
 Public
 All
Value Members

final
def
!=(arg0: Any): Boolean
 Definition Classes
 AnyRef → Any

final
def
##(): Int
 Definition Classes
 AnyRef → Any

final
def
==(arg0: Any): Boolean
 Definition Classes
 AnyRef → Any

final
def
asInstanceOf[T0]: T0
 Definition Classes
 Any

def
clone(): AnyRef
 Attributes
 protected[lang]
 Definition Classes
 AnyRef
 Annotations
 @throws( ... ) @native() @IntrinsicCandidate()

final
def
eq(arg0: AnyRef): Boolean
 Definition Classes
 AnyRef

def
equals(arg0: Any): Boolean
 Definition Classes
 AnyRef → Any

final
def
getClass(): Class[_]
 Definition Classes
 AnyRef → Any
 Annotations
 @native() @IntrinsicCandidate()

def
hashCode(): Int
 Definition Classes
 AnyRef → Any
 Annotations
 @native() @IntrinsicCandidate()

def
initializeLogIfNecessary(isInterpreter: Boolean, silent: Boolean): Boolean
 Attributes
 protected
 Definition Classes
 Logging

def
initializeLogIfNecessary(isInterpreter: Boolean): Unit
 Attributes
 protected
 Definition Classes
 Logging

final
def
isInstanceOf[T0]: Boolean
 Definition Classes
 Any

def
isTraceEnabled(): Boolean
 Attributes
 protected
 Definition Classes
 Logging

def
log: Logger
 Attributes
 protected
 Definition Classes
 Logging

def
logDebug(msg: ⇒ String, throwable: Throwable): Unit
 Attributes
 protected
 Definition Classes
 Logging

def
logDebug(msg: ⇒ String): Unit
 Attributes
 protected
 Definition Classes
 Logging

def
logError(msg: ⇒ String, throwable: Throwable): Unit
 Attributes
 protected
 Definition Classes
 Logging

def
logError(msg: ⇒ String): Unit
 Attributes
 protected
 Definition Classes
 Logging

def
logInfo(msg: ⇒ String, throwable: Throwable): Unit
 Attributes
 protected
 Definition Classes
 Logging

def
logInfo(msg: ⇒ String): Unit
 Attributes
 protected
 Definition Classes
 Logging

def
logName: String
 Attributes
 protected
 Definition Classes
 Logging

def
logTrace(msg: ⇒ String, throwable: Throwable): Unit
 Attributes
 protected
 Definition Classes
 Logging

def
logTrace(msg: ⇒ String): Unit
 Attributes
 protected
 Definition Classes
 Logging

def
logWarning(msg: ⇒ String, throwable: Throwable): Unit
 Attributes
 protected
 Definition Classes
 Logging

def
logWarning(msg: ⇒ String): Unit
 Attributes
 protected
 Definition Classes
 Logging

final
def
ne(arg0: AnyRef): Boolean
 Definition Classes
 AnyRef

final
def
notify(): Unit
 Definition Classes
 AnyRef
 Annotations
 @native() @IntrinsicCandidate()

final
def
notifyAll(): Unit
 Definition Classes
 AnyRef
 Annotations
 @native() @IntrinsicCandidate()

def
run[VD, ED](graph: Graph[VD, ED], numIter: Int, resetProb: Double = 0.15)(implicit arg0: ClassTag[VD], arg1: ClassTag[ED]): Graph[Double, Double]
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
 VD
the original vertex attribute (not used)
 ED
the original edge attribute (not used)
 graph
the graph on which to compute PageRank
 numIter
the number of iterations of PageRank to run
 resetProb
the random reset probability (alpha)
 returns
the graph containing with each vertex containing the PageRank and each edge containing the normalized weight.

def
runParallelPersonalizedPageRank[VD, ED](graph: Graph[VD, ED], numIter: Int, resetProb: Double = 0.15, sources: Array[VertexId])(implicit arg0: ClassTag[VD], arg1: ClassTag[ED]): Graph[Vector, Double]
Run Personalized PageRank for a fixed number of iterations, for a set of starting nodes in parallel.
Run Personalized PageRank for a fixed number of iterations, for a set of starting nodes in parallel. Returns a graph with vertex attributes containing the pagerank relative to all starting nodes (as a sparse vector) and edge attributes the normalized edge weight
 VD
The original vertex attribute (not used)
 ED
The original edge attribute (not used)
 graph
The graph on which to compute personalized pagerank
 numIter
The number of iterations to run
 resetProb
The random reset probability
 sources
The list of sources to compute personalized pagerank from
 returns
the graph with vertex attributes containing the pagerank relative to all starting nodes (as a sparse vector indexed by the position of nodes in the sources list) and edge attributes the normalized edge weight

def
runUntilConvergence[VD, ED](graph: Graph[VD, ED], tol: Double, resetProb: Double = 0.15)(implicit arg0: ClassTag[VD], arg1: ClassTag[ED]): Graph[Double, Double]
Run a dynamic version of PageRank returning a graph with vertex attributes containing the PageRank and edge attributes containing the normalized edge weight.
Run a dynamic version of PageRank returning a graph with vertex attributes containing the PageRank and edge attributes containing the normalized edge weight.
 VD
the original vertex attribute (not used)
 ED
the original edge attribute (not used)
 graph
the graph on which to compute PageRank
 tol
the tolerance allowed at convergence (smaller => more accurate).
 resetProb
the random reset probability (alpha)
 returns
the graph containing with each vertex containing the PageRank and each edge containing the normalized weight.

def
runUntilConvergenceWithOptions[VD, ED](graph: Graph[VD, ED], tol: Double, resetProb: Double = 0.15, srcId: Option[VertexId] = None)(implicit arg0: ClassTag[VD], arg1: ClassTag[ED]): Graph[Double, Double]
Run a dynamic version of PageRank returning a graph with vertex attributes containing the PageRank and edge attributes containing the normalized edge weight.
Run a dynamic version of PageRank returning a graph with vertex attributes containing the PageRank and edge attributes containing the normalized edge weight.
 VD
the original vertex attribute (not used)
 ED
the original edge attribute (not used)
 graph
the graph on which to compute PageRank
 tol
the tolerance allowed at convergence (smaller => more accurate).
 resetProb
the random reset probability (alpha)
 srcId
the source vertex for a Personalized Page Rank (optional)
 returns
the graph containing with each vertex containing the PageRank and each edge containing the normalized weight.

def
runWithOptions[VD, ED](graph: Graph[VD, ED], numIter: Int, resetProb: Double, srcId: Option[VertexId], normalized: Boolean)(implicit arg0: ClassTag[VD], arg1: ClassTag[ED]): Graph[Double, Double]
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
 VD
the original vertex attribute (not used)
 ED
the original edge attribute (not used)
 graph
the graph on which to compute PageRank
 numIter
the number of iterations of PageRank to run
 resetProb
the random reset probability (alpha)
 srcId
the source vertex for a Personalized Page Rank (optional)
 normalized
whether or not to normalize rank sum
 returns
the graph containing with each vertex containing the PageRank and each edge containing the normalized weight.
 Since
3.2.0

def
runWithOptions[VD, ED](graph: Graph[VD, ED], numIter: Int, resetProb: Double = 0.15, srcId: Option[VertexId] = None)(implicit arg0: ClassTag[VD], arg1: ClassTag[ED]): Graph[Double, Double]
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
 VD
the original vertex attribute (not used)
 ED
the original edge attribute (not used)
 graph
the graph on which to compute PageRank
 numIter
the number of iterations of PageRank to run
 resetProb
the random reset probability (alpha)
 srcId
the source vertex for a Personalized Page Rank (optional)
 returns
the graph containing with each vertex containing the PageRank and each edge containing the normalized weight.

def
runWithOptionsWithPreviousPageRank[VD, ED](graph: Graph[VD, ED], numIter: Int, resetProb: Double, srcId: Option[VertexId], normalized: Boolean, preRankGraph: Graph[Double, Double])(implicit arg0: ClassTag[VD], arg1: ClassTag[ED]): Graph[Double, Double]
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
 VD
the original vertex attribute (not used)
 ED
the original edge attribute (not used)
 graph
the graph on which to compute PageRank
 numIter
the number of iterations of PageRank to run
 resetProb
the random reset probability (alpha)
 srcId
the source vertex for a Personalized Page Rank (optional)
 normalized
whether or not to normalize rank sum
 preRankGraph
PageRank graph from which to keep iterating
 returns
the graph containing with each vertex containing the PageRank and each edge containing the normalized weight.
 Since
3.2.0

def
runWithOptionsWithPreviousPageRank[VD, ED](graph: Graph[VD, ED], numIter: Int, resetProb: Double, srcId: Option[VertexId], preRankGraph: Graph[Double, Double])(implicit arg0: ClassTag[VD], arg1: ClassTag[ED]): Graph[Double, Double]
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
Run PageRank for a fixed number of iterations returning a graph with vertex attributes containing the PageRank and edge attributes the normalized edge weight.
 VD
the original vertex attribute (not used)
 ED
the original edge attribute (not used)
 graph
the graph on which to compute PageRank
 numIter
the number of iterations of PageRank to run
 resetProb
the random reset probability (alpha)
 srcId
the source vertex for a Personalized Page Rank (optional)
 preRankGraph
PageRank graph from which to keep iterating
 returns
the graph containing with each vertex containing the PageRank and each edge containing the normalized weight.

final
def
synchronized[T0](arg0: ⇒ T0): T0
 Definition Classes
 AnyRef

def
toString(): String
 Definition Classes
 AnyRef → Any

final
def
wait(arg0: Long, arg1: Int): Unit
 Definition Classes
 AnyRef
 Annotations
 @throws( ... )

final
def
wait(arg0: Long): Unit
 Definition Classes
 AnyRef
 Annotations
 @throws( ... ) @native()

final
def
wait(): Unit
 Definition Classes
 AnyRef
 Annotations
 @throws( ... )
Deprecated Value Members

def
finalize(): Unit
 Attributes
 protected[lang]
 Definition Classes
 AnyRef
 Annotations
 @throws( classOf[java.lang.Throwable] ) @Deprecated
 Deprecated