Homework IX: Subgroups, Graph Connectivity, and Structural Similarity

Cliques and n-Cliques

Figure 1: An undirected graph.

1. List the nodes in all the cliques of size four in Figure 1.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

2. List the nodes in all the cliques of size five in Figure 1.
   
   
   
   
   
   

3. How many cliques of size four does node A belong to?
   
   
   
   
   
   

4. List the nodes in one of the 2-cliques in Figure 1:
   
   
   
   

5. List the nodes in the five cliques of size four nested inside the clique of size five in Figure 1.
   
   
   
   
   
   
   
   
   
   

Structural Equivalence and Structural Similarity

Figure 2: An undirected graph.

• In the matrix below, write down the cell entries for the adjacency matrix corresponding to the graph shown in Figure 2:

	A	B	C	D	E	F	G	H	I	J	K	L
A	----
B		----
C			----
D				----
E					----
F						----
G							----
H								----
I									----
J										----
K											----
L												----

• Using the information from the previous matrix, in the matrix below, write down the cell entries for the structural similarity matrix corresponding to the graph shown in Figure 2 using the Euclidean Distance:

	A	B	C	D	E	F	G	H	I	J	K	L
A	----
B		----
C			----
D				----
E					----
F						----
G							----
H								----
I									----
J										----
K											----
L												----

1. Using the Information in the previous matrix, write down the sets of nodes that are structurally equivalent (e.g., connected to the same set of neighbors) in the graph shown in Figure 2.
   
   
   
   

2. Out of the nodes that are not structurally equivalent, which pairs of nodes have the highest structural similarity in the graph shown in Figure 2?
   
   
   
   

3. Using the Jaccard Similarity metric, compute the structural similarity between nodes J and M in the graph shown in Figure 1.
   
   
   
   

4. Using the Dice Similarity metric, compute the structural similarity between nodes E and N in the graph shown in Figure 1.
   
   
   
   

5. Using the Cosine Similarity metric, compute the structural similarity between nodes D and H in the graph shown in Figure 1.
   
   
   
   

Graph Connectivity

1. Write down a node cut set for the graph shown in Figure 1.
   
   
   
   

2. Write down an edge cut set for the graph shown in Figure 1.
   
   
   
   

3. What is the k-connectivity of the graph in Figure 1?
   
   
   
   

4. What is the edge connectivity of the graph in Figure 1?
   
   
   
   

5. What is the pairwise k-connectivity between nodes E and N in Figure 1?