Network Components and the Giant Component

Essential knowledge:

• A network is a set of nodes and a set of edges between nodes, this means that it is possible to have a network that is made up of several islands of nodes, where no connections exist between nodes on different islands.

• In Network theory these islands are called Components. For example in a social network we might see two separate groups of friends where there are no friendships between the groups, in this case we have two components.

• In many networks as the network grows the components get gradually connected together. At some point we can say that a significant proportion of the nodes are connected together in one Giant Component.

• There is no strict definition of when a component becomes giant, so it really depends on the type of network. We might simply say that a component becomes giant when a majority of nodes are connected (more than half).

You may be interested that:

Network components are related to how well connected a network is, and often a social network will evolve as it is used, starting with many components and ending with a giant component.

The best way to understand what are the network components is to look at an example:

It may seem counter intuitive but we actually consider the diagram above as a single network (a set of nodes and a set of edges between those nodes) and it clearly contains two parts. Those separated parts are the network components.

A giant component is a connected component of a network that contains a significant proportion of the entire nodes in the network. Typically as the network expands the giant component will continue to have a significant fraction of the nodes.

In the example above we might say that the component on the left is a giant component, as it contains a significant proportion of all the nodes in the network.

Social networks often start off having many components, but as they grow a giant component forms. For example, when it launched the FutureLearn social network of learners would have had many components based around each course, but as the platform is used over time, and people register for additional courses, those components start to be connected, and a giant component emerges.

Can you think of social networks that tend to have many components rather than one giant component? Is this because they are at an early stage of development, or is it intentional?

If you’re really curious:

In a directed network (a network where the edges have a direction), one can differentiate between two types of components:

• strongly connected components

• weakly connected components

A strongly connected component of a directed graph is the maximum set of nodes such that for every pair of nodes x and y, there is a direct path from x to y and a direct reverse path from y to x. Also there is no larger set with this property.

On the other hand, in a weakly connected component each node can be reached from any other node by following edges regardless of the direction.

Let’s consider our example again, but this time with directed edges (the diagram below). On the left you can see that the weakly connected components in the network are ABCDE and FGH, in which each node can reach any other by ignoring the direction. It is essentially as if the network was undirected as per our previous example above.

However, the shaded areas on the right represent the strongly connected components in the network (B, ACDE, F and GH) where each node can be reached by any other node in the same component.