Database Reference
In-Depth Information
We can iterate the above steps a fixed number of times. We can alternativelyiterate until
the graph becomes sufficiently small, or we could examine all nodes
v
in turn and not stop
until each node is in an SCC by itself; i.e.,
N
G
(
v,
∞) ∩
N
G
′
(
v,
∞) = {
v
}
for all remaining nodes
v
. If we make the latter choice, the resulting graph is called the
transitive reduction
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 sufficiently
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 origin-
al 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, find
the SCCs containing
u
and
v
. If one or both of these nodes have never been combined in-
to an SCC, then treat that node as an SCC by itself. If
u
and
v
belong to the same SCC,
then surely
u
can reach
v
. If they belong to different SCCs'
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.30 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 SCCs 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 SCCs 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 SCCs in the in- and out-components, the tubes, and other
structures can all be collapsed, leading to a far smaller graph.
□
10.8.7
Approximating the Sizes of Neighborhoods
In this section we shall take up the problem of computing the neighborhood profile for each
node of a large graph. A variant of the problem, which yields to the same technique, is to
