 # PageRank

### Related Doc: package lib

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

Definition Classes
AnyRef
7. #### def equals(arg0: Any): Boolean

Definition Classes
AnyRef → Any
8. #### def finalize(): Unit

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

Definition Classes
AnyRef → Any
10. #### def hashCode(): Int

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

Definition Classes
AnyRef
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 = 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.

34. #### final def synchronized[T0](arg0: ⇒ T0): T0

Definition Classes
AnyRef
35. #### def toString(): String

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

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

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

Definition Classes
AnyRef
Annotations
@throws( ... )