420
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
INDUCTION: Suppose we have computed Ri(v, d) for all i and v. Initialize
Ri(v, d + 1) to be Ri(v, d), for all i and v. Then, consider all arcs x →y in the
graph, in any order. For each x →y, set Ri(x, d+ 1) to the larger of its current
value and Ri(y, d).
Observe that the fact we can consider the arcs in any order may provide
a big speedup in the case that we can store the Ri’s in main memory, while
the set of arcs is so large it must be stored on disk. We can stream all the
disk blocks containing arcs one at a time, thus using only one disk access per
iteration per disk block used for arc storage. This advantage is similar to the
one we observed in Section 6.2.1, where we pointed out how frequent-itemset
algorithms like A-priori could take advantage of reading market-basket data in
a stream, where each disk block was read only once for each round.
To estimate the size of N(v, d), combine the values of the Ri(v, d) for i =
1, 2, . . . , k, as discussed in Section 4.4.3.
That is, group the R’s into small
groups, take the average, and take the median of the averages.
Another improvement to the ANF Algorithm can be had if we are only
interested in estimating the sizes of the reachable sets, N(v, ∞). It is not then
necessary to save Ri(v, d) for diﬀerent radii d. We can maintain one value Ri(v)
for each hash function hi and each node v. When on any round, we consider
arc x →y, we simply assign
Ri(x) := max
Ri(x), Ri(y)

We can stop the iteration when at some round no value of any Ri(v) changes.
Or if we know d is the diameter of the graph, we can just iterate d times.
A
B
C
D
E
G
H
F
I
Figure 10.26: A graph for exercises on neighborhoods and transitive closure
10.8.12
Exercises for Section 10.8
Exercise 10.8.1: For the graph of Fig. 10.9, which we repeat here as Fig. 10.26:
