Finding connected components in a friendship graph

Friendship graph
Fig. 1: A graph with relationships among people.

Suppose that you have this graph in which each node is a person name and each edge represents an "is-friend-with" relationship. Here we can see, for instance, that Sandra knows Dennis and Dennis knows John, but Sandra doesn't know John directly. There is a degree of separation between them, but it can eventually be overcome if Dennis decided to introduce her to John. This is the idea behind the "six degrees of separation": through suitable introductions we could eventually learn to know almost anyone in the world, at least theoretically. Here the world is purposefully small. If we follow through connected nodes, we could find out not only which people are friends, but which could relatively easily become friends. In comparison, people like Nora and Yvonne may find it much harder to become friends given the existing relationships.

They may not be in the same connected component. This is the subset of people which can be reached from a given node. If the start node is Nora, we can see that we can't reach Yvonne, at least not without some extra effort that would introduce an update to this graph.

Now that we know that they are in different connected components, we can assume that the energy to bridge the connection from one component to another may be higher that the within-component energy required to make introductions between people some of which already know each other. We can expect that it is more uncomfortable to meet someone new, completely outside our circle of friends, than it is to initiate or participate in an introduction.

Below you can find which people belong to the same connected component in which a person is part of. This allows you to see which potential friendships could be relatively easy to establish.