Skip to content
PREVIEW
GRAPH ANALYTICS
Basic Operations
Degrees
⚠

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

Graph Library: Degrees

Goal

This guide demonstrates how to use the Graph Library’s degree relations and perform common operations such as computing the degree of a node, computing the degree sequence of a graph, and finding the minimum, maximum, and average degrees of a graph.

Introduction

Numerous graph algorithms depend on the degrees of nodes in a graph. The Graph Library implements several relations for finding the degrees of nodes in undirected graphs and the indegrees and outdegrees of nodes in directed graphs. These relations are described in detail in the Degree Relations section.

Additionally, the Graph Library provides several relations for computing degree statistics and finding the degree sequence of a graph. Examples of using these relations, as well as other common operations involving degrees, are described in the Common Scenarios section.

Degree Relations

The Graph Library provides three relations for finding the neighbors of nodes in a graph.:

  1. degree
  2. indegree
  3. outdegree

The degree relation is primarily used with undirected graphs, while the indegree and outdegree relations are typically used with directed graphs. In undirected graphs, indegree and outdegree are both aliases for degree.

degree

The degree of a node is the number of neighbors it has in the graph. degree is a binary relation that maps nodes in a graph to their degree:

// read query
 
// Construct an undirected graph with three nodes and three edges.
def my_graph = undirected_graph[{(1, 1); (1, 2); (2, 3)}]
 
// Add an isolated node to the graph.
def my_graph:node = 4
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the contents of my_graphlib:degree.
def output = my_graphlib:degree

Node 1 is a neighbor of itself, since my_graph:edge contains the loop (1, 1). Node 1 is also a neighbor of 2, and therefore has degree two. Note that the degree of an isolated node is zero, since it has no neighbors.

In directed graphs, degree computes the total degree of the node, that is, the sum of the indegree and outdegree of the node:

// read query
 
// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 1); (1, 2); (2, 3)}]
 
// Add an isolated node to the graph.
def my_graph:node = 4
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the contents of my_graphlib:degree.
def output = my_graphlib:degree

Node 1 is an inneighbor and outneighbor of itself, and node 2 is also an outneighbor of 1. So, 1 has indegree one and outdegree two. The total degree of node 1, then, is three, which is why (1, 3) appears in the output.

indegree

The indegree of a node in a directed graph is the number of inneighbors of the node. indegree is a binary relation that maps nodes to their indegree:

// read query
 
// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 1); (1, 2); (3, 2)}]
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the contents of my_graphlib:degree.
def output = my_graphlib:indegree

Node 1 has one inneighbor — itself — so its indegree is one. Both nodes 1 and 3 are inneighbors of 2, so node 2 has indegree two. Node 3 has no inneighbors, so its indegree is zero.

outdegree

The outdegree of a node in a directed graph is the number of outneighbors of the node. outdegree is a binary relation that maps nodes to their outdegree:

// read query
 
// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 1); (1, 2); (3, 2)}]
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the contents of my_graphlib:degree.
def output = my_graphlib:outdegree

Node 1 has two outneighbors — itself and node 2 — so its outdegree is two. Node 2 is an outneighbor of node 3, so the outdegree of 3 is one. But, node 2 has no outneighbors so its outdegree is zero.

Common Scenarios

In this section, you’ll learn how to perform common operations with degree relations, including how to:

Compute the Degree of a Node

To compute the degree of a node, partially apply the degree relation to the node:

// read query
 
// Construct an undirected graph with two nodes and two edges.
def my_graph = undirected_graph[{(1, 1); (1, 2)}]
 
// Instantiate rel:graphlib on my_undirected_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the degree of node 1.
def output = my_graphlib:degree[1]

Node 1 is a neighbor of itself because my_graph:edge contains the loop (1, 1). Node 1 also a neighbor of 2 and therefore has degree two.

In directed graphs, degree computes the total degree, that is, the sum of the indegree and outdegree of a node:

// read query
 
// Construct a directed graph with two nodes and two edges.
def my_graph = directed_graph[{(1, 1); (1, 2)}]
 
// Instantiate rel:graphlib on my_undirected_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the degree of node 1.
def output = my_graphlib:degree[1]

Node 1 has degree three since it has indegree one and outdegree two. See degree for more information.

🔎

To compute the indegree or outdegree of a node in a directed graph, use indegree or outdegree.

Find All Nodes With a Degree

To find all nodes in a graph with a given degree, you can write some Rel that selects nodes from the first column of degree that have the degree you are seeking in the second column:

// read query
 
// Construct an undirected graph with three nodes and two edges.
def my_graph = undirected_graph[{(1, 2); (2, 3)}]
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display all nodes with degree 1.
def output(node) { my_graphlib:degree(node, 1) }

Both nodes 1 and 3 have degree one, so they are shown in the output. Node 2 has degree two, so it is not included.

🔎

To find all nodes with a given indegree or outdegree in a directed graph, use indegree or outdegree.

You can wrap this into a reusable relation that can be loaded into a model and used to find nodes of any degree in a graph.

// read query
 
// Find all nodes of degree k in a Degree relation.
// Degree may be one of degree, indegree, or outdegree, for example.
@outline
def degree_k_node(Degree, k in Int, node) { Degree(node, k) }
 
 
// Sample usage:
 
// Construct an undirected graph.
def my_graph = undirected_graph[{(1, 2); (2, 3)}]
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display all nodes in my_graph with degree 2.
def output:degree_two = degree_k_node[my_graphlib:degree, 2]
 
// Display all nodes with degree 0.
// Note that there are no nodes with degree 0,
// so the degree_zero relation is not displayed in the output.
def output:degree_zero = degree_k_node[my_graphlib:degree, 0]

The relation degree_k_node uses the @outline annotation to support the higher-order Degree parameter.

Compute the Degree Sequence

The degree sequence of a graph lists the degrees of each node in the graph ordered from largest to smallest. In Rel, sequences are modeled as relations containing tuples of the form (index, value), where index represents the position of value in the sequence.

To compute the degree sequence of a graph, use the degree_sequence relation:

// read query
 
// Construct an undirected graph with three nodes and three edges.
def my_graph = undirected_graph[{(1, 2); (2, 2); (2, 3)}]
 
// Add one isolated node to my_graph.
def my_graph:node = 4
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the degree sequence of my_graph.
def output = my_graphlib:degree_sequence

The result of degree_sequence contains four tuples: one for each node in my_graph. The tuple (1, 3) indicates that 3 is the largest degree in the graph, since it has index 1. There are two nodes with degree 1 represented by the tuples (2, 1) and (3, 1). The single isolated node in the graph is represented by the tuple (4, 0). Since 4 is the largest index in the sequence, 0 is the smallest degree in the graph.

🔎

To find the sequence of indegrees and outdegrees in directed graphs, use indegree_sequence or outdegree_sequence.

In directed graphs, degree_sequence results in the sequence of total degrees of the graph — that is, the sum of the indegree and outdegree of each node:

// read query
 
// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 2); (2, 2); (2, 3)}]
 
// Add one isolated node to my_graph.
def my_graph:node = 4
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the degree sequence of my_graph.
def output = my_graphlib:degree_sequence

See degree for more information on how degrees are computed in directed graphs.

Find the Min, Max, and Average Degrees

To find the minimum, maximum, and average degrees of a graph, use the min_degree, max_degree, and average_degree relations:

// read query
 
// Construct an undirected graph with three nodes and three edges.
def my_graph = undirected_graph[{(1, 2); (2, 2); (2, 3)}]
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the minimum, maximum, and average degree of my_graph.
def output:min = my_graphlib:min_degree
def output:max = my_graphlib:max_degree
def output:avg = my_graphlib:average_degree

To find the minimum, maximum, and average indegree or outdegree of the graph, append _indegree or _outdegree to one of min, max, or average. For instance, min_indegree for the minmum indegree.

View Degree Statistics

You can view a summary of all degree statistics of a graph using the degree_statistics relation:

// read query
 
// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 2); (2, 2); (2, 3)}]
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display a summary of degree statistics.
def output = my_graphlib:degree_statistics

The degree_statistics relation is compatible with both directed and undirected graphs.

Plot a Degree Histogram

The degree_histogram relation counts the number of nodes with each degree in the graph and contains tuples of the form (degree, node_count):

// read query
 
// Construct an undirected graph with three nodes and three edges.
def my_graph = undirected_graph[{(1, 2); (2, 2); (2, 3)}]
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the contents of degree_histogram.
def output = my_graphlib:degree_histogram

The tuple (1, 2) in the output indicates that there are two nodes with degree 1. You can see that nodes 1 and 3 both have degree 1. Node 2 is the only node with degree 3, which is why (3, 1) also appears in the output.

🔎

To count the number of nodes with a given indegree or outdegree in directed graphs, use the indegree_histogram and outdegree_histogram relations.

In the next example, the degree histogram is plotted using the vegalite:bar relation. The graph is loaded from a CSV file hosted on Azure. See Create a Graph From a CSV File for details on loading graphs from a CSV file. The CSV data, edge set, and instantiated graph and library modules are loaded into a model:

// model
 
// Declare a configuration module for the load_csv relation
// containing the path to the CSV file on Azure
// and the schema for the columns.
module config
    def path = "https://raidocs.blob.core.windows.net/datasets/power-grid/opsahl-powergrid.csv"
    def schema = (:node_from, "int"); (:node_to, "int")
end
 
// Load the CSV data into a relation called my_graph_csv.
def my_graph_csv = load_csv[config]
 
 
// Build an edge set from the CSV data.
def my_edge(node1 in Int, node2 in Int) {
    exists(row_num:
        my_graph_csv(:node_from, row_num, node1)
        and my_graph_csv(:node_to, row_num, node2)
    )
}
 
// Create an unidirected graph with edges from my_edge.
def my_graph = undirected_graph[my_edge]
 
// Instantiate the graph library on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

The histogram is built by organizing the data in degree_histogram into a module that can be provided to the :data parameter of the vegalite:bar relation:

// read query
 
// Count the number of nodes for each degree in my_graph.
def degree_hist = my_graphlib:degree_histogram
 
// Preare the data for visualization.
module data
    def degree = d for d in first[degree_hist]
    def node_count = degree_hist
end
 
// Create a histogram using vegalite:bar.
// The data module is provided as data to the chart constructor.
// :degree is selected as the source for the bars (x-values),
// and :node_count is selected as the source for the height of each bar.
def histogram = vegalite:bar[:degree, :node_count, {(:data, data)}]
 
// Display the histogram.
def output = vegalite:plot[histogram]

Note that you may plot the indegree or outdegree histograms of directed graphs by using indegree or outdegree for the data instead of degree.

Alternatively, you may use my_graphlib:degree as the data for the chart and use Vega-Lite to do the aggregation:

// read query
 
// Prepare the data for visualization.
def data:degree = my_graphlib:degree
 
// Build a histogram using vegalite:bar.
// The data module is provided as data to the chart constructor.
// :degree is selected as the source for the bars (x-values).
// The height of each bar is determined by aggregating all of the
// degree values by count.
def histogram = vegalite:bar[
    :degree,
    {(:aggregate, "count")},
    {(:data, data)}
]
 
// Display the histogram.
def output = vegalite:plot[histogram]

In the preceding version of the plot, the Vega-Lite Library performs the aggregation, not the Graph Library. This has some advantages. For example, you may specify custom bin sizes. The following query displays the same data as the preceding histogram but grouped into bins with step size five. The bars are also displayed on a log scale:

// read query
 
// Prepare the data for visualization.
def data:degree = my_graphlib:degree
 
// Build a binned histogram using vegalite:bar.
// The data module is provided as data to the chart constructor.
// :degree is selected as the source for the bars (x-values)
// with bins of step size 5. The height of each bar is determined
// by aggregating all of the degree values by count
// and is computed on a log scale.
def binned_histogram = vegalite:bar[
    {:degree; (:bin, {(:step, 5)})},
    {(:aggregate, "count"); (:scale, {(:type, "log")})},
    {(:data, data)}
]
 
// Display the binned histogram.
def output = vegalite:plot[binned_histogram]

For large graphs, it may be more performant to use degree_histogram rather than Vega-Lite to perform the aggregation. See Data Visualization: Vega-Lite for more information on plotting in Rel.

Plot the Degree Distribution

The degree_distribution relation computes the proportion of nodes that have a given degree to the total number of nodes in the graph:

// read query
 
// Construct an undirected graph with three nodes and three edges.
def my_graph = undirected_graph[{(1, 2); (2, 2); (2, 3)}]
 
// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
// Display the contents of degree_distribution.
def output = my_graphlib:degree_distribution

The relation my_graph has three nodes: nodes 1 and 3 have degree 1, and node 2 has degree 3. The output contains two tuples: one for each of the degrees in the graph. The tuple (1, 0.6666666666666666) indicates that two-thirds of the nodes have degree 1, and (3, 0.3333333333333333) indicates that one-third of the nodes have degree 3.

🔎

To compute the distribution of indegrees and outdegrees in directed graphs, use the indegree_distribution and outdegree_distribution relations.

To plot the distribution as a bar chart, use the vegalite:bar relation. The following query loads a graph from a CSV file on Azure and displays a bar chart of the degree distribution:

// read query
 
// Declare a configuration module for the load_csv relation
// containing the path to the CSV file on Azure
// and the schema for the columns.
module config
    def path = "https://raidocs.blob.core.windows.net/datasets/power-grid/opsahl-powergrid.csv"
    def schema = (:node_from, "int"); (:node_to, "int")
end
 
// Load the CSV data into a relation called my_graph_csv.
def my_graph_csv = load_csv[config]
 
 
// Build an edge set from the CSV data.
def my_edge(node1 in Int, node2 in Int) {
    exists(row_num:
        my_graph_csv(:node_from, row_num, node1)
        and my_graph_csv(:node_to, row_num, node2)
    )
}
 
// Create an unidirected graph with edges from my_edge.
def my_graph = undirected_graph[my_edge]
 
// Instantiate the graph library on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]
 
 
// Compute the degree distribution.
def degree_distribution = my_graphlib:degree_distribution
 
// Prepare the data for visualization.
module data
    def degree = d for d in first[degree_distribution]
    def proportion = degree_distribution
end
 
// Build a bar chart of the degree distribution.
// The data module is provided as data to the chart constructor.
// :degree is selected as the source for the bars (x-values).
// :proportion is selected as the source for the height of the bars.
def distribution_plot = vegalite:bar[:degree, :proportion, {(:data, data)}]
 
// Display the bar chart.
def output = vegalite:plot[distribution_plot]

Note that you may plot the indegree of outdegree distrubtions by using indegree_distribution or outdegree_distribution for the chart data instead of degree_distribution. See Create a Graph From a CSV File and Data Visualization: Vega-Lite for more information on loading graphs and plotting in Rel.

See Also

See Neighbors to learn about working with neighbor relations. See the Overview of Graph Algorithms to explore all of the algorithms implemented in Rel’s Graph Library.

Was this doc helpful?