Barabasi-Albert Graph for Apache AGE

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 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-Albert Graph Generation Function

The function is declared at age--1.2.0.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:

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:

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
Apache AGE GitHub Repo