Which data structures would be useful and efficient to store following information on social networking sites?

This is a direct use case of Directed Graphs.

If you understand what directed graphs are: There are certain nodes (data points) and there are one way connections between these nodes.

In our particular use case, let’s assume that each individual account at our social media website is represented as a node.

Now, if let’s say user A follows user B, we can make a directed edge from user A to user B.

Example: in this case, A has followed B. B has followed C. C user has followed E, and so on.

Now, let me introduce the concept of indegree and outdegree.

Indegree of a node is the number of edges directed into that node. For example, the indegree of node F is 1. indegree of node B is 2 (There are 2 edges A->B and D->B directed into B).

Outdegree of a node is similarly the number of edges directed outwards from a node. Example: C has an outdegree of 1. E has an outdegree of 2. F has an outdegree of 0.

If we want to know the number of followers of a particular user, we just need to look at the indegree of that node. If we want to know the number of people a user is following, we note the outdegree of that node. Example: If we take a look at E, it is being followed by C: indegree of E is 1. And, it is following D & F: outdegree of E is 2.

This is a common example that we at Programming Pathshala use to explain Graphs. An Undirected Graph can be imagined like Facebook where people become friends of other people (bidirectional connection) whereas Instagram or Twitter can be imagined as a Directed Graph (one-way connection of following).