Barabasi-Albert Graph for Apache AGE
Tags: algorithms, postgres, development, opensource
Published: 2023-05-16 19:09:39

## Introduction

The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the World Wide Web, citation networks, and some social networks are thought to be approximately scale-free and certainly contain few nodes (called hubs) with unusually high degree as compared to the other nodes of the network. The BA model tries to explain the existence of such nodes in real networks. The algorithm is named for its inventors Albert-László Barabási and Réka Albert.

I've been working on a feature for Apache AGE where it is possible to generate the Barabasi-Albert graph. AGE is an opensource extension for PostgreSQL that enables users to leverage a graph database on top of existing relational databases. Here's the [Pull Request](https://github.com/apache/age/pull/917) for it.

## Background

The BA model starts with a small number of nodes and then iteratively adds new nodes to the graph. Each new node is connected to m existing nodes, where m is a fixed parameter of the model. The probability that a new node is connected to an existing node is proportional to the degree of the existing node, meaning that nodes with higher degrees are more likely to receive new connections.

![barabasi-explain](https://upload.wikimedia.org/wikipedia/commons/4/40/Barabasi_albert_graph.svg)

## Barabasi-Albert Graph Generation Function


The function is declared at `age--1.2.0.sql`:

```sql
CREATE FUNCTION ag_catalog.age_create_barabasi_albert_graph(graph_name name, 
                                                            num_vertices int,
                                                            num_edges int,
                                                            node_label name = NULL,
                                                            edge_label name = NULL,
                                                            bidirectional bool = true)
RETURNS void
LANGUAGE c
CALLED ON NULL INPUT
PARALLEL SAFE
AS 'MODULE_PATHNAME';
```

This function will receive six arguments: the name of the graph, the total number of vertices, the number of edges each vertex will connect to, the label for the nodes, the label for the edges and if these connections shall be bidirectional or not (the default is `true`). AGE's standard node and vertex label are `_ag_label_vertex` and `_ag_label_edge`, the label's name arguments are set to NULL, so that, if no argument is passed, it will create vertices and edges of the standard label. 

To use it, you can simply call:
```sql
SELECT age_create_barabasi_albert_graph('BarabasiAlbertGraph', 100, 1, NULL, NULL, true);

NOTICE:  graph "BarabasiAlbertGraph" has been created
 age_create_barabasi_albert_graph 
----------------------------------
 
(1 row)
```

And with AGE Viewer, we can visualize it like so:

![AGE Viewer Graph](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/z20tishxwflz7i918glo.png)

## Conclusion
With this feature developed for Apache AGE, users will easily generate Barabasi-Albert graphs within the PostgreSQL environment. Incorporating the Barabasi-Albert model into AGE expands its capabilities and empowers users to analyze and explore scale-free networks efficiently.

If you want to learn more about Apache AGE, checkout my other posts, the Apache AGE website, and it's GitHub repository:

[Apache AGE Website](https://age.apache.org/)
[Apache AGE GitHub Repo](https://github.com/apache/age)