Skip to content

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.

RelationDescription
num_nodesGet the number of nodes.
num_edgesGet the number of edges.
neighborFind neighbors of nodes.
inneighborFind inneighbors of nodes in directed graphs.
outneighborFind outneighbors of nodes in directed graphs.

Degree

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

RelationDescription
degreeCompute the degree of nodes.
indegreeCompute the indegree of nodes in directed graphs.
outdegreeCompute the outdegree of nodes in directed graphs.
degree_sequenceCompute the degree sequence.
indegree_sequenceCompute the indegree sequence in directed graphs.
outdegree_sequenceCompute the outdegree sequence in directed graphs.
degree_histogramCount the number of nodes with a given degree.
indegree_histogramCount the number of nodes in a directed graph with a given indegree.
outdegree_histogramCount the number of nodes in a directed graph with a given outdegree.
degree_distributionCompute the proportion of nodes with each degree.
indegree_distributionCompute the proportion of nodes in a directed graph with each indegree.
outdegree_distributionCompute the proportion of nodes in a directed graph with each outdegree.
min_degreeFind the minimum degree.
max_degreeFind the maximum degree.
average_degreeFind the average degree.
min_indegreeFind the minimum indegree in directed graphs.
max_indegreeFind the maximum indegree in directed graphs.
average_indegreeFind the average indegree in directed graphs.
min_outdegreeFind the minimum outdegree in directed graphs.
max_outdegreeFind the maximum outdegree in directed graphs.
average_outdegreeFind the average outdegree in directed graphs.
degree_statisticsCompute 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:

RelationDescription
weighted_degreeCompute the weighted degree of nodes.
weighted_indegreeCompute the weighted indegree of nodes in directed graphs.
weighted_outdegreeCompute the weighted outdegree of nodes in directed graphs.
weighted_degree_sequenceCompute the weighted degree sequence.
weighted_indegree_sequenceCompute the weighted indegree sequence in directed graphs.
weighted_outdegree_sequenceCompute the weighted outdegree sequence in directed graphs.
min_weighted_degreeFind the minimum weighted degree.
max_weighted_degreeFind the maximum weighted degree.
average_weighted_degreeFind the average weighted degree.
min_weighted_indegreeFind the minimum weighted indegree in directed graphs.
max_weighted_indegreeFind the maximum weighted indegree in directed graphs.
average_weighted_indegreeFind the average weighted indegree in directed graphs.
min_weighted_outdegreeFind the minimum weighted outdegree in directed graphs.
max_weighted_outdegreeFind the maximum weighted outdegree in directed graphs.
average_weighted_outdegreeFind the average weighted outdegree in directed graphs.
weighted_degree_statisticsCompute 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:

RelationDescription
eigenvector_centralityMeasures 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.
pagerankMeasures a node’s importance in a graph. pagerank is similar to eigenvector_centrality, but with an additional scaling factor.
degree_centralityMeasures 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_centralityMeasures 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:

RelationDescription
jaccard_similarityMeasures the similarity of two nodes based on the number of neighbors common to both nodes. Values range from 0 to 1, inclusive.
cosine_similarityMeasures 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_attachmentComputes 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_adarComputes 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_neighborFinds common neighbors of nodes in a graph.

Community

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

RelationDescription
is_connectedComputes whether or not a graph is connected.
weakly_connected_componentComputes the weakly connected components of a graph.
triangleComputes triples of nodes that form a triangle in a graph. Use triangle to check whether three nodes in a graph form a triangle.
unique_triangleComputes 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_trianglesComputes the number of unique triangles contained in a graph.
triangle_countComputes the number of unique triangles containing each node in a graph.
triangle_distributionComputes the distribution of unique triangles among nodes in a graph.
diameter_rangeEstimates the diameter of a graph by giving a minimum and maximum bound.
local_clustering_coefficientComputes the clustering coefficient for each node in a graph.
average_clustering_coefficientComputes the average clustering coefficient over all nodes in a graph.
triangle_communityAssigns community labels to nodes using the K-clique algorithm with K=3.
label_propagationAssigns community labels to nodes using the Label Propagation Algorithm.

Paths

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

RelationDescription
shortest_path_lengthComputes the length of the shortest path between nodes in a graph.
transitive_closureComputes 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.
Was this doc helpful?