Friendship circles are a common pattern, these consist of a limited amount of users sharing many common connections.
Now, after having thought of the basic interaction of users in social networks, we can start building a data structure that allows us to easily implement these requirements.
In the next section you will see why the graph data structure is a great fit for this problem.
Why Graphs?Simply put, graphs are nothing but a collection of nodes and edges which connect them.
In the books, you find nodes often also called vertices.
In general, nodes can represent any kind of abstract data object.
In the context of a social network, it’s obvious to represent users by nodes.
But also other abstract entities like groups, companies, events, etc.
can be modeled as nodes.
The connections between nodes are called Edges.
It exists a range of different types of edges, which allow you to model all kinds of relations between nodes.
Read the article Graph Data Structures for Beginners by @amejiarosario to learn more about the differences between directed, undirected, cyclic and acyclic graphs.
You find the link in the resources section.
What do you think?.Sounds promising, right?.Let’s dive right into building a graph and see if it’s actually as good.
Create the GraphAbove, we have figured out what’s the core functionality of a social network.
To represent this we will build a graph with nodes representing users and bi-directional edges to model the equal connection between users.
We implement the graph in an object-oriented fashion.
Therefore, we start writing a Graph constructor function which contains an empty object as it's only property.
Now To continue the implementation, we add getter and setter methods to our graph.
To add a node, we simply add the user as a key-value pair to the graph object and use the user's name as the key.
Note, in production unique ids would the better choice.
For the getter method we simply return the user which we retrieve by the name passed as properties.
Next, we create the Node constructor function.
Create NodesThe constructor function for the nodes comes only with a name and a friends property.
In general, there are two approaches to how graphs can represent nodes and their relations to each other.
The first approach, which we will apply here is called adjacency list and relies on a list, kept by each individual node, storing all of the node's edges.
The second approach is called adjacency matrix.
Such are especially useful for complex (directed and weighted edges) and highly dense graphs.
Read more about the benefits of each representation in When are adjacency lists or matrices the better choice?.you find the link in the resources section.
The friends property acts as our adjacency list and stores all connected users.
We could simply use an array or a set to store the connections' names.
However, an object is more performant as we will need to check for already existing connections when we create an edge.
Create EdgesThe last missing piece to complete the basic network, is a method to add connections between nodes.
As we decided on bidirectional edges, we need to add the connection to both involved nodes.
To do so, we call addConnection within itself with the user's node we want to connect with.
Thanks to the condition which wraps the actual logic, we do not end up in an infinite loop.
Having all this in place, we can actually start adding users to our network!Grow the Network!To start our network, let’s create a couple of nodes and connect them.
Therefore, we first create a couple of nodes.
Next, we instantiate a graph and add the nodes to it.
In the final step, we connect nodes to each other.
You can use the helper function writeToJSON to export your graph to a json to get a better overview.
In this repo you can find it.
Pretty cool, right?Visualise the Network!If you want to visualise your network and play with it, check out the visualisation tool on hinsencamp.
As a next step, you should run another helper function — the network generator.
It generates random networks with up to 150 users.
It’s also good fun to play around with the number of participants.
You will see, with increasing network size it becomes quickly impossible to keep an overview by just looking at the JSON object.
For a better overview, you can drop the JSON object in the visualiser as well.
ConclusionWe have built the initial data structure for a social network.
Therefore, we have created constructors for the graph and nodes representing users.
Moreover, we added edges connecting these nodes bi-directional.
This structure represents a solid foundation to build more powerful features on top of it.
Here are some hints of what could be added next:Methods to delete edges and nodesDifferent types of nodes like “groups” or “companies”Search Algorithms like Breadth-first search (BFS)Recommend users new friends by comparing sets of edges.
Let me know what interests you the most on twitter @hinsencamp!.Based on your feedback, I will choose the next tutorial topic.
When you are interested in going into production with a graph-based solution you should consider graph databases, which provide many features of graphs out of the box.
It’s worth having a look at the following free graph databases Neo4J, OrientDB and GunDB.
Originally published at https://hinsencamp.