In the last part of the lecture,
I wanna now talk about the third generative model,
which we call Kronecker graphs, uh, generative model.
And this is a very different, uh,
model because it will be kind of much more, uh, mathematical,
in some sense, much less interpretable,
but it allows us to generate very rich, uh, networks.
So, uh, let me explain what the Kronecker graph model is.
So the way we will think about this is we'll think
about it from the viewpoint of recursive graph generation, right?
Can we think of network structure recursively?
And in particular, can we generate networks that have this type of self-similar,
uh, structure where, you know,
the object is self-similar if- uh, um,
if the object it's- is- is similar to a part of itself,
like, you know, the hole has the same shape as one of its parts.
Um, and the idea is that we would be able to then generate big graphs from small, uh,
building blocks, right, from- and in this way,
perhaps imitate different communities and growth of, uh, different communities.
And the Kronecker graphs will allow us to do this through this notion of
a Kronecker product that will allow us to
generate self-similar adjacency matrices, right?
So the idea will be that if- that if I start with some starting graph,
I somehow would recursively expand the starting graph,
uh, into bigger and bigger graphs.
So I wanna ge- have a small kind of generator,
small building block, and then I wanna
generate- use it to generate bigger and bigger graphs.
And the way this will work is, I will, uh,
take a small generator matrix like the one I have here,
let's call it K_1.
And then I'm going to, uh,
apply Kronecker product to- uh, to itself.
So I am going to do K_1,
Kronecker product K_1 to get now,
uh, a matrix, uh, K_2.
And then, you know, I can keep multiplying,
and I will get this very nice self-similar structure.
Uh, now, let's say, you know,
that has size 81 by 81.
And just notice that K_1 has this,
uh, pattern of, you know, um,
uh, 1s kind of along the diagonal band and 0s,
uh, off the diagonal.
And notice how now this adjacency matrix also has same structure, right?
I have this block of 0s,
and then I have this block of 1s,
but each of these blocks is similar, has 0s,
uh, of the diagonal and kind of has non-0s on the diagonal.
And then each of these blocks is again similar to the original block.
So that's kind of why these Kronecker graphs,
uh, uh, model will allow us to do.
So now, how do we define it?
How do I get what I just showed you on the previous slide?
We are going to define the Kronecker product of two matrices A and B the following way.
So the idea is, if I have two matrices, A and
B and I Kronecker multiply them, then basically,
the way to think of this is that I take the matrix B,
I put it into every cell of A and multiply with the entry in that cell.
So this means I can take two matrices,
uh, A and B, that have different sizes,
and the Kronecker product of them,
the size of the Kronecker product will be the product of the sizes, right?
So if, uh, uh,
matrix A has n rows and, uh,
matrix B has k rows,
then the number of rows of the product will be n times k,
and the same for columns, right?
Then the- you- the way you see now,
the product is simply you take B and you put that entire matrix into
the every cell of matrix A and multiply with an entry,
uh, at the- that- uh, cell.
So now that we know what is a Kronecker product of, uh, general matrices,
we can define a Kronecker product of two graphs by simply as
a Kronecker product of the corresponding adjacency matrices, right?
So, uh, now that we have defined this,
um, this basically goes- goes here, right?
I have a Kronecker- I have,
uh, first, adjacency matrix,
now I do Kronecker product of this adjacency matrix with itself,
and I get this type of structure, right?
I have zero here because if I take K_1, put it here,
and multiply it by 0,
I get a three-by-three block of 0s.
While in these other parts,
I get simply a copy of K_1 because,
um, because I have a coefficient 1 here.
So basically, now I get a matrix of size 9-by-9,
uh, where I have two blocks of size 3-by-3 of 0s,
and the rest are simply copies of this, uh,
matrix K. And now that I have a 9-by-9 matrix,
I could Kronecker multiply 9-by-9 with another 9-by-9 matrix,
and I would get, uh,
Kronecker, uh, matrix now on,
um, 81 nodes, so I have now a graph of- on- in 81 nodes.
So how are we going to define Kronecker graphs?
Kronecker graph is obtained by growing- uh,
by a growing seq- sequence of graphs by
iterating Kronecker product over this initiator matrix K_1.
So if I wanna get the Kth Kronecker graph K,
I'll simply take my initiar- initiator matrix K- K_1,
and I'm going to Kronecker multiply it with itself, uh, m times.
So basically, I'm taking the nth Kronecker power of the initiator matrix,
uh, to get the- to get the final graph.
Um, and of course,
and nobody says you have to take
one initiator matrix and just power it with itself m times.
You would have different-ish initiator matrices and multiply them to get a bigger graph.
So there's a lot of flexibility here.
To give you an example, uh,
here is an initiator matrix on four nodes,
here is the corresponding graph,
here is the adjacency matrix.
Uh, notice basically, uh,
we have self-loops, uh,
on the diagonal and then kind of,
uh, first row, first column,
uh, is basically the- the star node linking to other satellite nodes.
If now I generate, uh,
a Kronecker graph with this initiator here as the adjacency matrix,
and again, notice the self-similarity pattern.
Uh, here's a different, um, uh, uh,
initiator matrix with the corresponding adjacency matrix, right?
Again, I have this node,
uh, that links to all other nodes,
but then there is a triangle, uh,
here as well, um,
denoted in this part.
And now, notice as I create a Kronecker graph,
I get the same self-similar structure, right?
I get basically band of non-0s.
I have these two elements that are 0, corresponds to this area here.
I have this- this part corresponds to this part here, right?
So you see how I get
this recursive self-similar structure where basically this initiator matrix is- uh,
its structure is retained at the different, uh,
levels, and this is how we define the Kronecker graph.
Um, so far, we have defined Kronecker graphs as deterministic, right?
We started with a 0,
1 adjacency matrix and we generated a bigger adjacency matrix.
So what we wanna do next,
is we wanna make, uh,
these gra- these Kronecker graphs stochastic.
We wanna make it so that it generates random graphs.
And the way we generate random graphs with Kronecker graphs is that
rather than thinking of the initiator matrix as a- as a little,
uh, graph, as a little, uh, 0,
1 type matrix, we are going to think of it as a probability matrix.
So basically, rather than having K_1,
we are now going to have Theta 1.
And rather than ha- K had either an edge or no edge,
now, we will say that every edge has a probability between 0 and 1.
So theta is now a matrix of probabilities.
Then we are going to take this Theta 1,
and we are going to apply Kronecker power to it.
We are going to Kronecker power it with itself to get the kth power.
And then now that we have this probabilistic adjacency matrix k,
we are going to sample edges from it at random
according to the probabilities defined by this,
uh, in this- uh, in this matrix.
So let me basically give you, uh, um,
um, a picture that will explain what I mean, right?
So the idea is I started with some initiator matrix,
the entries have to be between 0 and 1,
and they don't have to sum to 1,
I Kronecker multiply this initiator matrix to get a bigger,
uh, probabilistic adjacency matrix.
Now, every cell here can be interpreted as a probability of an edge.
So in order to generate the graph,
I now simply traverse this matrix and flip a coin where, uh,
every entry tells me what is the bias of that coin,
and if the coin says, uh, yes,
if it lands on tail- uh, sorry,
on head, then we actually create a graph.
We- we create an edge in the graph,
and we then call this- this is now an instance sampled from this,
uh, probabilistic, uh, adjacency matrix.
Um, right. So the idea is once you have this probabilistic, uh, matrix,
you simply go and flip the coins according to the biases, um,
that are encoded in the values of the cells and this will give you a, uh, a graph.
It will give you, uh,
now an instance of a Kronecker graph sampled from this,
uh, stochastic Kronecker graph.
Uh, this is great because now we can generate graphs, uh, stochastically,
but all having kind of similar structure,
all being generated from the initia- the same initial, uh, probability matrix.
Uh, what is the problem?
The problem is that we have to flip all these coins.
And if the graph has size n,
which means this matrix has size n by n,
then we need to flip order n square, uh, coins.
Uh, and that's far too many coins to flip if I
wanna generate a million node graph because then I need to flip,
a million squared, uh, nodes.
So it will be- I have to flip 10 to the 12, uh,
coins, or if I want to generate a billion node graph, which is, you know,
nothing too large, then I would have to flip,
uh, 10 to the 18 different coins,
um, and that's unfeasible in practice.
So let me now tell you how to do this faster, uh,
using what is called a ball-dropping, uh,
or an edge-dropping mechanism, uh, and it's quite cool.
So here is how we are going to generate Kronecker graphs, uh, faster.
So think that you had this 2-by-2, um,
initiator- probabilistic initiator matrix that has, you know,
entries a, b, c, and d. Now,
if you Kronecker multiply this with itself,
the Kronecker product matrix will look like this, right?
The first entry will be a times a,
then it would be a times b,
b times a, b times b,
a times c, and so on. All right?
So that's one way to look at it,
is basically let- first,
you would generate all the cells and then you can flip the coins.
But what you can also notice is that we have this kind of hierarchical structure, right?
I have a, b, c, and d,
and then each of these four- four, uh,
quadrants has further a,
b, c, d in there, right?
So the way you can now think of this is is a two-level structure.
And the way you can say what is the probability of a- of a given edge,
it simply, um, you can fli- you can basically, uh,
separate it out as a set,
almost like as a diving,
dropping into the underlying adjacency matrix,
where at every stage you have to decide which of
the four quadrants do you wanna dive into.
So let me give you an example.
If this is my final, uh, you know,
this is my final adjacency matrix size I'd like to create,
so this would be number of nodes is,
uh, whatever is the number of rows and columns here,
then the way I can think of it is I can split this into four quadrants and I can say,
a-ha, you know a fraction of times I'm going to go into this part of the network,
b fraction of times I'm going to go here, c,
and d. And then basically you can pick again, uh, um,
uh, according to these values, a,
b, c, and d, one of these four quadrants.
And now that you have picked it,
you now then say, a-ha,
I- I- I have now picked this, uh,
this quadrant, let me again split it into four parts.
And again, let me pick which of
these four different subparts do I want to dive into and you would pick one of them.
And now you are still not all the way down at- at the bottom of the matrix,
you still have, um, um,
uh, to choose which cell you go to.
So again, you split this into four,
and again decide which of these four,
uh, to pick, right?
So, uh, what this means is that basically, rather than, uh,
flipping these, uh, coins kind of row by row,
you start at the- at the top,
and then you- you descend into one of
the four quadrants with probability proportional to a,
b, c, and d and you pick one of them and move into that part.
And now you say, a-ha, I will again,
I have four ways to go to and pick one of the four,
uh, ways at random and you'll move to the one part.
And then again, you say, Aha,
now I'm here, I wanna go deeper.
And you keep descending until you hit, uh, the, uh,
individual cell, and this is when you,
uh, when you stop and you put an edge.
Um, this means that you are going to land in a given, um,
in a given cell exactly with the probability,
um, uh, according to that cell.
The only difference is that you may get a couple of edges colliding, right?
You may land to the same cell multiple times.
If that happens, just ignore it,
uh, and try again.
And this gives you now a very fast way to generate a- a Kronecker graph, right?
So, uh, basically, this, uh,
edge-dropping or ball-dropping mechanism basically says,
um, take the initia- initial, uh, matrix,
whatever are the entries, uh,
normalize them and then keep dropping in, um,
in- keep descending in until you hit an individual cell and put an edge there, right?
Put a value 1 there,
and this would mean that you have connected nodes,
uh, i and j that are in a column,
uh, in the row i and column j.
And if you do this, what is interesting is that,
for example, with a very simple, uh,
adjacent parameter matrix only four values,
you can actually generate the graphs,
uh, that correspond to real graphs quite well.
Here is for example, the- this is now a directed graph in-degree, out-degree,
clustering coefficient, uh, diameter which is number of nodes,
uh, at a given distance.
Uh, these are some other properties that people care about.
And you can notice how Kronecker graphs in green and the real graph match really well,
and all you have to do is decide on these four different parameters, right?
Four different parameter values.
So basically with just four parameters,
we are able to generate, uh,
a realistic graphs using, um, Kronecker graphs.
Here the network we are trying to mimic has 75,000 nodes and,
uh, uh, more than half a million, uh, edges.
Uh, so the cool thing is now we are also able to model
degree distribution class- clustering as well as, uh,
shortest path, uh, di- distribution,
as well as some other properties with just four free, uh, parameters.
Here are the, you know,
the numbers of those parameters.
If you start with this initiator matrix,
you can basically generate this social network on 76,000 nodes and half a million edges.
So, uh, to conclude the lecture for today, uh,
the summary, so today we looked at these traditional generative models for graphs.
First, we discussed about, um,
what metrics do we use to characterize the graph.
And we talked about degree distribution,
clustering coefficient, um, the giant connected component,
as well as shortest path-length.
We started with the simplest possible generative model
called Erdos-Renyi random graph model,
um, and we- we saw that it generates shortest path-lengths.
Realistically, that it gives us connected graphs,
but it doesn't generate clustering coefficient.
So we then, uh,
talked about the small-world, uh, graph generator,
and we talked about how you only need a couple of
random shortcut edges that bring down the diameter but- but keeps the clustering high.
So this is what was in the- the significance of the small-world model.
And then we looked at,
um, at the different model called, uh, Kronecker graphs.
That's kind of more mathematical and, uh,
is defined as based on the Kronecker product of graph adjacency matrices.
We then defined the stochastic Kronecker graph, uh,
where the adjacency matrix is stochastic and we can then generate multiple instances,
uh, from the stochastic, uh, matrix.
Um, we talked and then- then last about this ball-dropping, uh,
mechanism that allows us to generate Kronecker graphs, uh, quick, um,
in a fast and efficient way so we can generate graphs with billions of nodes,
uh, without any problem.
So, um, with this, uh,
this finishes the lecture for today.
What we are going to talk about, uh,
next week is about deep generative models for networks, right?
So while today the models were kind of mechanistic with a lot of,
uh, insight from the network generative processes that happen in real world,
uh, the- in- on Tuesday,
we are going to talk about deep generative models where basically we will
say let's just formulate this as an- as a machine learning problem,
as a kind of complex, uh, prediction problem,
and all we care about is to generate a
realistic structure and we don't care so much about, uh,
whether, uh, you know,
what is the true underlying,
let's say real-world, uh, generative process.
So we learn how to generate graphs,
uh, from, uh, raw data.