package lib

Various analytics functions for graphs.

Linear Supertypes
AnyRef, Any
  1. Alphabetic
  2. By Inheritance
  1. lib
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
  1. Public
  2. All

Value Members

  1. object ConnectedComponents


    Connected components algorithm.

  2. object LabelPropagation


    Label Propagation algorithm.

  3. object PageRank extends Logging


    PageRank algorithm implementation.

    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 that this is not the "normalized" PageRank and as a consequence pages that have no inlinks will have a PageRank of alpha.

  4. object SVDPlusPlus


    Implementation of SVD++ algorithm.

  5. object ShortestPaths


    Computes shortest paths to the given set of landmark vertices, returning a graph where each vertex attribute is a map containing the shortest-path distance to each reachable landmark.

  6. object StronglyConnectedComponents


    Strongly connected components algorithm implementation.

  7. object TriangleCount


    Compute the number of triangles passing through each vertex.

    Compute the number of triangles passing through each vertex.

    The algorithm is relatively straightforward and can be computed in three steps:

    • Compute the set of neighbors for each vertex
    • For each edge compute the intersection of the sets and send the count to both vertices.
    • Compute the sum at each vertex and divide by two since each triangle is counted twice.

    There are two implementations. The default implementation first removes self cycles and canonicalizes the graph to ensure that the following conditions hold:

    • There are no self edges
    • All edges are oriented src > dst
    • There are no duplicate edges

    However, the canonicalization procedure is costly as it requires repartitioning the graph. If the input data is already in "canonical form" with self cycles removed then the TriangleCount.runPreCanonicalized should be used instead.

    val canonicalGraph = graph.mapEdges(e => 1).removeSelfEdges().canonicalizeEdges()
    val counts = TriangleCount.runPreCanonicalized(canonicalGraph).vertices

Inherited from AnyRef

Inherited from Any