418
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
all nodes until each is assigned to some SCC. Note that in the extreme case, a
node v is in an SCC consisting of itself only, if
NG(v, ∞) ∩NG′(v, ∞) = {v}
If we make the latter choice, the resulting graph is called the transitive re-
duction of the original graph G. The transitive reduction is always acyclic, since
if it had a cycle there would remain an SCC of more than one node. However, it
is not necessary to reduce to an acyclic graph, as long as the resulting graph has
suﬃciently few nodes that it is feasible to compute the full transitive closure of
this graph; that is, the number of nodes is small enough that we can deal with
a result whose size is proportional to the square of that number of nodes.
While the transitive closure of the reduced graph is not exactly the same
as the transitive closure of the original graph, the former, plus the information
about what SCC each original node belongs to is enough to tell us anything
that the transitive closure of the original graph tells us. If we want to know
whether Path(u, v) is true in the original graph, ﬁnd the SCC’s containing u
and v. If u and v belong to the same SCC, then surely u can reach v. If they
belong to diﬀerent SCC’s s and t, respectively, determine whether s reaches t
in the reduced graph. If so, then u reaches v in the original graph, and if not,
then not.
Example 10.33 : Let us reconsider the “bowtie” picture of the Web from
Section 5.1.3. The number of nodes in the part of the graph examined was
over 200 million; surely too large to deal with data of size proportional to the
square of that number. There was one large set of nodes called “the SCC” that
was regarded as the center of the graph. Since about one node in four was
in this SCC, it would be collapsed to a single node as soon as any one of its
members was chosen at random. But there are many other SCC’s in the Web,
even though they were not shown explicitly in the “bowtie.” For instance, the
in-component would have within it many large SCC’s. The nodes in one of
these SCC’s can reach each other, and can reach some of the other nodes in the
in-component, and of course they can reach all the nodes in the central SCC.
The SCC’s in the in- and out-components, the tubes, and other structures can
all be collapsed, leading to a far smaller graph.
✷
10.8.11
Approximating the Sizes of Neighborhoods
In this section we shall take up the problem of computing the neighborhood
proﬁle for each node of a large graph. A variant of the problem, which yields
to the same technique, is to ﬁnd the size of the reachable set for each node v,
i.e., the set we have called N(v, ∞). Recall that for a graph of a billion nodes,
it is totally infeasible to compute the neighborhoods for each node, even using
a very large cluster of machines. Even if we want only a count of the nodes in
each neighborhood, rather than the nodes themselves, we need to remember the
