So, today we will start
with with a new topic and
we will start looking at
the Analysis of Large Graphs.
And in particular, we will talk
about Link Analysis and PageRank.
So here is the idea.
So, so far,
this is how the class fits together and
we are starting with a new topic with
a new set of data that is the Graph data.
And in this module of the class.
We will look at link analysis methods,
like PageRank and SimRank.
We will look at Community Detection with,
where the idea is that we want to find
clusters of nodes in the network.
And then we will also look at
Spam Detection, where the idea is that we
want to identify nodes that are spam,
spam nodes in the graph.
So those are the three modules for
the Graph data section.
If we think about graphs,
graph, graphs are everywhere.
In a sense that for example,
social networks Facebook Twitter and
things like that.
Can very naturally be
represented as graphs.
Graphs in a sense of as a set of nodes and
a set of edges or connections or
intersections between them.
Another set of data points that
also can be represented as
graphs are social media networks.
For example here, in this graph.
What, what I'm showing you is is
an illustration of the structure of
the United States blogosphere around
the Presidential Election in 2004.
And what you see is basically
these two clumps in this network.
These two communities and
they basically correspond to the two
political parties in
the United States system.
And you see how this class,
the nodes in one cluster then link
into the other cluster and there is some
number of cross-linking between the two.
So there is some amount of
polarization in a sense.
Another word,
another set of data that can actually be
represented as networks
are the networks of information.
So for example, in this, in this case,
what we are seeing here
is a map of science.
So here every node is a, is a different
journal and or a different conference.
And now the edges between these
journals are publication menus I mean,
that one journal is
citing the other journal.
So based on this citation
network between journals,
we can basically visualize how
different disciplines of science and
sub fields of science,
how they're relating to each other.
Of course, internet is another case where
that can be studied as a, as a graph.
So here, we have computers or
routers talking to each other.
And again, this can be represented
as a dynamic network of nodes which
represent computers or routers.
And then let's say, physical links or
between, between these machines and
those are the edges of the network.
Of course, kind of the technological
networks are also the,
the oldest example of graphs
people have been studying.
So for example, the, the field of
graph theory goes, goes back to 1700s
when Euler posed this problem about
the seven bridges of, of Konigsberg where
the idea is that we want to cross at some
point and travel each bridge only once.
And the question is can that be done?
And this can be formulated as a,
as a graph problem.
And examples of other
technological networks, for
example are power grids, road networks
water distribution networks and so on.
And it's, it's important for us to
understand the structure of these networks
to detect failures to, to detect disease
outbreaks or contaminations and so on.
Another example of a big part of
kind of networks is, is the web.
Right.
So web itself,
can be represented as a graph.
And what we will do today,
we will kind of focus on the structure
of the web graph and we will
develop methods that allow us to learn
something about the, the pages on the web.
So the first question is how do
we represent web as a graph?
We will represent web as a directed graph.
So we now will graph nodes will be,
will correspond to web pages.
So every web page will be,
will be a node in this graph.
And now we will have directed
links between these web pages that
correspond to hyperlinks.
Right?
So if I have my example here,
I have a set of four web pages.
And now these web pages
contain hyperlinks.
So in this case, a particular,
a particular webpage points to another,
another page via a hyperlink.
So we can use now this hyperlink
relationships to create a network.
All right.
So here is a small example,
if I show you a bigger example.
You could, think of the university
website as a big giant graph of
web pages citing or referring to each
other via the use of hyperlinks.
Right.
So we
just represented the web as this network.
The question is how is the web organized?
The, the way people tried to
approach organizing the web was to
human naturally created by humans.
So for example, Yahoo back in 1996.
Their original idea was to take
all the web pages on the web and
manually categorize them
into a set of categories.
So for example here,
I have a screen shot of the web page and
you see that the top category was for
example arts.
There was business.
There was education.
And each of these categories
had further subcategories.
So the idea was to take every web page and
categorize it into,
into this giant hierarchy.
Of course, time showed that the web
was growing far, far to quickly so
this, this did not scale.
So the next way how to
organize the web and
how to kind of find things on
the web is the web search.
And this is what kind
of what we use today.
And what is interesting in terms of
the web search is that there is lit,
literature in particular the field
of information retrieval.
That covers the problem of how do we find
a document in a large set of documents.
Right?
So in our case of the web,
we can think of every
web page as a document.
The whole, the whole web is one
giant corpus of documents and
our goal is to find a relevant document
to a given query in this huge set.
However, traditionally the information
retrieval field was interested in finding
these documents in relatively small,
small collections of trusted documents.
So for example, like newspaper collections
or pap patent collections and so on.
However, the web is very different.
The, the difference is first,
that the web is huge.
And the second thing is the web is full
of untrusted documents, random things,
spam, unrelated things and so on.
So the,
the big question on the web is which,
which web pages on
the web should we trust?
Which web pages are kind of legitimate?
And which are,
which are fake and irrelevant?
And this is what we will
be looking at today.
Is how do we identify set of relevant or
trustworthy web page,
web pages in this huge web graph.
So, when you are doing the web search,
there are two that,
that there are two challenges.
Right?
So as I mentioned, the first challenge
is who do we trust on the web?
Right?
How do we know which are, which web pages
are legitimate and which web pages are,
for example, spam or
somehow fabricated on the web?
The idea here is that we will use
the structure of the link web graph
to understand these things.
So the idea is kind of that trust,
trustworthy web pages
will link to each other.
And we will build on this idea
to exploit it to be able to
identify the page rank algorithm.
And then, the other problem
that happens on the web is that
sometimes queries can be rather ambiguous.
For example, you can ask, what is
the best answer to a query newspaper?
And there is really kind of no,
no good answer to this query.
And the, the, the,
goal here if you want to identify
all the good newspapers on the web.
Is to again, look at the,
at the web structure of the of,
of the structure of the web graph in order
to identify the we, the set of pages.
Or a set of newspapers that
are linking to each other.
And again, get, get the result out
of the structure of the web graph.
So these are the two challenges we
will address in today's lecture.
The way we can address both of these
challenges is to basically realize that
the web as a graph has
very reach structure.
So one thing that we can do is we
can try to think of this problem
abstractly as a way to rank
nodes of forbidden graph.
So basically,
we would like to compute a score or
an importance score of every
node in this web graph.
And the idea is that some nodes
will collect lots of links, so
they will have high importance and
some other nodes will have a small number
of links or links from untrusted sources.
So they will have low importance.
So that's the,
that's the thing we want to compute.
So, in order to compute the importances
of the nodes in a graph.
There are several approaches to this.
Broadly, these approaches
are called link analysis.
Because you're analyzing
the links on the web graph to in,
to compute an important
score of a node in a graph.
So the b, the first approach we will
look at, it's called Page Rank.
And this is really the algorithm that was,
that was invented in that
behind the initial implementation
of the Google Search engine.
Then we will take a look at
also at another algorithm that
is called Hubs and Authorities.
Here the idea is that we
have two types of web pages.
In our web graph, we have the web
pages that are called Hubs.
And we have web pages that
are kind of called Authorities.
That are good authorities for
given topics.
And then, we will look at some
extensions of these algorithms.
First, in terms of topic-specific or what
is also called as Personalized Page Rank.
And we will also use these ideas and
apply them to web spam, spam detection.
Where basically spammers may want
to manipulate the structure of
the web graph in such a way to,
to make some web pages to,
to seem important even
though they are not.
So basically,
boost importance of some of the web pages.