CSCI-1080 Intro To CS: World Wide Web

Saint Louis University, Department of Computer Science

Network Structure

“Connected”: a word of many meanings

The word “connected” speaks to the most basic structural properties of networks. It is arguably both the most important and the most overused term in the network vocabulary.

Important and proper uses of “connected”:

Connected has several distinct formal definitions, each of which is important. We introduce three of them here and elaborate the details later.

• A path connects its origin and destination nodes

• Two nodes are connected if there is at least one path that connects them

• A graph is connected if each of its nodes is connected to all the others

Examples:

• Nodes 6 and 2 are connected in graph G1 below

• Nodes a and b are not connected in graph G2 below

• Graph G1 is connected; graph G2 is not connected

Graph G1 = (V1,E1)

Graph G2 = (V2,E2)

Common sloppy uses of “connected”:

Sometimes “connected” is used informally when another term would be more clear. For example, avoid using “connected” when one of these unambiguous words would apply:

• Joined

• Adjacent

• Incident

Induced Subgraphs

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 , an induced subgraph is defined by a subset of vertices (i.e., ). Then

• The nodes of the subgraph induced by are simply the nodes in , and

• The edges of the subgraph induced by are all edges in that have both endpoints in .

• We can write the induced subgraph formally as , where is the set of edges defined above (edges in that have both endpoints in ).

Example 1: Consider the graph drawn below.

Original graph

The subgraph induced by the subset of nodes can then be drawn:

Induced subgraph

Example 2: Let 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.

“Connected” defined formally

Earlier we stated that:

• A path connects its origin and destination nodes

• Two nodes are connected if there is at least one path that connects them

• A graph is connected if each of its nodes is connected to all the others

“Connected nodes” defined formally:

Given an undirected graph , two nodes x and y (i.e., and ) are connected if and only if one of the following is true:

• x=y, or

• there is at least one path in G with origin x and destination y

The most important clarification in our formal definition of connected nodes is that any node is by definition connected to itself.

Connected graphs and connected components

A connected graph (as defined above) is said to consist of a single connected component. If a graph is not connected, then it consists of two or more connected components.

The book Six Degrees offers this intuitive metaphor for connected component:

The following examples illustrate the idea of connected component.

Graph G1 is connected and therefore has 1 connected component:

Graph G2 has 2 connected components:

Graph G3 has 3 connected components:

A connected component can be defined as an induced subgraph. For example, (above) consists of three connected components:

• the subgraph induced by {1,2,5,6}

• the subgraph induced by {3,4}

• the subgraph induced by {7,8}

Hubs

A hub is a node in a graph with much higher degree than average. For example, nodes 1 and 2 are both hubs in the figure below:

Clusters

Informally speaking, a cluster is a group of nodes in a graph that are more connected to each other than they are to the rest of the graph. For example, the red and yellow regions below are clusters:

Defining clusters, part one: connected components

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

• First, we formally define connected component

• Second, we introduce and formally define clique

• Third, we informally define cluster based on the above two formal definitions

Given an undirected graph , we define a connected component to be a subgraph induced by node set i.e., , with the following two properties:

1. 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:

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)

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 (drawn above and again below) is not a connected component because it violates property : it is not connected.

Graph G2 = (V2,E2)

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 . There are edges in E that join nodes in S to node b, which is a node not in S.

Defining clusters, part two: cliques

In an undirected graph a clique is a subgraph induced by node set i.e., ) such that the density of is 1. Put another way, in a clique, every pair of nodes is adjacent.

Example: Consider undirected graph drawn below.

The following are cliques:

• The subgraph induced by {c,d,e,f}

• The subgraph induced by {b,f}

The following are not cliques:

• The subgraph induced by {a,b,c}

• The subgraph induced by {b,c,d,e}, which is drawn below. The subgraph is not a clique since its density is less than 1.

The subgraph induced by {c,d,e,f} is the largest clique in G: the clique with the most nodes. Usually the largest clique in a graph is the most interesting clique in that graph.

Defining clusters, part three

Our definition of cluster informally draws upon our formal definitions of connected components and cliques.

In an undirected graph a cluster is a subgraph induced by node set i.e., with the following two properties:

• The average degree of is “relatively high”; (a relaxed adaptation of clique-ness)

• There are “relatively few” edges in E that join a node in S to a node not in S; (a relaxed adaptation of connected component-ness)

Example: In the graph drawn below, the following subsets of nodes induce subgraphs that can fairly be called clusters:

Subsets of nodes:

• {1,2,3,4,5,7}

• {20,21,22,23,24,25}

• {14,15,16}

Corresponding clusters:

Not all connected components are clusters. For example:

• In the graph above, the subgraph induced by {9,10,11,12,13} is a connected component, but it is arguably not a cluster, because the average degree of that induced subgraph is relatively low.

• The subgraph induced by {6} is a connected component, but it is definitely not a cluster, because the average degree of the induced subgraph is zero.

Not all cliques are clusters – even relatively large cliques. For example:

• The subgraph induced by {1,2,3,4} is a clique, but it is not a cluster because every single one of those nodes is adjacent to node 5; there are too many edges joining nodes in {1,2,3,4} to nodes not in {1,2,3,4}.

• Even the largest clique in the above graph –the subgraph induced by {1,2,3,4,5}– is arguably still not a cluster because node 7 is adjacent to so many nodes in {1,2,3,4,5}.