Apache AGE: Watts-Strogatz Graph

Introduction

We will discuss in this post about the Watts-Strogatz graph, a feature that I've worked for Apache AGE and you can see the Pull Request for it here. First, let's introduce what is Apache AGE and Watts-Strogatz graph.

What is Apache AGE

Apache AGE is a PostgreSQL extension that provides graph database functionality. The goal of the project is to create single storage that can handle both relational and graph model data so that users can use standard ANSI SQL along with openCypher, the Graph query language.

Contribute to Apache AGE
Website: https://age.apache.org
Github: https://github.com/apache/age

What is Watts-Strogatz Graph

The Watts–Strogatz model was proposed by Duncan J. Watts and Steven Strogatz in their article published in 1998 in the Nature scientific journal. It is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering.

How the algorithm works
First create a ring over n nodes. Then each node in the ring is joined to its k nearest neighbors (or k-1 neighbors if k is odd). Then shortcuts are created by replacing some edges as follows: for each edge (u,v) in the underlying “n-ring with k nearest neighbors” with probability p replace it with a new edge (u,w) with uniformly random choice of existing node w.

Creating Watts-Strogatz Graph

Here is the syntax of the function:

age_create_watts_strogatz_graph(graph_name Name, n int, k int, p float
                                vertex_label_name Name DEFAULT = NULL,
                                vertex_properties agtype DEFAULT = NULL,
                                edge_label_name Name DEAULT = NULL,
                                edge_properties agtype DEFAULT = NULL,
                                bidirectional bool DEFAULT = true)

• graph_name - Name of the graph to be created
• n - The number of nodes
• k - Each node is joined with its k nearest neighbors in a ring topology.
• p -The probability of rewiring each edge
• vertex_label_name - Name of the label to assign each vertex to.
• vertex_properties - Property values to assign each vertex. Default is NULL
• edge_label_name - Name of the label to assign each edge to.
• edge_properties - Property values to assign each edge. Default is NULL
• bidirectional - Bidirectional True or False. Default True.

Examples

SELECT * FROM 
    age_create_watts_strogatz_graph('gp1', 8, 2, 0.5,
                                    'vertices',
                                    NULL,
                                    'edges',
                                    NULL,
                                    true);

This query creates a graph named gp1 with 8 nodes. Each node is connected to its 2 nearest neighbors, and there is a 50% chance of rewiring each connection between two nodes. The node label is vertices, and the edge label is edges. Neither the vertices nor the edges have any properties, and the graph is bidirectional.

SELECT * FROM 
    age_create_watts_strogatz_graph('gp2', 8, 5, 0.5, 
                                    'vertices',
                                    '{"type":"vertex"}',
                                    'edges',
                                    '{"type":"edge", "connection":"strong"}',
                                    false);

This query creates a graph named gp2 with 8 nodes. Each node is connected to its 4 nearest neighbors, k-1 since k is odd, and there is a 50% chance of rewiring each connection between two nodes. The node label is vertices, and the edge label is edges. Each node has a property called type and its value is vertex. For the edges, there are 2 properties named type and cconnection, with the values edge and strong, respectively. This graph is not bidirectional.

Conclusion

When the functionality is merged into the source code, we will be able to create a Watts-Strogatz graph using the provided function and examples. This will enhance the graph generation algorithms in Apache AGE.