ECE398BD: Making Sense of Big Data
Quiz 3
Peter Kairouz and Pramod Viswanath
Due 10:00 a.m. September 10, 2014
In this in-lab quiz, you will analyze rumor spreads on irregular graphs. Make sure you read the uploaded
lecture notes carefully before solving the problems. The grading is based on your write-up which is due at
10 a.m. September 10, 2014.
The Breadth-First Search (BFS) algorithm is a popular graph traversal strategy. The search begins
at an initial node and visits all its neighboring nodes. Then for each one of those neighboring nodes, it visits
their unvisited neighboring nodes, and so on. In general, the BFS sequence (order in which nodes are visited)
is not unique. For this quiz, assume that the neighbors of a node are visited in increasing order. This makes
the BFS sequence unique. For example, if we consider the graph in Figure 1a and start the search at node
0, then BFS visits the nodes in the following order 0, 1, 2, 3, 4, 5, 6. If we start the search at node 5, then
BFS visits the nodes in the following order 5, 1, 0, 4, 2, 3, 6. If we consider the graph in Figure 1b and start
the search at node 6, then BFS visits the nodes in the following order 6, 2, 1, 3, 4, 5, 7, 8, 9.
1. (10 pts) Message Passing Complexity
(a) What is the runtime complexity (as a function of N ) of the rumor centrality and Jordan centrality
message passing algorithms discussed in class? Justify your answer.
2. (40 pts) Rumors on Irregular Graphs
(a) Consider the infection graphs shown in Figure 1. For each graph, list all the permitted orderings
for each possible rumor source.
(b) For each graph, compute the probability of each permitted ordering and deduce the exact ML
estimate vˆ = arg maxv∈GN P (GN |v) for v ∗ , the rumor source.
(c) For each graph, compare your answers in part (b) to those given by vˆ = arg maxv∈GN R (v, GN )
and v¯ = arg maxv∈GN J (v, GN ), where R (v, GN ) is the rumor centrality of v in GN and J (v, GN )
is the Jordan centrality of v in GN . Is there any difference, why or why not?
(d) For each graph, compare your answers in parts (b) and (c) to that given by the following heuristic
v˜ = arg max P (σv∗ |v) R (v, GN ) ,
v∈GN
where σv∗ is the breadth-first search (BFS) permitted ordering with node v as the rumor source.
Is there any difference, why or why not?
1
2
0
2
1
4
3
5
6
(a) Irregular graph G1 with N = 4
6
7
2
3
1
5
4
9
8
(b) Irregular graph G2 with N = 5
Figure 1: Examples of irregular graphs

OFFICIAL RESULTS

Universität des Saarlandes