Question

1. For the next few questions, consider a network formed by 500 students in a dorm as the nodes.

The edges in this network represent roommate relationships, i.e. two nodes are connected if they are currently roommates. In this form, the rooms are mostly double occupancy with a few triples and quads.

What is the mode (most frequent value) of the node degrees?

2. Consider the aforementioned roommate network. How many nodes are in the largest clique in the network?

3.Consider the aforementioned roommate network. Would an adjacency matrix of this graph contain mostly ones or zeros?

4.Consider the aforementioned roommate network. Among the following types of network representations, which would be more compact? Adjacency Matrix or Adjacency List?

5.Consider the aforementioned roommate network. Which of the following best describes the connectivity of this graph?

Not connected

Weakly connected

None of the above

Strongly connected

Answer 1

Ans-1: Mode is the most frequent value. In the quesiton, mode of nodes' degree is asked. A degree of a node x is the number of nodes that are adjacent to x. So, given network would contain degrees of nodes as below:

d₁,d₂,d₃, d₄, d₅, d₆, d₇, d₈, d₉... = 1, 1, 2, 1, 1, 3, 1, 1, 1, 1...

Here d_i = '1' represents that node i is connected to only single node, '2' represent that it is connected to two othe nodes and '3' represents that it is connected to three other nodes.

As the question stats that most of the connections are doubly i.e. most of the nodes will have their degree as 1.

So mode will be 1.

Ans-2: Clique is a subset C of vertices(nodes) of an undirected graph such that the subgraph induced by C is fully connected. Largest clique will be the clique which has the largest number of vertices. Vertices are fully connected in a clique i.e. You can start from a vertex 'x' and can traverse all other vertices and then come back to 'x' itself.

Let say given network G = {v1, v2, v3, ..., v500}. As the question stats that there are quad occupancy i.e. there would be some groups of 4 vertices which are connected to each other only(4 students in a dorm 'D')

So number of nodes in Largest clique would be 4.

Ans-3: Adjacency matrix would contain most of zeros as the network is sparse. An entry in matrix show edge between them. The network contain 500 students i.e. matrix of 500x500 but most of the relationship is doubly, a few are tripple and quad.

Ans-4: As the network is sparse(less 1s and more 0s), An adjacency list would be more compact.

Ans-5: The aformentioned graph is not connected. This graph has connected components in the size of 2, 3 and 4.

A undirected graph(network) is connected if and only if there is a path between any two vertices i.e. you can start from a vertex x and traverse all other vertices and come back to x. This property should hold for all the vertices in the graph.