PageRank centrality algorithm - Neptune Analytics
SyntaxInputsOutputsQuery examplesSample output

PageRank centrality algorithm

PageRank is an algorithm originally developed by Larry Page and Sergey Brin, co-founders of Google. It was originally developed to rank web pages in search engine results. The PageRank score for a given node is calculated based on the number and quality of the edges pointing to that node, as well as the importance of the nodes that are connected to it. The PageRank algorithm assigns a higher score to nodes that are linked to other high-scoring nodes, and a lower score to nodes that are linked to low-scoring nodes.

The output of PageRank can be visualized as a ranking metric for the importance of a node within a given graph, with the most important nodes having the highest score, and the least important node having the lowest score. PageRank is used in search engines to rank web pages based on their importance and influence, in citation networks to identify highly cited scientific papers, and in recommendation systems to suggest popular and relevant content to users.

The space complexity of the .pageRank algorithm is: 

O(|V|) + [storage of data O(|V|+|E|)]

In more detail, this is:

|V| * (3 * sizeof(local id type) +
       2 * sizeof(double) +
       sizeof(global id type)) +
       O(|1DData Parts|)

.pageRank  syntax

CALL neptune.algo.pageRank(
  [node list (required)],
  {
    numOfIterations: a small positive integer like 20 (optional),
    dampingFactor: a positive float less than or equal to 1.0, like 0.85 (optional)
    edgeLabels: [a list of edge labels for filtering (optional)],
    vertexLabel: a node label for filtering (optional),
    concurrency: number of threads to use (optional),
    traversalDirection: the direction of edge to follow (optional),
    tolerance: a floating point number between 0.0 and 1.0 (inclusive)(optional),
    edgeWeightProperty: the weight property to consider for weighted pageRank computation (optional),
    edgeWeightType: The type of values associated with the edgeWeightProperty argument (optional)
  }
)
YIELD node, rank
RETURN node, rank

.pageRank  inputs

  • a node list   (required)   –   type: Node[] or NodeId[];   default: none.

    The node or nodes for which to return the page rank values. If an empty list is provided, the query result will also be empty.

    If the algorithm is called following a MATCH clause (query integration), the result returned by the MATCH clause is taken as the node list.

  • a configuration object that contains:

    • numOfIterations (optional)   –   type: a positive integer greater than zero;   default: 20.

      The number of iterations to perform to reach convergence. A number between 10 and 20 is recommended.

    • dampingFactor (optional)   –   type: a positive floating-point number less than or equal to 1.0;   default: 0.85.

      A positive floating-point damping factor between 0.0 and 1.0 that expresses the probability, at any step, that the node will continue.

    • edgeLabels   (optional)   –   type: a list of edge label strings;   example: ["route", ...];   default: no edge filtering.

      To filter on one more edge labels, provide a list of the ones to filter on. If no edgeLabels field is provided then all edge labels are processed during traversal.

    • vertexLabel (optional)   –   type: string;   default: none.

      A vertex label for vertex filtering. If a vertex label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list.

    • concurrency   (optional)   –   type: 0 or 1;   default: 0.

      Controls the number of concurrent threads used to run the algorithm.

      If set to 0, uses all available threads to complete execution of the individual algorithm invocation. If set to 1, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.

    • traversalDirection (optional)   –   type: string;   default: "outbound".

      The direction of edge to follow. Must be one of: "oubound" or "inbound".

    • tolerance (optional)   –   a floating point number between 0.0 and 1.0 (inclusive). When the average difference in the pageRank values of two iterations drops below tolerance, the algorithm stops, regardless of whether the numOfIterations is reached. Default value is 0.000001 (1e-6).

      • Note that this tolerance computation is equivalent to L1 error or sum of Mean Absolute Difference (MAE)s.

      • The stopping condition is l1_error_sum < tolerance * numNodes, equivalent to l1_error_sum/numNodes < tolerance.

    • edgeWeightProperty (optional)   –   type: string   default: none.

      The weight property to consider for weighted pageRank computation.

    • edgeWeightType (optional) - required if edgeWeightProperty is present   –   type: string;   default: none.

      The type of values associated with the edgeWeightProperty argument, specified as a string. valid values: "int", "long", "float", "double".

      • If the edgeWeightProperty is not given, the algorithm runs unweighted no matter if the edgeWeightType is given or not.

      • Note that if multiple properties exist on the edge with the name specified by edgeWeightProperty, one of those property values will be sampled at random.

Outputs for the .pageRank algorithm

  • node   –   A key column of the input nodes.

  • rank   –   A key column of the corresponding page-rank scores for those nodes.

If the input nodes list is empty, the output is empty.

Query examples for .pageRank

This is a standalone example, where the source vertex list is explicitly specified in the query.

CALL neptune.algo.pageRank(
  ["101"],
  {
    numOfIterations: 1,
    dampingFactor: 0.85,
    edgeLabels: ["route"]
  }
)

This is a query integration examples, where .pageRank follows a MATCH clause and uses frontier injection to take the output of the MATCH clause as its list of source nodes:

MATCH (n)
CALL neptune.algo.pageRank(
  n,
  {
    dampingFactor: 0.85,
    numOfIterations: 1,
    edgeLabels: ["route"]
  }
)
YIELD rank
RETURN n, rank

This query is an example of constraining the results of .pageRank based on the PageRank values, and returning them in ascending order:

MATCH (n)
CALL neptune.algo.pageRank(
  n,
  {
    numOfIterations: 10,
    dampingFactor: 0.85,
    tolerance: 0.0001,
    vertexLabel: "airport",
    edgeLabels: ["route"]
  }
)
YIELD rank WHERE rank > 0.004
RETURN n, rank ORDER BY rank

Sample   .pageRank   output

Here is an example of the output returned by .pageRank when run against the sample air-routes dataset [nodes], and sample air-routes dataset [edges], when using the following query:

aws neptune-graph execute-query \
  --graph-identifier ${graphIdentifier} \
  --query-string "CALL neptune.algo.pageRank(n) YIELD node, rank RETURN node, rank LIMIT" \
  --language open_cypher \
  /tmp/out.txt
  
cat /tmp/out.txt  
{
  "results": [
    {
      "node": {
        "~id": "2709",
        "~entityType": "node",
        "~labels": ["airport"],
        "~properties": {
          "lat": 65.4809036254883,
          "elev": 49,
          "longest": 8711,
          "city": "Nadym",
          "type": "airport",
          "region": "RU-YAN",
          "desc": "Nadym Airport",
          "code": "NYM",
          "lon": 72.6988983154297,
          "country": "RU",
          "icao": "USMM",
          "runways": 1
        }
      },
      "rank": 0.00016044313088059425
    },
    {
      "node": {
        "~id": "3747",
        "~entityType": "node",
        "~labels": ["continent"],
        "~properties": {
          "code": "AN",
          "type": "continent",
          "desc": "Antarctica"
        }
      },
      "rank": 0.0000404242
    }
  ]
}