Library: graphlib (centrality)

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.
`betweenness_centrality`A measure of centrality of a node based on the number of shortest paths that pass through the node.

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`.

Supported Graph Types

Graph TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedYes

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`.

In the case of weighted graphs, weights are assumed to be non-negative.

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 for only node `11`:

``````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 of a single node
def output = my_graphlib:pagerank[11]
//output> 0.15578817733990152``````

Compute the PageRank for nodes in a weighted, directed graph:

``````def W = {(11, 12, 1); (11, 13, 2); (13, 14, 3)}
def G = create_graph[{(:weight, W)}, {(:is_weighted,); (:is_directed)}]
@inline def my_graphlib = rel:graphlib[G]

def output = my_graphlib:pagerank
//output> (11, 0.161769)
//        (12, 0.207603)
//        (13, 0.253438)
//        (14, 0.377191)``````

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`.

Supported Graph Types

Graph TypeSupportedNotes
UndirectedYesSee Explanation for convergence criteria.
DirectedNoWill not converge.
WeightedYes

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.

In the case of weighted graphs, weights are assumed to be non-negative.

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)``````

Compute the eigenvector centrality for nodes in a weighted, undirected graph:

``````def W = {(11, 12, 0.8); (12, 13, 0.7); (13, 13, 2.0); (12, 14, 1.5)}
def G = create_graph[{(:weight, W)}, {(:is_weighted,)}]
@inline def my_graphlib = rel:graphlib[G]
// Compute the eigenvector centrality for every node in the graph
def output = my_graphlib:eigenvector_centrality
//output> (11, 0.15732673092171892)
//        (12, 0.4732508189314368)
//        (13, 0.8150240891426493)
//        (14, 0.2949876204782229)``````

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.

Supported Graph Types

Graph TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedYes

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)``````

weighted_degree_centrality

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

`weighted_degree_centrality` produces the weighted degree centrality values of every node in the graph. And `weighted_degree_centrality[v]` produces the degree centrality of a node `v` in the graph. The weighted degree centrality of a node is the sum of the weights of all the edges attached to the node divided by the number of nodes in the graph - 1.

Supported Graph Types

Graph TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedYes

Parameters

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

Explanation

Weighted Degree centrality is a measure of the centrality or importance of a node in a graph based on its weighted degree. We use the definition of weighted degree centrality where the weighted degree of a node is the sum of the weights of all the edges attached to it.

Examples

Compute the Weighted Degree Centrality for nodes in an undirected graph:

``````def my_edge = {(11, 12, 2.0); (11, 13, 0.5); (12, 11, 1.5)}
def my_graph = create_graph[{(:weight, W)}, {(:is_weighted,);}]
@inline def my_graphlib = rel:graphlib[my_graph]
// Compute the Degree Centrality for every node in the graph
def output = my_graphlib:weighted_degree_centrality
//output> (11, 1.25)
//        (12, 1.75)
//        (13, 1.0)``````

betweenness_centrality

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

`betweenness_centrality` produces the betweenness centrality values of every node in the graph. `betweenness_centrality[v]` produces the betweenness centrality of a node `v` in the graph. `betweenness_centrality(v, p)` checks that `p` is the betweenness centrality of node `v`.

Supported Graph Types

Graph TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedNo

Parameters

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

Explanation

Betweenness centrality measures how important a node is based on how many times that node appears in a shortest path between any two nodes in the graph. Nodes with high betweenness centrality represent bridges between different parts of the graph. For example, in a network representing airports and flights between them, nodes with high betweenness centrality may identify “hub” airports that connect flights to different regions.

Calculating betweenness centrality involves computing all of the shortest paths between every pair of nodes in a graph and can be expensive to calculate exactly. The `betweenness_centrality` relation gives an approximation using the Brandes algorithm (opens in a new tab) with source nodes drawn from a sample of 100 nodes with the highest degrees. Values are non-negative and are not normalized.

Examples

Compute the betweenness centrality for every node in a 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]

def output = my_graphlib:betweenness_centrality
//output>  (11, 0.0)
//         (12, 1.0)
//         (13, 0.0)
//         (14, 0.0)``````

Compute the betweenness centrality of a node:

``````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]

def output = my_graphlib:betweenness_centrality[12]
//output> 1.0``````

Module: rel:graph:algorithm

View source
``rel:graph:algorithm``

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.

pagerank

View source
``pagerank(Config, v, p)``

`pagerank` computes the PageRank value `p` for each node `v` as specified in the `Config` relation.

Supported Graph Types

Graph TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedYesOnly positive weights supported.
UnweightedYes

Parameters

ParameterTypeRequiredDescription
`Config`ModuleYesProvide the graph and optional parameters to the algorithm.
`v``Config:graph:node`NoA node in `Config:graph`.
`p``Float`NoThe PageRank of `v`.

Configuration Optional Parameters

| Config Parameter | Type | Required | Default | Description | | :— | :— | :— | :— | :— | :— | | `:damping_factor` | `Float` | No | `0.85` | The damping factor of the PageRank calculation. Values must be in [0, 1). | | `:tolerance` | `Float` | No | `0.000001` | Convergence tolerance of the PageRank calculation. | | `:iter_limit` | `Int` | No | `20` | The maximum number of iterations for PageRank to run. Must be positive. | | `:diagnostics` | `RelName` | No | `:false` | Whether or not to return diagnostic information with the results. |

Explanation

`pagerank` produces the PageRank values of every node in the graph, after the algorithm has reached a steady state. `pagerank[Config, v]` produces the PageRank value of the node `v`. In the case of weighted graphs, weights are assumed to be positive.

Examples

Compute the PageRank for nodes in an undirected graph:

``````def my_edge = {(11, 12); (12, 13); (13, 13); (12, 14)}
def G = undirected_graph[my_edges]
with rel:graph:algorithm use pagerank

// Compute the PageRank for every node in the graph
def output = pagerank[{(:graph, G)}]
//output> (11, 0.15578817733990152)
//        (12, 0.41748768472906406)
//        (13, 0.27093596059113306)
//        (14, 0.15578817733990152)``````

Compute the PageRank for only node `11`:

``````def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def G = undirected_graph[my_edges]
with rel:graph:algorithm use pagerank

// Compute the PageRank of a single node
def output = pagerank[{(:graph, G)}, 11]
//output> 0.15578817733990152``````

Compute the PageRank for nodes in a weighted, directed graph with a configuration:

``````def W = {(11, 12, 1); (11, 13, 2); (13, 14, 3)}
def G = create_graph[{(:weight, W)}, {(:is_weighted,); (:is_directed)}]
with rel:graph:algorithm use pagerank

// Set the damping factor and tolerance.
def config = {
(:graph, G);
(:damping_factor, 0.85);
(:tolerance, 0.000001)
}

// Compute the PageRank values for every node in the graph.
def output = pagerank[config]
//output> (11, 0.161769)
//        (12, 0.207603)
//        (13, 0.253438)
//        (14, 0.377191)``````

Compute the PageRank for nodes in a weighted, directed graph and return diagnostics:

``````def W = {(11, 12, 1); (11, 13, 2); (13, 14, 3)}
def G = create_graph[{(:weight, W)}, {(:is_weighted,); (:is_directed)}]
with rel:graph:algorithm use pagerank

// Set damping factor, tolerance and iter_limit.
def config = {
(:graph, G);
(:damping_factor, 0.85);
(:tolerance, 0.000001);
(:iter_limit, 20);
(:diagnostics, :true)
}

// Compute the PageRank values for every node in the graph.
def pagerank_info = pagerank[config]
def output:result = pagerank_info:result
//output> (:result, 11, 0.161769)
//        (:result, 12, 0.207603)
//        (:result, 13, 0.253438)
//        (:result, 14, 0.377191)

def output:damping_factor = pagerank_info:config:damping_factor
//output> (:damping_factor, 0.85)

def output:tolerance = pagerank_info:config:tolerance
//output> (:tolerance, 0.000001)

def output:num_iterations = pagerank_info:diagnostics:num_iterations
//output> (:num_iterations, 13)

def output:termination_status = pagerank_info:diagnostics:termination_status
//output> (:termination_status, :converged)``````