Library: graphlib (centrality)

EXPERIMENTAL: These features are experimental and should not be used in production systems.

# Graph Library (`graphlib`) — Centrality Algorithms Extension

A library extension to `graphlib` containing various centrality algorithms.

## Module: rel:graphlib

View source
``rel:graphlib[G]``

This section of the graph library supports the following centrality algorithms:

MeasureDescription
`pagerank`A measure of centrality of a node based on the PageRank value.
`eigenvector_centrality`A measure of centrality of a node based on the top eigenvalue.
`degree_centrality`A measure of centrality of a node based on the degree.

### pagerank

View source
``````pagerank
pagerank[v]
pagerank(v, p)``````

`pagerank` computes the PageRank values of nodes. `pagerank[v]` computes the PageRank value of node `v`. `pagerank(v, p)` is true if `p` is the PageRank value of node `v`.

Parameters

ParameterTypeDescription
`v``G:node`A node in `G`.
`p``Float`The PageRank of `v`.

Explanation

`pagerank` produces the PageRank values of every node in the graph, after the algorithm has reached a steady state. `pagerank[v]` produces the PageRank value of the node `v`.

Examples

Compute the PageRank for nodes in an undirected graph:

``````def my_edge = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edge]
@inline def my_graphlib = rel:graphlib[my_graph]
// Compute the PageRank for every node in the graph
def output = my_graphlib:pagerank
//output> (11, 0.15578817733990152)
//        (12, 0.41748768472906406)
//        (13, 0.27093596059113306)
//        (14, 0.15578817733990152)

// Compute the PageRank of a single node
def output = my_graphlib:pagerank[11]
//output> 0.15578817733990152``````

### eigenvector_centrality

View source
``````eigenvector_centrality
eigenvector_centrality[v]
eigenvector_centrality(v, p)``````

`eigenvector_centrality` produces the eigenvector centrality values of every node in the graph. `eigenvector_centrality[v]` produces the eigenvector centrality value of the node `v`.

Parameters

ParameterTypeDescription
`v``G:node`A node in `G`.
`p``Float`The EigenVector Centrality of `v`.

Explanation

Eigenvector centrality is a measure of the centrality or importance of a node in a graph based on finding the eigenvector associated with the top eigenvalue of the adjacency matrix. We use the power method to compute the eigenvector in our implementation. Note that the power method requires the adjacency matrix to be diagonalizable (opens in a new tab), and will only converge if the absolute value of the top 2 eigenvalues is distinct. Thus, if the graph you are using has an adjacency matrix that is not diagonalizable or the top two eigenvalues are not distinct, this method will not converge.

Examples

Compute the eigenvector Centrality for nodes in an undirected graph:

``````def my_edge = {(11, 12); (12, 13); (13, 14)}
def my_graph = undirected_graph[my_edge]
@inline def my_graphlib = rel:graphlib[my_graph]
// Compute the eigenvector centrality for every node in the graph
def output = my_graphlib:eigenvector_centrality
//output> (11, 0.3717480344601844)
//        (12, 0.6015009550075456)
//        (13, 0.6015009550075456)
//        (14, 0.3717480344601844)``````

### degree_centrality

View source
``````degree_centrality
degree_centrality[v]
degree_centrality(v, p)``````

`degree_centrality` produces the degree centrality values of every node in the graph. And `degree_centrality[v]` produces the degree centrality of a node `v` in the graph.

Parameters

ParameterTypeDescription
`v``G:node`A node in `G`.
`p``Float`The Degree Centrality of `v`.

Explanation

Degree centrality is a measure of the centrality or importance of a node in a graph based on its degree. Degree centrality is usually defined as the degree of a node divided by the number of nodes - 1. For simple graphs without self loops, this value will be at most 1. Graphs with self loops might have nodes with degree centrality higher than 1.

Examples

Compute the Degree Centrality for nodes in an undirected graph:

``````def my_edge = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edge]
@inline def my_graphlib = rel:graphlib[my_graph]
// Compute the Degree Centrality for every node in the graph
def output = my_graphlib:degree_centrality
//output> (11, 0.333333)
//        (12, 1.0)
//        (13, 0.666667)
//        (14, 0.333333)``````