So he's now put in a lot of work designing
and analyzing super fast algorithms for
reasoning about graphs. So in this
optional video, what I want to do is show
you why you might want such a primitive,
especially for computation on extremely
large graphs. Specifically, we're going to
look at the results of a famous study that
computes the strongly connected components
of the web graph. So what is the web
graph? Well, it's the graph in which the
vertices correspond to web pages. So for
example, I have my own web page where I,
you know, list my research papers, and
also links to courses such as this one And
the edges are going to be directed, and
they correspond precisely to hyperlinks.
So, the links that, bring you from one web
page to another. Note of course that these
are directed edges, where the tail is the
page that contains the hyperlink, and the
head is the pa, page that you go to if you
click the hyperlink, and so this is a
directed graph. So from my home page you
can get to my papers. You can get to my
courses. Sometimes I have random links up
to things I like, like say, my favorite
record store And of course for many of
these web pages there are additional links
going out and going in. So for example
from my papers I might link some to my
co-authors, some of my co-authors might be
linking from their home pages to me, or of
course there's web pages out there that
list the currently available free online
courses And so on So obviously this is
just part of a, massive, web graph, Just a
tiny, tiny piece of it. So the origins of
the web were probably around 1990 or so
but it started to really explode in the
mid'90s. And by the year 2000 it was
already beyond comprehension. Even though
in internet years the year 2000 is sort of
the Stone Age relative to right now,
relative to 2012 But still, even by 2000
people were so overwhelmed with the
massive scale of the web graph; they
wanted to understand anything about it,
even the most basic things. Of course one
issue with understanding what the graph
looks like is you don't even have it
locally, right? It's distributed over all
these different servers Over the entire
world. So the first thing people really
focused on when they wanted to answer this
question Was on techniques for crawling.
So having software which just follows lots
of hyperlinks Reports back to the home
base, from which you can assemble. At
least some kind of sketch of what this
graph actually is. So, but then the
question is Even once you have this
crawled information Even if, once you've
accessed A good chunk of the nodes and the
edges of this Of this network. What does
it look like? So what makes this a
difficult question, more difficult than,
say, for any other directed graph you
might encounter? Well, it's simply the
massive scale of the web graph, it's just
so big. So for the graph used in the
particular study I'm gonna discuss, you
know, like we said, it was in the year
2000, which was sort of the stone age
compared to 2012, so the graph was small,
relatively, but still, the graph was
really, really, big. So, it was something
like 200 million nodes and one billion
edges, really, one and a half billion
edges. So the reference for the work I'm
gonna discuss is a paper by a number of
authors. The first author is Andrei Broder
And then he has many co-authors And this
was a paper that appeared in the Dub, Dub,
Dub conference of the year 2000. That's
the World Wide Web Conference And I
encourage you, those of you who are
interested, to go track down the, the
paper on line And read the original
source. So Andrei Broder the lead author.
At this time he was at a company that was
called Alta Vista. So how many of you
remember a company called Alta Vista?
Well, some of you, especially, you know,
the youngest ones among you maybe have
never heard of Alta Vista And the youngest
ones among you maybe can't even conceive
of a world in which we didn't have Google
But in fact there was a time when we had
Web Search that it would, but Google did
not yet exist. That was sort of in the,
you know, maybe 97 or so. And so this was
in the very embryonic years of Google And
this, this data set actually came out of,
out of Alta Vista instead. So [inaudible]
etc all wanted to get some answers to this
question. What does the web graph look
like? And they approached it in a few
ways, but the one I'm going to focus on
here is they asked, well. You know, what's
the most detailed structure we can get
about this web graph without doing an
infeasible amount of computation? Really
just sticking to linear time algorithms,
at, at the worst And what have we seen?
We've seen that in a directed graph you
can get full connectivity information just
really using [inaudible] first search. You
can compute strongly connected components
in linear time with small constants, and
that's one of the major things that they
did in this study. Now if you wanted to do
this same computation today you'd have one
thing going against you and one thing
going for you. The obvious thing that
you'd have going against you is that the
web is still very much bigger Than it was
here. Certainly by an order of magnitude
The thing that you'd have going for you is
now there's specialized systems which are
meant to operate on massive data sets And
in particular, they can do things like
compute connectivity information on graph
data. So what you have to remember, for
those of you who are aware of these terms,
in 2000, there was no map reduce. There
was no [inaudible]. There were no tools
for automated processing large data sets.
These guys really had to do it from
scratch. So let me tell you about what
Broder et al found when they did strong
connectivity computations one the web
graph. They explained their results in
what they called the bow tie picture of
the web. So let's begin with the center of
the knot of the bow tie. So in the middle
we have what we're gonna call a giant,
strongly connected component. With the
interpretation being this is the core of
the web in some sense. Alright, so all of
you know what a, an SCC is at this point.
A strongly connected component is the reg
ion from which you can get from any point
to any other point along a directed path.
So in the context of the web graph, with
this giant SCC, what this means is that
from any webpage inside this [inaudible]
you can get to any other webpage inside
this [inaudible] just by traversing a
sequence of hyperlinks. And hopefully, it
doesn't strike you as too surprising that
a big chunk of the web is strongly
connected, is well connected in this sense
Right? So if you think about all these
different universities in the world. You
know, probably all of the web pages
corresponding to all of the different
universities. You can get from any one
place to any other place For example, from
the homepage on which I put my papers,
that often include links to my co-authors
which very commonly are other universities
so that already provides a web link from
some Stanford page to some page at say,
Berkeley or Cornell or whatever and of
course I'm just a one person. I'm just one
of many faculty members at Stanford. So
you put all of these together, you would
expect all of the different SCCs
corresponding to different universities to
collapse into a single one and so on for
other sectors s well. An then of course if
you knew that a huge chunk of the web was
in the same shelling ham component, let's
say ten percent of the web, which would be
tens of millions of web pages, you
wouldn't expect there to be a second one,
right, it would be super weird if there
were two different blobs, ten million web
pages each, that somehow were not mutually
reachable from each other. That would
just, all it takes to collapse two SCCs
into one, is a lone arc going from one to
the other, and then a lone arc in the
reverse direction. And then those two SCCs
collapse into one. So we do expect a giant
SCC, just sort of thinking anecdotally
about what the web looks like, and then
once we realize there's one giant SCC, we
don't expect there to be more than one.
Alright, so is that the whole story? Is
the web graph just one big SCC? Well, one
of the perhaps intere sting findings of
this [inaudible] paper is that, you know
there is a giant SCC, but it doesn't
actually take up the whole web, or
anything really that close to the entire
web. So what else would there be in such a
picture? Well, there's the other two ends
of the bow tie. Which are called the in
and the out regions In the out regions,
you have a bunch of strongly connecting
components, not giant SCCs. We've
established that shouldn't be any other
giant SCCs, but small SCCs Which you can
reach from the giant strongly connecting
component, but from which you cannot go
back to the giant strongly connecting
component. I encourage you to think about
what types of web sites you would expect
to see in this out part of the bow tie.
I'll give you once example, very often if
you look at a corporate site including
those of well known corporations, which
you would definitely expect to be
reachable from the giant SEC. There's
actually a corporate policy that no
hyperlinks can go from something in the
corporate site to something outside the
corporate site. So that means the
corporate site is going to be a collection
of web pages which are certainly strongly
connected, because it's a major
corporation you can certainly get there
from. The giant has [cough], but because
of this corporate policy you can't get
back out. Symmetrically, in the in part of
the bow tie, you have a strong [inaudible]
of components, generally small ones, from
which you can reach the giant SCC But you
cannot get through them from the giant
SCC. Again I encourage you to think about
all the different types of web-pages you
might expect to see in this import of the
bow-tie [inaudible]. Certainly one really
obvious example would be new web-pages. So
if you just create something, and then,
you know if I just created a web-page and
pointed it to Stanford University that
would immediately be in this in-component,
in this in-collection of components. Now,
if you think about it, this does not
exhaust all of the possibilities of where
notes can log. There's a few other cases.
They frankly are pretty weird, but they're
there. You can have passive hyperlinks
which bypass the giant FCC, and go
straight from the in part of the Bowtie to
the out part So [inaudible] suggested
calling these tubes. And then there's also
a kind of very curious outgrowths going
out of the in component, but which don't
make it all the way to the giant SCC, and
similarly there's stuff which goes into
the out component And [inaudible]
recommended calling these strange
creatures' tendrils And then in fact you
can also just have some weird isolated
islands of SCCs that are not connected
even weekly to the giant SCC. So this is
the picture that emerged from Broderall's
strong component computation on the web
graph and here's qualitatively some of the
main findings that they came up with. So
first of all, that picture on the previous
slide I drew roughly to scale in the sense
that all four parts, so the giant SCC, the
in-part, the out-part and then their
residual stuff; the tubes and tendrils,
have roughly the same size. You know, more
or less 25 percent of the nodes in the
graph. I think this surprised some people.
I think some people might have thought
that the core that the giant SCC might
have been a little bit bigger than just 25
or 28%. But [inaudible] is a lot of other
stuff outside of the stronger connected
core. You might wonder if this is, is just
an artifact of the, this data set being
from the Stone Age, being from 2000 or so.
But, people have rerun this experiment on,
on the web graph again in later years. And
of course the numbers are changing because
the graph is growing rapidly, but these
qualitatively findings, qualitative
findings have seemed pretty stable,
throughout subsequent, reevaluations of
the structure of the web. On the other
hand, while the. Core of the web is not as
big as you might have expected. It's
extremely well connected Perhaps better
connected than you might have expected.
Now you'd be right to ask the question.
You know, what could I mean by unusually
well connected? We've already established
that this giant core of the web is strong
and connected. You can get from any one
place to any other place, via a sequence
of hyperlinks. What else could you want?
Well, in fact. It has a very richer notion
of connectivity called the small world
property. So let me tell you about the
small world property or the phenomenon
colloquially known as six-degrees of
separation. So this is an idea which had
been in the air at least since the early
twentieth century, but it really it was
kind of studied. In a major way and
popularized by [inaudible]. Norgren was a
social scientist back in 1967. So Norgren
was interested in understanding you know
are people at great distance in fact
connected by short chains of
intermediaries. So the way he evaluated
this he ran the following experiment. He
gave he identified a friend in Boston
Massachusetts. A doctor I believe And so
this was gonna be the target And then he
identified a bunch of people who were
thought to be far away both culturally and
geographically. Specifically Omaha So for
those of you who don't live in the US just
take it on faith that many people in the
US would regard Boston and, and Omaha as
being fairly far apart geographically and
otherwise And what he did is he wrote each
of these residents of Omaha the following
letter. He said look here's the name and
address of this doctor who lives in
Boston. Okay, your job is to get this
letter to this doctor in Boston. Now,
you're not allowed to mail the letter
directly to the doctor, instead you need
to mail it to an intermediary, someone who
you know on a first name basis. So of
course if you knew the doctor on a first
name basis you could mail it straight to
them, but that was very unlikely. So you
know what people would do in Omaha is,
they'd say, well. I don't know any
doctors, or I don't know anyone in Boston,
but at least I know somebody in
Pittsburgh, and at least that's closer to
Boston than Omaha, that's further eastward
Or maybe someone would say, well I don't
really know anyone at E ast coast, but at
least I do know some doctors here in Omaha
And so they give the letter to somebody
depending on a first name basis in Omaha
And then, the situation would repeat.
Whoever got the letter, again they'd be
given the same instructions: If you know
this doctor in Boston on a first name
basis, send him the letter. Otherwise,
pass the letter on to somebody who seems
more likely closer to them then you are
Now of course many of these letters never
reached their destination but shocking at
least to me is that a lot of them did. So
something like 25 percent at least of the
letters that they started with made it all
the way to Boston. Which I think says
something about people in the late sixties
just having more free time on their hands
than they do in the early 21th century And
I find this hard to imagine but it's a
fact. So you had dozens and dozens of
letters reaching this doctor in Boston.
And they were able to trace exactly which
path of individuals the letter went along
before it eventually reached this doctor
in Boston And so then what they did is
they looked at the distribution of chain
links. So how many intermediaries were
required to get from some random person in
Omaha to this doctor in Boston? Some were
as few as two. Some were as big as nine
But the average number of hops, the
average number of intermediaries was in
the range of five and one-half or six And
so this is what has given rise to the
colloquialism even the name of a popular
play the six degrees of separation. So
that's the origin myth. That's where this
phrase comes from. These sorts of
experiments with physical letters But now,
in network science, the small world
property is meant to be a network, which,
on the one hand, is richly connected But
also, in some sense, there are enough cues
about which links are likely to get closer
to some target. So that if you need to
route information from point a, to point
b. Not only is there a short path But if
you, in some sense, follow your nose, then
you'll actually exhibit a short path. So
in some sense, routing information is easy
in small world networks And this is
exactly the property that [inaudible]
identified with [inaudible] SCC, very rich
with short paths and if you want to get
from point A to point B just follow your
nose and you'll do great. You don't need a
very sophisticated [inaudible] path
algorithm to find a short path. Some of
you may have heard of Stanley Migrim, not
for this small world experiment but for
another famous, or maybe infamous, he did
earlier in the Sixties which consisted
into tricking volunteers into thinking
they were subjecting other human beings to
massive doses of electric shocks. So that
wound up, you know, ended up causing a
rewrite to certain standards of ethics in
experimental psychology. You don't hear
about that so much when people are talking
about networks, but that's another reason
why Migram's work is well known And just
as a point of contrast, outside of this
[inaudible] opponent which has this rich
small world structure very poor
conductivity in other parts of the web
graph. So there's a lot of cool research
going on these days about the study of
information networks like, like the web
graph. So they want you to get the
impression that the entire interaction
between algorithms and thinking about
information networks is just being as one
strong component competition in 2000. Of
course, there is all kind of interactions,
I have just singled one out that was easy
to explain and also highly influential and
interesting back in the day But you know
these days; lots of stuffs are going on.
People are thinking about information
networks kind of different ways and of
course algorithms and almost everything
explained a very fundamental law. So let
me just dash off to a few examples. I'm
Whetting your appetite, maybe you want to
go explore this topic in greater depth
outside of this course. So one super
interesting question is, rather than
looking at a static snapshot of the web
Like we were doing so far in this video
Alright, the web is changing all the time.
New pages are getting created, new links
are getting created and destroyed and so
on And How does this evolution proceed?
Can we have a mathematical model which
faithfully reproduces the most important
first order properties of this
evolutionary process? So the second issue
is to not think not just about the
dynamics of the graph itself, but the
dynamics of information that gets carried
by the graph. And you could ask this both
about the web graph and about other social
networks like say, Facebook or Twitter.
Another really important topic which
there's been a lot of work on, but we
still don't fully understand by any means,
is getting at the finer grain structure in
networks, including the web graph And
particularly what we really like to do is
that full proof method for identifying
communities. So groups of notes is going
to be web pages and web graph for
individuals and social network which we
should think of as grouped together. We
discussed this when we talked about
applications of cuts. One motivation of
cuts is to identify communities
everything. Communities has been
relatively densely connected inside and
sparsely connected outside And that's just
a, and that's just baby step, really we
need much better techniques for both
defining and computing communities in
these kind of networks. So I think these
questions are super interesting, both from
a mathematical/technical level, but also
they're very timely. Answering them really
helps us understand our world better.
Unfortunately these are gonna be well
outside the course of just the bread and
better design analysis of algorithms,
which is what the, on task with covering
here. But I will leave you with a
reference of a book that I recommend if
you want to read more about these topics
Namely the, quite recent book by David
Easley and Jon Kleinberg, called
"Networks, Crowds, and Markets."