Webwhompers

Chapter 2 of Six Degrees pp 56-61 has a good introduction to homophily and triadic closure. Read that before you continue. The following algorithm describes the process of repeated triadic closure:

Triadic Closure Algorithm:

Input:

An undirected graph G=(V,E) with |V|>0 and |E|>0

Output:

See below...

Steps:

1. Look for two nodes x, y that are non-adjacent and share a common neighbor
2. If no such pair of nodes x, y exists, then we’re done
3. Add element {x,y} to set E
4. Go to step 1

The output of the triadic closure algorithm has some notable properties. We can deduce these properties from the following observations:

Consider the closing of a single triad: Nodes x and y are non-adjacent and share a common neighbor; then x and y are joined by edge {x,y}.

1. Adding edge {x,y} does not change the number of connected components in G. Nodes x and y were already connected before we joined them with {x,y}.
2. Adding edge {x,y} increases the density of the connected component that contains nodes x and y.

Repeating the above observations over the course of every iteration of the triadic closure algorithm, we see that the output graph G'=(V,E') computed by the algorithm has these two properties

1. Output graph G' has exactly the same number of connected components as input graph G. Furthermore, the nodes that induce each connected component are the same in G' and G.
2. Each connected component of G' has the maximum possible density: it is a clique.

Example: Suppose the triadic closure algorithm starts with graph G=(V,E) drawn below:

Upon completion, the algorithm will have added all the orange edges drawn below: