10.8. NEIGHBORHOOD PROPERTIES OF GRAPHS
419
nodes found so far as we explore the graph, or else we shall not know whether
a found node is new or one we have seen already.
On the other hand, it is not so hard to ﬁnd an approximation to the size
of each neighborhood, using the Flajolet-Martin technique discussed in Section
4.4.2. Recall that this technique uses some large number of hash functions;
in this case, the hash functions are applied to the nodes of the graph. The
important property of the bit string we get when we apply hash function h to
node v is the “tail length” – the number of 0’s at the end of the string. For
any set of nodes, an estimate of the size of the set is 2R, where R is the length
of the longest tail for any member of the set. Thus, instead of storing all the
members of the set, we can instead record only the value of R for that set. Of
course, the Flajolet-Martin technique uses many diﬀerent hash functions and
combines the value of R obtained from each, so we need to record the value of
R for each hash function. Nevertheless, the total space needed for (say) several
hundred values of R is much less than the spece needed to list all the members
of a large neighborhood.
Example 10.34 : If we use a hash function that produces a 64-bit string, then
six bits are all that we need to store each value of R. For instance, if there are
a billion nodes, and we want to estimate the size of the neighborhood for each,
we can store the value of R for 20 hash functions for each node in 15 gigabytes.
✷
If we store tail lengths for each neighborhood, we can use this information
to compute estimates for the larger neighborhoods from our estimates for the
smaller neighborhoods. That is, suppose we have computed our estimates for
|N(v, d)| for all nodes v, and we want to compute estimates for the neighbor-
hoods of radius d + 1. For each hash function h, the value of R for N(v, d + 1)
is the largest of:
1. The tail of v itself and
2. The values of R associated with h and N(u, d), where v →u is an arc of
the graph.
Notice that it doesn’t matter whether a node is reachable through only one
successor of v in the graph, or through many diﬀerent successors.
We get
the same estimate in either case. This useful property was the same one we
exploited in Section 4.4.2 to avoid having to know whether a stream element
appeared once or many times in the stream.
We shall now describe the complete algorithm, called ANF (Approximate
Neighborhood Function). We choose K hash functions h1, h2, . . . , hk. For each
node v and radius d, let Ri(v, d) denote the maximum tail length of any node
in N(v, d) using hash function hi.
BASIS: To initialize, let Ri(v, 0) be the length of the tail of hi(v), for all i and
v.
