Packages

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.

Linear Supertypes
Logging, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. PageRank
  2. Logging
  3. AnyRef
  4. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native() @IntrinsicCandidate()
  6. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  7. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  8. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @IntrinsicCandidate()
  9. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @IntrinsicCandidate()
  10. def initializeLogIfNecessary(isInterpreter: Boolean, silent: Boolean): Boolean
    Attributes
    protected
    Definition Classes
    Logging
  11. def initializeLogIfNecessary(isInterpreter: Boolean): Unit
    Attributes
    protected
    Definition Classes
    Logging
  12. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  13. def isTraceEnabled(): Boolean
    Attributes
    protected
    Definition Classes
    Logging
  14. def log: Logger
    Attributes
    protected
    Definition Classes
    Logging
  15. def logDebug(msg: ⇒ String, throwable: Throwable): Unit
    Attributes
    protected
    Definition Classes
    Logging
  16. def logDebug(msg: ⇒ String): Unit
    Attributes
    protected
    Definition Classes
    Logging
  17. def logError(msg: ⇒ String, throwable: Throwable): Unit
    Attributes
    protected
    Definition Classes
    Logging
  18. def logError(msg: ⇒ String): Unit
    Attributes
    protected
    Definition Classes
    Logging
  19. def logInfo(msg: ⇒ String, throwable: Throwable): Unit
    Attributes
    protected
    Definition Classes
    Logging
  20. def logInfo(msg: ⇒ String): Unit
    Attributes
    protected
    Definition Classes
    Logging
  21. def logName: String
    Attributes
    protected
    Definition Classes
    Logging
  22. def logTrace(msg: ⇒ String, throwable: Throwable): Unit
    Attributes
    protected
    Definition Classes
    Logging
  23. def logTrace(msg: ⇒ String): Unit
    Attributes
    protected
    Definition Classes
    Logging
  24. def logWarning(msg: ⇒ String, throwable: Throwable): Unit
    Attributes
    protected
    Definition Classes
    Logging
  25. def logWarning(msg: ⇒ String): Unit
    Attributes
    protected
    Definition Classes
    Logging
  26. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  27. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @IntrinsicCandidate()
  28. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @IntrinsicCandidate()
  29. 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.

  30. 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

  31. 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.

  32. 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.

  33. 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

  34. 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.

  35. 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

  36. 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.

  37. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  38. def toString(): String
    Definition Classes
    AnyRef → Any
  39. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  40. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native()
  41. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Deprecated Value Members

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

Inherited from Logging

Inherited from AnyRef

Inherited from Any

Ungrouped