Six Degrees of Separation Using Apache AGE
Tags: postgres, apacheage, graph
Published: 2023-07-20 17:35:51

Have you ever heard of Six degrees of separation? It is an idea introduced by Frigyes Karinthy which says that people are six or fewer social connections away from each other. Yes, the idea suggests that you are six or less phone calls away from Elon Musk 😃.

This concept is of great importance to social networks like Facebook, LinkedIn, Twitter, etc. For example, Twitter suggests that you follow certain accounts because one or some of the people you follow follows them. LinkedIn can tell the social distance between two people by their network.

How can we represent these in computers? The most effective way to represent this kind of data is using the graph data structure. A graph consists of nodes/vertices and edges. Every node represents an object, and edges connect nodes to show the relationship between them. 

In a social network, people are nodes, and edge represent the relationship between them.

![Graph containing 3 nodes and 2 edges](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v52m896qei0zvjsiy9tk.png)

## Social Network
Let's create a social network using Apache AGE, a graph extension for PostgreSQL, and with it, find out the degree of separation between people.

### Prerequisites
To begin, you will need to have PostgreSQL, Apache AGE, and AGE Viewer installed.
* [Download PostgreSQL](https://www.postgresql.org/download/)
* [Download and install Apache AGE and AGE Viewer](https://theundersurfers.netlify.app/age-installation/)

To begin, create a new database and connect to it.

To be able to use the AGE extension, it needs to be loaded for every session. Also, to simplify our queries, we will add `ag_catalog` to PostgreSQL's search path.

```sql
CREATE EXTENSION age;
LOAD 'age';
SET search_path = ag_catalog, "$user", public;
```


### People
To simplify this example, each node will contain only one property, which will the name of the person

```sql
SELECT * from cypher('social_network', $$
    CREATE (:Person {name: 'Joseph'}),
     (:Person {name: 'Alice'}),
     (:Person {name: 'Ade'}),
     (:Person {name: 'Mariam'}),
     (:Person {name: 'Ryan'}),
     (:Person {name: 'Fred'})
$$) AS (v agtype);
```
Now, we create a graph.

```sql
SELECT create_graph('social_network');
```

### Friends
Next, we will represent their relationships by creating an edge between them. So if Joseph and Alice are friends, an edge with the 
label `is_friends_with` is created between them.

```sql
SELECT * from cypher('social_network', $$
    MATCH (x:Person), (y:Person) WHERE x.name = 'Joseph' AND y.name = 'Alice'
    CREATE (x)-[:Is_friends_with]->(y)-[:Is_friends_with]->(x)
$$) AS (e agtype);
```

To prevent this post from being too long, you can see the full source code used in the [GitHub gist](https://gist.github.com/Allison-E/bcae7622087c51e4a40105852cca974d) I created. Running the script will give you the network below.

![Social network graph](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3iz8klwb61ffydwjbmd4.png)

## Degree of Separation
To find out the degree of separation between two people, we look for the shortest path between them. For example, to find the degree of separation between Joseph and Ade, we use:

```sql
SELECT * from cypher('social_network', $$
    MATCH paths = (x:Person {name: 'Joseph'})-[:Is_friends_with * 1..6]->(y:Person {name: 'Ade'})

    RETURN min(length(paths)) as degree
$$) AS (degree agtype);
```

We receive an output which tells us that Joseph is 3 people away from Ade.

```sql
 degree 
--------
 3
```

## Conclusion
Today, we learnt about six degrees of separation and how it could be implemented using Apache AGE. We could use this build recommender systems, evaluate the strength of social networks and in marketing analysis.

## See also
* [Six Degrees of Separation - Wikipedia](https://en.wikipedia.org/wiki/Six_degrees_of_separation)
* [Creating a Graph Database for a Social Network with Apache AGE](https://dev.to/matheusfarias03/creating-a-graph-database-for-a-social-network-with-apache-age-161i)