SOCIAL NETWORKS - NPTEL JULY 2024

Week 3
1. Why do some individuals have lower clustering coefficient?
(a) They prefer solitude
(b) They have no friends at all
(c) Their friends are from different circles
(d) They are too busy to socialize
Answer: (c)
Solution: Some individuals have lower clustering coefficients in a friendship network because they connect
friends from different social circles who do not know each other, have fewer overall connections, or have more
random and dispersed friendship patterns, leading to fewer mutual friends
2. Which of the following best describes betweenness centrality of a node?
(a) All the paths between the given node and the highest degree node.
(b) All the shortest paths that pass through the given node.
(c) All the paths that pass through the given node.
(d) All the shortest paths between the given node and the highest degree node.
Answer: (b)
Solution: Betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair
of nodes in a connected graph, there exists at least one shortest path between the nodes. The betweenness
centrality for each node is the number of these shortest paths that pass through the node.
3. What is the neighbourhood overlap of an edge connecting B and C from the below given graph?

Figure 1: Graph H

(a) 1/2
(b) 2/5
(c) 1/6
(d) 1/4

1
SOCIAL NETWORKS NPTEL - JUL 2024

Answer: (a)
Solution: Neighbourhood overlap of an edge connecting A and B is defined as the ratio of number of nodes
who are neighbors of both A and B to the number of nodes who are neighbors of at least one of A and B. In
the given graph, the ratio is, evidently, 1/2 for an edge connecting B and C.
4. Compute the embeddedness of the edge AB in the graph H in Figure 1.
(a) 0
(b) 1
(c) 2
(d) 3
Answer: (c)
Solution: Embeddedness of an edge in a network to be the number of common neighbors the two endpoints
have
5. Assume the neighborhood overlap of an edge ’e’ is 0, then ’e’ is
(a) local bridge
(b) strong tie
(c) an edge with high betweenness
(d) edge to be removed first in Girvan Newmann algorithm
Answer: (a)
Solution: A local bridge is an edge connecting two nodes with no common neighbors, meaning its removal would
increase the shortest path length between those nodes. Hence, low neighborhood overlap typically signifies that
an edge plays a crucial role in connecting different parts of the network, acting as a local bridge.
6. Consider a large social network where we have two communities C1 and C2 that are connected by only through
two nodes P and Q. They exhibit a property called

(a) Neighborhood overlap

Answer: (c)
Solution: Structural holes refer to gaps or ”holes” in a network where certain nodes bridge or connect otherwise
disconnected parts of the network. In this case, nodes P and Q act as bridges between the two communities
C1 and C2, highlighting the concept of structural holes.
7. Which of the following conditions is typically used to identify an ideal community within a network?

(a) High edge density within the community and low edge density with nodes outside the community
(b) Low clustering coefficient within the community and high clustering coefficient with nodes outside the
community
(c) High degree centrality within the community and low degree centrality with nodes outside the community
(d) High neighborhood overlap within the community and high degree centrality with nodes outside the
community

Answer:(a)

Solution: An ideal community in a social network is often characterized by a high density of connections among
its members (high edge density within the community) and relatively few connections between its members
and those outside the community (low edge density with nodes outside the community). This ensures that the
community is tightly-knit internally while being isolated from other communities.
8. Alex starts a new job and establishes connections with both his new colleagues and an external network of
industry professionals. What role/property of social networks is exemplified by Alex in this situation?

2
SOCIAL NETWORKS NPTEL - JUL 2024

(a) Structural hole

Answer:(c)
Solution: Alex connects two different groups (new colleagues and external industry professionals) that may
otherwise be disconnected, thereby filling a structural hole. Alex’s role in linking these two groups demonstrates
brokerage, as he facilitates connections between otherwise separate networks. Thus, Alex’s role exemplifies both
structural holes and brokerage.
9. According to Girvan Newman method, the most vital edge for connecting different regions of the network is
the node with ——– betweenness.

(a) zero
(b) low
(c) high
(d) medium

Answer: (c)
Solution: The Girvan-Newman method is used for community detection in networks by iteratively removing
edges with the highest betweenness centrality. Betweenness centrality measures how often an edge lies on
the shortest path between pairs of nodes. Edges with high betweenness are considered crucial for connecting
different parts of the network. By removing these edges, the method aims to reveal the underlying community
structure of the network.
10. For each pair of nodes A and B in the graph, the flow between A and B divides itself evenly along all the
possible shortest paths from A to B: so if there are k shortest paths from A and B, then 1/k units of flow pass
along each one. Here we define the betweenness of an edge to be the total amount of flow it carries, counting
flow between all pairs of nodes using this edge. Which edge will be removed first based on Girvan Newman
method?

Figure 2: Graph H

A. 6-7
B. 1-3
C. 4-6
D. 6-5
Answer: (a)
Solution: The 6-7 edge carries the full unit of flow from each node among 4, 5, and 6 to each of the other nodes
1,2,3, and 7. Thus the betweenness is 3.4=12 which is the highest.