COMP 3121 Homework 3
Question 1
Suppose you’re working with a group of researchers studying social networks, with a particular
focus on the distances between people in such networks, and the broader implications for the
small-world phenomenon.
The research group is currently negotiating an agreement with a large mobile phone carrier to get
a snapshot of their “who-calls-whom” graph. With agreement, the carrier provides a graph in
which a node represents a customer, and an edge represents two people who have called each
other in the past year. (The edges will be annotated with the number of calls and the time of each
call.) Recently, the carrier proposes that they will only provide edges where two people have
called each other at least once a week on average in the past year. (In other words, all nodes will
be presented, but there will only be edges where two people talked at least 52 times.) The carrier
understands that this is not the full network, but they argue that this is a good approximation to
the full network.
Given such change, which of the following statement is true?
1) This will reduce the weak tie edges in the network
2) This will NOT reduce the weak tie edges in the network
Question 2
Consider the following graph. The distance is defined as the relative position traversing from
node to another node. For instance, the distance of node 0 and node A is 6. What is the path
outputted by decentralized search between node 0 and node 9, and why?
1) 0-C-8-9
2) 0-1-D-9
3) 0-C-B-A-9
4) 0-4-9
