Webwhompers

It is often useful to consider only part of a graph. Induced subgraphs are one particularly convenient way to define a specific sub-part of a larger graph.

Given a graph G=(V,E), an induced subgraph is defined by a subset of vertices S (i.e., S ⊆ V). Then

• The nodes of the subgraph induced by S are simply the nodes in S, and
• The edges of the subgraph induced by S are all edges in E that have both endpoints in S.

Example 1: Consider the graph G=(V,E) drawn below.

The subgraph induced by the subset of nodes S={1, 2, 3, 4} can then be drawn:

Example 2: Let G=(V,E) be the Facebook friends network:

• V = {x: x has a Facebook account}
• E = {{x,y}: x and y are Facebook friends}

This is a big network: if we want to draw it, we must consider a small subgraph. One way to define a subgraph is to run the Touchgraph Facebook browser and ask to see your top 4 friends, not including yourself. When Bruce Hoppe does that, Touchgraph calculates his top 4 friends as the set S={KenM, AlanP, MarkB, Patti}.

Although the notion of "top 4 friends" is admittedly murky, once we have defined a subset of Facebook accounts, such as S={KenM, AlanP, MarkB, Patti}, then that subset S unambiguously induces a subgraph of the Facebook friends network. In this case, Touchgraph draws the induced subgraph for us: