Webwhompers

The following sections present a "semi-formal" definition of clusters in three parts:

1. First, we formally define connected component
2. Second, we introduce and formally define clique
3. Third, we informally define cluster based on the above two formal definitions

Given an undirected graph G=(V,E), we define a connected component to be a subgraph induced by node set S⊆V (i.e., G_S = (S,E_S)) with the following two properties:

1. G_S is connected
2. There is no edge in E that joins a node in S to a node not in S

The above 2 mathematical properties of a connected component translate into the button-and-thread metaphor as follows:

1. G_S is connected: The only buttons that rise off the floor do so because of the one button you are lifting and the threads that ultimately connect that button to other buttons (i.e., paths)
2. There is no edge in E that joins a node in S to a node not in S: You have lifted the one button in your hand high enough so that no more buttons will come off the floor no matter how much higher you lift the button you are holding.

For example:

The graph G₂ (drawn above and again below) is not a connected component because it violates property #1: it is not connected.

The subgraph induced by S={c,d,e,f} (drawn with dark nodes and edges below) is not a connected component because it violates property #2. There are edges in E that join nodes in S to node b, which is a node not in S.