So next we are going to talk about spectral graph graph partitioning.
And we will split the,
discussion of spectral graph partitioning into two parts.
First we will talk about, the problem and
we will define the graph Laplacian matrix, and then in the next, second part.
We will talk about how to do the partitioning.
So let's first define what is our goal and what we want to do.
Right? What we would like to
do is we would like to define clusters or communities in networks.
And the way we would like to do this is basically we would like to,
in the simplest way, split the graph into two pieces.
And we would like to split the graph into two pieces in such a way that each of
the two pieces has lots of connections between the members of each piece, and
then a few connections crossing the two pieces.
Right? And here I give you an example of
this where I show a simple example of a network with kind of two clusters and
a small set of edges that crosses the two clusters.
And the same view of the same kind of data but
now through our adjacency matrix, right?
So this is now on the right hand side called the graph adjacency matrix.
Where rows and columns of this matrix represent nodes, and then an entry i,
j is either filled in or not.
And if it's filled in,
this means that a particular node i links to a particular node j.
And if the entry that is empty, that means the nodes don't link to each other.
[COUGH] And in the presence of Clusters, what we see is that
this adjacency matrix can be re-ordered in such a way that we have two clusters where
there is lots of connections between the members of the cluster.
Here's another one.
Lots of connections.
And then there are very few connections between the two
clusters in the off diagonal parts.
Right? So now the question is how do
we identify such structure?
How do we split the graph into the two pieces.
The way we will think about this is we will,
we will define the problem as we want to partition the graph into two
pieces such that the resulting pieces have low conductance, right?
We have already defined the notion of conductance which intuitively can be
thought of as for a given set of nodes we want to ask how many edges
are pointing outside this set of nodes and how many edges are inside the set.
Right? So in this particular case one would
bisection of the, of the graph here would be the line the blue line here, okay?
So now the question is, how do we go and
efficiently find such a good partition, right?
So I give you a graph and
I ask you what is the best partition of the graph into, into two pieces such that
the conductance of each of the piece is as small as possible.
Which means we find good communities or good clusters.
So we have already defined the notion of graph adjacency matrix right?
We said we will, we will denote A as the graph adjacency matrix and
this matrix A will be a binary matrix with values either zero or
one where a value of one means that the particular pair of nodes i and
j are connected and an entry of value zero means that they are not connected.
So that's the first thing we will define.
The second thing we will define is notion of a vector x.
So let's think of a vector x is a long of vector of real valued entries.
Then the length of the vector is exactly the,
the same as the number of nodes in the network.
So the way we can now think of this network is that basically every entry of,
of this vector is a label for a value of a node in the network, right?
So basically this means that the x,
j basically corresponds to the value of node j in our graph.
So now that we have defined a matrix and we have defined the vector we can
start asking about what is this kind of semantics or intuition.
What does it mean to take our matrix A, which is now a simple binary matrix, and
multiply it with this vector x?
And the question is what happens when I take the matrix and
multiply it with our vector.
Right, so here I have our matrix A,
I have our vector x and imagine that A times x equals y.
So the question is, how should I think about the entries of y?
The way that we do the multiplication of a vector with a matrix, right, very simple.
I basically go for every row,
multiply it with my vector x, and this gives me a particular value y.
Right, so if I write this out, I basically say that y, i, right, the ith entry of y,
is simply a product over all the columns of A, where I take the ith row,
and then I multiply with, this with the entries of x going down by j.
Right, so if you think about this, what this is basically happening is to say that
a particular node i, it's labels are simply the sum of the labels,
of the nodes x that are connected to it, right?
so basically here a, i,
j will be one if the i links to j and will be zero otherwise, right?
So we can equivalently rewrite this summation as simply the prod,
the summation over the address i, j where i is the node of interest, right?
This is the y, i, and the j is the node j that points to y.
So now basically what this means.
Is what we have just learned is that basically entry y,
i is simply a sum of labels x, j of all of the neighbors of y.
Right? So basically when we take a matrix A and
multiply it with x all we are doing is basically for
every node, every node is asking what are the labels of my neighbors?
Let me sum up these neighbors and that's my new value.
Right? So this is the meaning of A times x.
So now that we have, understood what is the meaning of A times x,
we can start asking about what happens if we are star-,
if we are, thinking about this matrix in a bit different way.
In a, and in particular, let's think about the eigen value problem, right?
We have already talked about eigenvalues and eigenvectors and
here is a definition of an eigenvalue problem, right?
So basically we are saying that eigenvector and
the corresponding eigenvalue.
The solution to the equation of A times x equals lambda x, right?
So eigenvectors are these interesting vectors that when I
multiply them with matrix A, they basically survive.
I get the same vector out, it just may be, scaled by, by the scalar lambda.
So, now what is the spectral graph theory?
Spectral graph theory is really asking about what is the spectrum of
a given matrix representation of our graph G, and what do we define as spectrum?
Spectrum is simply a set of eigenvectors ordered by their magnitude and
their corresponding eigenvalues.
Right? So, basically what we are interested in
now is to ask, if I have our adjacency matrix A of a graph.
I compute the Eigenvectors and Eigenvalues of this matrix.
I label Eigenvalues as lambda's.
Eigenvectors as x's.
The question is what do these Eigenvectors and
Eigenvalues, what do they tell me about the graph?
So let's all start thinking about what do Eigen, Eigenvectors and
the corresponding Eigenvalues, what do they tell us about the graph?