Our general plan of
attack today will be to
think about generative models for
networks.
So our goal will be the following.
Actually, first,
I will start tell, talk, telling you
about, how do we generate networks, right?
So if I have some model,
how can I generate a network, a graph,
from this model?
Right?
Where, you know,
nodes, nodes represent some entities or
people and edges represent let's
say friendships and so on.
And our goal in some sense
will be that we will want to
define a model that is able to
generate realistic looking graphs.
And then in the second step
what we will do is to say,
actually, given a real graph, imagine,
given, like, a Facebook graph.
What we will want to do is we
will want to go and fit, or
find a generative model that
has generated our graph.
And by doing so we will go and
detect communities.
So this is the overall idea for today.
Our next thing now is to actually say,
what is a good generative models for,
model for networks.
So, let me tell you how
to think about this.
All right?
Our goal is to say we want to define
a generative model for network.
And in some sense, our model will have
a set of parameters, right, that we will,
kind of, later want to estimate given,
given our real data.
And by estimating those parameters,
we will in some sense implicitly
actually detect these social
communities that I was talking about.
So the question is, given a set of nodes,
how do communities generate the edges
of the underlying social network?
So we need kind of define the way
the edges arise given a set of notes.
The model we will be
talking about is called
the community-affiliation graph model.
And the way this works is the following.
All right?
So our goal is,
we want to define the model
that will generate a network.
So the model has specified the following.
We have a set of nodes V, these are the
nodes of my underlying social network.
Imagine here they are.
And then I have also another set
of nodes that I will talk, and
I will call them communities.
I call this set C, okay.
And then what I will do is the following,
I will say that every node can be
a member of any of the communities.
So in some sense I will have these
edges here that are basically community
memberships, right.
So what this will tell me is that
the blue node is member of community A,
green nodes are members of community B,
and the four red nodes,
they belong both to community A and
to community C.
So this is now my
specification of my model.
Now what I want to do is,
given this model,
I will want to generate the network.
So the affiliation graph model is
a generative model for networks,
and the model can be specified as with,
kind of, four types of parameters.
I need to know the set
of nodes in the network.
This is the set V.
I need to know the set of communities.
That is the set C.
I need to know the set of edges,
the membership edges between nodes and
the corresponding communities.
And then what we will also have
is every community has a single
parameter associated with it, and
we call this parameter p sub A, p sub B,
and in general, there is a set of these
parameters that we will call p sub C.
Okay?
So the, the model above is
uniquely defined by this tuple of
four four different sets.
Now kind of what we want
to do next is to specify,
how does this model generate the network,
right?
We need to define, what is the process
from going from this affiliation network
here on the left to actually the edges
of the underlying social network.
For example, one thing we already know is
that, that the set V, the number of nodes
at the bottom here, is exactly the number
of nodes of our social network.
What we need to do now is
define how are these edges of
the social network created or
how do they arise out of our model.
So, the way we do this, is to think,
to think about the affiliation
graph modeling the following way.
We can think that every of
the communities that a pair of
nodes shares generates an edge
with some probability.
So in some sense the idea is,
if we both belong to soccer community,
and we also both go, attend the same
university, then because we
are playing soccer together, that has
some probability of us being friends.
And also because we, I don't know,
attend the same university,
that has us also some probability for
us becoming friends.
So the idea is that each of such social
communities in some sense creates
an opportunity for a pair of nodes to
meet and create a friendship connection.
So the idea is that every community,
let's call this community A, has a,
has a single parameter p sub A, and
this parameter tells us with, how likely,
with what probability does a pair of
nodes connect if they both belong
to this community A, okay?
So now we can ask, okay, given a pair
of nodes and all the communities they
belong to, how likely is this pair
of nodes to connect with each other.
And the way we will do this is
we will say they connect if at
least one of the communities they
have in common creates an edge.
And the formula that describes this,
I have it down here.
All we are saying is
the probability that node u and v
are connected is 1 minus the product over
all the communities they have in common.
1 minus the probability of each given
community creating a connection.
The way to think about this
formula is the following, right.
1 minus p sub C basically tells us,
what is the probability that they,
that the pair of nodes does not connect,
because they have a community in common.
So the product over these
probabilities tells us,
what is the probability that all,
all of the communities they,
they have in common, all of these said,
no, I don't want a connection.
So 1 minus that is the probability
that at least one of
the communities created a connection.
So one way to think about this
expression here is that in
some sense this is an OR function.
A pair of nodes will
connect if at least one of
the communities they have in common
actually creates, creates an edge.
What is also interesting here
is that we already see that
this is an increasing function in
the number of common communities.
Why does it increase, is because
the more communities we have in common,
the more numbers are in this product.
Each of the elements of this product
is a number smaller than 1, so
the more numbers that are smaller than
1 we multiply together, the smaller
the total product, so 1 minus a small
number is, is a bigger number, right?
So this means that the more communities
a pair of nodes has in common,
the more likely they will
be to link with each other.
So now we specify basically how to
create edges of our network, right.
The way we create edges here is that for
every pair of nodes, we ask, what
are the communities you have in common?
And we apply this formula down here and
say that this way we compute the total
probability of a connection, flip a coin,
and if the coin says yes,
we create a connection, right?
The nodes that have multiple
communities in common,
they will basically get multiple chances,
in some sense, to create an edge.
So what is now, what we have done so
far is that we have our affiliation
graph model of networks.
We specify the model.
So here is a different
specification of the model,
where we have three communities.
Each of these communities has
a different linking parameter.
And given such model,
we can now generate a network.
Right.
So, from the model,
we can go to the network.
Here's a picture of the network that
would arise from the model above.
What we nicely see here is that
each of these communities,
we can think of it as a tile.
We see that, for example, the red
nodes here in the overlap of all three
communities, they are very well connected.
We see that, for example, the pink nodes
also connect heavily with each other.
And then we see that the other parts
of the communities where, kind of,
there is no overlaps,
they are less well connected.
But the model that we specified here is
able to generate us the network, below.
So what is good about
the affiliation graph model and
the way I described the model so
far is that this model is able to
express a variety of different
structures of networks.
So for example, if I want communities,
social communities or clusters that don't
overlap with each other, this is how I
could really present this using our model.
Right, so the idea is, I have
a community A, I have a community B,
and imagine I have maybe a few
edges across these two communities.
The way I would represent this in terms of
our model, the affiliation graph model,
is basically to say, I have one community
node A, I have another community node B,
and then a set of nodes is a member of A,
and
the other set of nodes is a member of B.
Of course, given the way I defined the
formula on the previous slide, the idea
is, if a pair of nodes has no community
in common, then they link with a small
probability epsilon, so that we still get
a few edges crossing the two communities.
So this is the idea for
how to model non-overlapping or
these kind of partition-based communities.
If you want, we already know how
to model overlapping communities.
The idea here is I, have communities A and
B, they overlap in this yellow area, so
how does the model, AGM model look like?
Here is the model.
Basically, the idea is that I have these
two yellow nodes that actually belong to
both communities,
to community A and community B.
And what's interesting, we can even,
like, think about nested or
hierarchically nested communities,
where we could have, you know, the mother
community B, that then has two smaller
communities A and C embedded in it.
The way we would model this using our
affiliation network model is to say, okay,
we have three communities,
the nodes at the bottom,
every node is a member of the community B.
But in some set,
subset of them is also a member of A,
and another subset is a member of C.
So this way, we nicely model
the hierarchy structure of the network.
So basically the bottom line is that this
model for generating networks is very
flexible, and if somebody gives us
the structure of this bipartite graph,
this affiliation network below,
we are able to generate the network.
Of course, what we will do next is
actually turn the problem around.
We will say,
given a network we want to find the model.
So this'll be the topic
of our next lecture.