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:

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.

Linear Supertypes

Logging, AnyRef, Any

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[java.lang]
Definition Classes
AnyRef
Annotations
@throws( ... )
final def eq(arg0: AnyRef): Boolean

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

Definition Classes
AnyRef → Any
def finalize(): Unit

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( classOf[java.lang.Throwable] )
final def getClass(): Class[_]

Definition Classes
AnyRef → Any
def hashCode(): Int

Definition Classes
AnyRef → Any
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
final def notifyAll(): Unit

Definition Classes
AnyRef
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 = 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.
final def synchronized[T0](arg0: ⇒ T0): T0

Definition Classes
AnyRef
def toString(): String

Definition Classes
AnyRef → Any
final def wait(): Unit

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

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

Definition Classes
AnyRef
Annotations
@throws( ... )

Related Doc: package lib

object PageRank extends Logging

Value Members

final def !=(arg0: Any): Boolean

final def ##(): Int

final def ==(arg0: Any): Boolean

final def asInstanceOf[T0]: T0

def clone(): AnyRef

final def eq(arg0: AnyRef): Boolean

def equals(arg0: Any): Boolean

def finalize(): Unit

final def getClass(): Class[_]

def hashCode(): Int

def initializeLogIfNecessary(isInterpreter: Boolean): Unit

final def isInstanceOf[T0]: Boolean

def isTraceEnabled(): Boolean

def log: Logger

def logDebug(msg: ⇒ String, throwable: Throwable): Unit

def logDebug(msg: ⇒ String): Unit

def logError(msg: ⇒ String, throwable: Throwable): Unit

def logError(msg: ⇒ String): Unit

def logInfo(msg: ⇒ String, throwable: Throwable): Unit

def logInfo(msg: ⇒ String): Unit

def logName: String

def logTrace(msg: ⇒ String, throwable: Throwable): Unit

def logTrace(msg: ⇒ String): Unit

def logWarning(msg: ⇒ String, throwable: Throwable): Unit

def logWarning(msg: ⇒ String): Unit

final def ne(arg0: AnyRef): Boolean

final def notify(): Unit

final def notifyAll(): Unit

def run[VD, ED](graph: Graph[VD, ED], numIter: Int, resetProb: Double = 0.15)(implicit arg0: ClassTag[VD], arg1: ClassTag[ED]): Graph[Double, Double]

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]

def runUntilConvergence[VD, ED](graph: Graph[VD, ED], tol: Double, resetProb: Double = 0.15)(implicit arg0: ClassTag[VD], arg1: ClassTag[ED]): Graph[Double, Double]

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]

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]

final def synchronized[T0](arg0: ⇒ T0): T0

def toString(): String

final def wait(): Unit

final def wait(arg0: Long, arg1: Int): Unit

final def wait(arg0: Long): Unit

Inherited from Logging

Inherited from AnyRef

Inherited from Any

Ungrouped