# Overview of The Rel Graph Library

Rel’s Graph Library implements a wide range of algorithms for common graph analytics tasks.

## Getting Started

You can create a graph in three steps:

```
// model
// STEP 1: Create a graph data module with node and edge data.
// Note that the `node` relation is optional and only necessary
// for including isolated nodes.
module my_graph_data
def edge = {(1, 2); (1, 3); (2, 3)}
def node = {4}
end
// STEP 2: Create an attributes set.
// Valid attributes include `:is_directed` to create a directed graph,
// and `:is_weighted` to create a weighted graph. An empty attribute
// set creates an undirected graph.
def my_attributes = {:is_directed}
// STEP 3: Create the graph.
// Apply the `create_graph` constructor to the `my_graph_data`
// and `my_attributes` relations.
def my_graph = create_graph[my_graph_data, my_attributes]
```

Directed, undirected, and weighted graphs are supported. See Graphs for more information.

To run algorithms on a graph,
Instantiate the
`rel:graphlib`

library on the graph
and utilize one of the library’s relations,
such as `pagerank`

:

```
// read query
// Instantiate the `rel:graphlib` library module on `my_graph`.
def my_graphlib = rel:graphlib[my_graph]
// Compute the PageRank of each node in the graph.
def output = my_graphlib:pagerank
```

For detailed information about working with graphs and performing basic operations, see the Basic Operations section. The following sections provide an overview of all relations in the graph library.

## Basics

The following relations support basic operations on graphs, such as counting nodes and edges and finding neighbors of nodes.

Relation | Description |
---|---|

`num_nodes` | Get the number of nodes. |

`num_edges` | Get the number of edges. |

`neighbor` | Find neighbors of nodes. |

`inneighbor` | Find inneighbors of nodes in directed graphs. |

`outneighbor` | Find outneighbors of nodes in directed graphs. |

## Degree

The graph library contains several relations for computing different kinds of degrees of nodes in a graph.

Relation | Description |
---|---|

`degree` | Compute the degree of nodes. |

`indegree` | Compute the indegree of nodes in directed graphs. |

`outdegree` | Compute the outdegree of nodes in directed graphs. |

`degree_sequence` | Compute the degree sequence. |

`indegree_sequence` | Compute the indegree sequence in directed graphs. |

`outdegree_sequence` | Compute the outdegree sequence in directed graphs. |

`degree_histogram` | Count the number of nodes with a given degree. |

`indegree_histogram` | Count the number of nodes in a directed graph with a given indegree. |

`outdegree_histogram` | Count the number of nodes in a directed graph with a given outdegree. |

`degree_distribution` | Compute the proportion of nodes with each degree. |

`indegree_distribution` | Compute the proportion of nodes in a directed graph with each indegree. |

`outdegree_distribution` | Compute the proportion of nodes in a directed graph with each outdegree. |

`min_degree` | Find the minimum degree. |

`max_degree` | Find the maximum degree. |

`average_degree` | Find the average degree. |

`min_indegree` | Find the minimum indegree in directed graphs. |

`max_indegree` | Find the maximum indegree in directed graphs. |

`average_indegree` | Find the average indegree in directed graphs. |

`min_outdegree` | Find the minimum outdegree in directed graphs. |

`max_outdegree` | Find the maximum outdegree in directed graphs. |

`average_outdegree` | Find the average outdegree in directed graphs. |

`degree_statistics` | Compute various degree statistics. |

Although all of the above relations work with weighted graphs, they do not take edge weights into consideration. For weighted degrees, use the following relations:

Relation | Description |
---|---|

`weighted_degree` | Compute the weighted degree of nodes. |

`weighted_indegree` | Compute the weighted indegree of nodes in directed graphs. |

`weighted_outdegree` | Compute the weighted outdegree of nodes in directed graphs. |

`weighted_degree_sequence` | Compute the weighted degree sequence. |

`weighted_indegree_sequence` | Compute the weighted indegree sequence in directed graphs. |

`weighted_outdegree_sequence` | Compute the weighted outdegree sequence in directed graphs. |

`min_weighted_degree` | Find the minimum weighted degree. |

`max_weighted_degree` | Find the maximum weighted degree. |

`average_weighted_degree` | Find the average weighted degree. |

`min_weighted_indegree` | Find the minimum weighted indegree in directed graphs. |

`max_weighted_indegree` | Find the maximum weighted indegree in directed graphs. |

`average_weighted_indegree` | Find the average weighted indegree in directed graphs. |

`min_weighted_outdegree` | Find the minimum weighted outdegree in directed graphs. |

`max_weighted_outdegree` | Find the maximum weighted outdegree in directed graphs. |

`average_weighted_outdegree` | Find the average weighted outdegree in directed graphs. |

`weighted_degree_statistics` | Compute various degree statistics. |

## Centrality

Centrality algorithms assign ranks to nodes in a graph, often for the purpose of measuring a node’s influence or importance in the graph. The Graph Library implements three centrality algorithms:

Relation | Description |
---|---|

`eigenvector_centrality` | Measures a node’s importance in such a way that connections to more important nodes contribute more to a node’s score than connections to less important nodes. |

`pagerank` | Measures a node’s importance in a graph. `pagerank` is similar to `eigenvector_centrality` , but with an additional scaling factor. |

`degree_centrality` | Measures a node’s importance based on its degree. Unlike `pagerank` and `eigenvector_centrality` , `degree_centrality` does not consider the importance of a node’s neighbors when ranking a node. |

`betweenness_centrality` | Measures a node’s importance based on the number of shortest paths that pass through the node. |

## Similarity

Similarity algorithms are used to cluster nodes and predict links between nodes. The Graph Library implements a number of algorithms related to similarity:

Relation | Description |
---|---|

`jaccard_similarity` | Measures the similarity of two nodes based on the number of neighbors common to both nodes. Values range from 0 to 1, inclusive. |

`cosine_similarity` | Measures the similarity of two nodes as a function of the angle between vector representations of their neighborhoods. Values range from -1 to 1, inclusive. |

`preferential_attachment` | Computes the “closeness” of two nodes `u` and `v` as the number of neighbors of `u` times the number of neighbors of `v` . Preferential attachment is used to predict the likelihood of two nodes receiving a new link when modeling network growth. Higher scores indicate that two nodes are “closer” than lower scores. |

`adamic_adar` | Computes the “closeness” of two nodes by computing the inverse logarithmic sum of the degrees of neighbors common to both nodes. Like `preferential_attachment` , `adamic_adar` is used to predict the likelihood that two nodes receive a link as a network grows. |

`common_neighbor` | Finds common neighbors of nodes in a graph. |

## Community

These algorithms are used to determine how nodes are clustered in a graph:

Relation | Description |
---|---|

`is_connected` | Computes whether or not a graph is connected. |

`weakly_connected_component` | Computes the weakly connected components of a graph. |

`triangle` | Computes triples of nodes that form a triangle in a graph. Use `triangle` to check whether three nodes in a graph form a triangle. |

`unique_triangle` | Computes triples of nodes, unique up to order, that form a triangle in the graph. Use `unique_triangle` to find unique triangles containing a given node or pair of nodes. |

`num_triangles` | Computes the number of unique triangles contained in a graph. |

`triangle_count` | Computes the number of unique triangles containing each node in a graph. |

`triangle_distribution` | Computes the distribution of unique triangles among nodes in a graph. |

`diameter_range` | Estimates the diameter of a graph by giving a minimum and maximum bound. |

`local_clustering_coefficient` | Computes the clustering coefficient for each node in a graph. |

`average_clustering_coefficient` | Computes the average clustering coefficient over all nodes in a graph. |

`triangle_community` | Assigns community labels to nodes using the `K` -clique algorithm with `K=3` . |

`label_propagation` | Assigns community labels to nodes using the Label Propagation Algorithm. |

## Paths

The Graph Library implements the following algorithms related to paths in graphs:

Relation | Description |
---|---|

`shortest_path_length` | Computes the length of the shortest path between nodes in a graph. |

`transitive_closure` | Computes the transitive closure of the edges in a graph and may be used to determine which nodes are reachable from each node in the graph. |