Apache AGE: Watts-Strogatz Graph
Tags: apacheage, tutorial, postgres, algorithms
Published: 2023-06-02 16:22:44

## **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](https://github.com/AGEDB-INC/postgraph/pull/139). 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.