So, what are we going to do next is to
take our affiliation graph model and
simplify into something
that we will call BIGCLAM,
which will allow us to detect
communities in large networks.
So, let's see how we do this.
So the previous case, what was kind
of problematic, in terms of trying to
fit the model to the data, is that we had
this big, bulky, bipartite structure that,
that we have to fit and basically
search over this affiliation graph.
So what we will do now is basically
relax the, the model a bit.
And the idea now is to say,
rather than, than for
every node to have a 0-1
type of membership,
in a sense that I can either be a member
of a given community or a non-member.
Now we want to actually model the strands
of every node community membership.
So the idea will be that we will have this
non-negative strand of every node being
a member of a given community.
Of course, if a strand of membership is 0,
this means a node is not
member of the community.
And if the strand of a membership is very
high, this means that the node is very,
kind of, active part or
an active member of a given community.
The way we will think of these strands,
we will, we will label them as Fu comma A,
where u is the name of the node and
A is the name of the community.
So we will call this membership strands F.
And they are non-negative values.
So basically, 0 means no membership and
anything greater than 0 means
that you are a member of a given
community, to a given degree.
So now the question is,
how do we think about links of
the network arise from this model?
And the way we will think about
this is very similar to what we
have been doing so far.
So we will say that each community
A links nodes independently.
And the probability that two nodes
are linked due to a given community,
meaning them being a member
of a given community,
is simply 1 minus the exponential
of minus product of
the membership strands of the two,
of the two nodes in that given community.
So the idea is very simple, right?
If we are are both members to that
community to a very high degree,
then our product will be large.
We have a minus sign here,
so exponential of a very large negative
number is something very small.
So the communi,
the total probability will be high.
For example, what is also a nice property
of the product is if node v is, for
example, not a member of a given
community and node u is a member,
is a member of that community,
then it will be 0 times something else, so
the whole thing will be 0.
That is also nice.
And then, another thing is,
if we have nodes that are members to
a given community to varying degrees,
we will take the product of the two
corresponding strands to compute
the overall linking probability.
So now, this is the idea of,
of having a linking probability for
nodes u and v,
belonging to a single community A.
So now, what happens if nodes
share multiple communities?
In order to achieve this,
we have to first define what we
will call the community
membership strength matrix F.
So, here is my matrix F, and let me
tell you what, what its.structure is.
So this matrix F has
the number of columns,
which is the number of
communities in our network, and
the number of rows of this matrix equals
to the number of nodes of the network.
And every entry of this matrix tells
us to what degree does a given node,
in a given row x, belong to a given
community in a given column, okay?
So the, what we can then do is, if you
think of a single row basically being
a description of what, of what the,
what are the communities a given node is
member of and to what strength is, is
given node, the member of that community.
We can basically think that this
completely specifies the community
structure of our network, right?
For every node,
we know what communities it belongs to.
And we can think now of every,
every row in this case
as a simple vector of community
membership strands for that node.
So as we have discussed,
now the question is,
how do we compute the probability
of our connection?
The way we compute the probability of
a connection is simply probability that is
proportional to the product of
the strengths of the two nodes.
So we, we have already seen the equation.
It is simply probability of our
pair of nodes being connected,
due to our given community A, to be 1
minus the exponential of minus the product
of the strands of the committee membership
of nodes u and v to a given community A.
So now that we know how likely is a pair
of nodes being connected due to our
membership to a given community A,
now we want to generalize this and
say, what if a pair of nodes has
multiple communities in common?
And we will use the same approach as
we did with affiliation graph model,
we'll say the probability of a pair
of nodes being connected is propor,
is proportional to the,
to the idea that at least one of
the communities they have
in common created an edge.
So, here it is, the probability of pair of
nodes being connected is simply 1 minus
the product over the communities, 1 minus
the probability of them being connected,
given that they share a membership
in a given community.
So this, this formula simply says,
what's the probability that at least one
of the communities creates a connection.
So, what we want to do now is think
about this formula a bit more and
actually try to simplify it.
So let me show you how we
can simplify it further.
What we have so far is to say, given
community A, here is the probability that
a pair of nodes is connected,
due to the membership to that community.
Then we said, we said, right?
The probability of nodes being connected
in the network is proportionate to
the probability that at least one
common community that they have in co,
that a pair of nodes has in
common links that given pair.
So, I have the expression
from the previous slide,
now let's try to simplify things a bit,
right?
So, the first thing I can do when I
have this value P sub c, I go and, and
insert and insert our expression for
the probability of an edge.
And now, what I notice is that the first
line 1 and the second 1 will cancel out,
so all I will be left with is a product or
the expo, exponentials and
then a product of
the membership strengths.
A product of the exponentials is some
of the things in the exponent, so
I can, I can simplify this simply to say
this is 1 minus exponential function.
And then sum over the communities,
product of the corresponding strands, and
then I have this minus here.
Now, what we notice is that the, the,
the summation that we have here
is simply a dot product, right?
It's a, we are going and
multiplying the components of the two
memberships' transvectors together.
So to write this more compactly,
here's the expression.
We say that the probability of node
u linking to node v is simply 1 minus
the exponential of minus, and
then it's a dot product of factor that,
basically a row, for the node u and
a row for node v, right?
Where these rows basically tell us how,
to what degree is a given node
member of a given community.
So, to give you an example,
here I can think of my ma, my matrix F,
where I have the factor vectors of the
community strengths membership vectors for
the three nodes.
So now I can start asking,
what is the probability of a given
pair of nodes being connected?
So, for example, I can compute,
given the formula above,
the probability of nodes u and
v being connected, that is very simple.
It is 1 minus the, the e to the,
raised to the power of minus 0.16.
If I do that, the value is 0.14, so this
is for nodes u and v being connected here.
What we see is that they, they have
the only reason they, they can be
connected is because they share
the membership of the fourth community.
I can, for example, ask,
what is the probability of nodes u and
w being connected?
Here is node u, here is node w.
What we notice is that they
have one community in common,
the same as in first case.
But now, they both are very strong, have
very strong membership to that community.
So the overall linking probability that
we compute out of this is very high.
But for example, nodes v and
w have the linking probability of 0.
Why is that?
Is because v and
w have no common communities, right?
In the first case,
one is a member of the first community and
the second node is not, and
so on and so forth, right?
So, what do we,
what do we see from this is that kind of
the model has exactly
the components we would like.
If nodes are members to a given
community with very high strength,
the probability is large.
If the strength is low, the linking
probability is correspondingly small.