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
.
- 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[java.lang]
- Definition Classes
- AnyRef
- Annotations
- @native() @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
- Annotations
- @native()
-
def
hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
def
initializeLogIfNecessary(isInterpreter: Boolean, silent: Boolean = false): 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()
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
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
- @native() @throws( ... )