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 sourcerel:graphlib[G]This section of the graph library supports the following centrality algorithms:
| Measure | Description |
|---|---|
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 sourcepagerank
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
| Parameter | Type | Description |
|---|---|---|
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.15578817733990152eigenvector_centrality
View sourceeigenvector_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
| Parameter | Type | Description |
|---|---|---|
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 sourcedegree_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
| Parameter | Type | Description |
|---|---|---|
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)