In this last section on community finding,
I'd like to discuss how one actually goes
about discovering communities in networks.
We talked about how simply looking for
cliques or, a k course, etc.
How that can be a little bit arbitrary.
What if we had a criterion that said.
Once you've partitioned the nodes into
these groups, so the key word is for now,
is that we're partitioning, we're chopping
the network up.
That we can say that this is the optimal
way to chop the network up with respect to
some criterion.
And these would be the natural communities
that exist in the network.
The trick is just to, to find them.
One approach is hierarchical clustering,
where you compute some similarly between
the nodes and you,
To start with, each node is in its own
component and its own community.
And then you find the two nodes, for
example, that are most alike.
And this similarity could be things like,
how many neighbors do they have in common?
Or if you have a weighted network, how
often do they communicate with one
another?
Regardless you have some notion of these
two nodes are close.
They, they're similar.
And you start agglomerating in this way.
And there are, of course, some decisions
you have to make.
Do you pick the node that has the minimum
distance to a node in, in the existing
cluster?
Or do you look for the average similarity
being the highest etcetera, right?
So, so there are different options in
hierarchical clustering.
But one nice thing is that, as you're
aggregating up and up, you can, and
finally you have the whole network as in
the same component.
Or same community.
You can then decide at what level you
would like to cut.
And so, depending on how low you go, you
have very refined community structure or
very coarse community structure.
Now there is a very efficient and
successful implementation of this in
Pajek, and some other software.
To my knowledge, it's not implemented in
Gaffi,
And I've looked a little bit, at I-Graph
and Network X.
And of course, you know, these are things
that you can sort of implement yourself if
you are a programmer.
So, let's leave hierarchical clustering
for now.
It's definitely, an okay way to approach
finding communities and networks.
But it doesn't necessarily fulfill this
criterion of we have some.
Some single metric that we're trying to
optimize, right?
Hierarchical clustering is just more
organic.
We're going to keep lumping together,
nodes and group of nodes until, you know,
it's all lumped together.
And we're just going to somehow decide
where we want to, where we want it to
stop.
But we don't really have that stopping
criterion yet.
If we go back to the Zachary Karate Club,
I just wanted to illustrate what this
might look like in Pajek. So, if you
remember, this is the club that broke up.
And we just want to see what would a
community finding algorithm have predicted
happened, would happen.
Who will go where?
So, I had somehow managed to accidentally
delete the last part of this lecture.
So this is a little bit of a redo.
So, apologies for the disconnected flow.
Where I was at was.
Looking at hierarchical clustering in Piek
for Zachary's Karate Club.
That is, can we predict that these folks
are going to go one way, and the rest of
these folks are going to go another?
Before we do that, we're going to look at
the adjacency matrix in a pretty neat way.
What I've done is I've used Pajek to color
each.
Entry in the matrix where there's an edge
is black.
And you can see the way that the data was
originally entered already betrays some
structure.
However, it's not very clear how many
different communities there are.
If we were to randomly per, permute the
rows, we would get, I mean so this is the
same network, it's just that which vortex
has the label thirteen and is in the
thirteenth row, is different in this
matrix then it was in the previous one.
And here, we can see very little
structure, right.
This is a random permutation.
After we perform our hierarchical
clustering, we can re-permute the matrix,
such as, such that those nodes that are in
the same cluster are clo, are placed close
together, and now we can see clearly that
there are two distinct communities, each
with one or two very central individuals.
One other form of output is the
dendrogram, which tells us,
As you join nodes and, groups of nodes
together that are similar in this
hierarchical clustering process.
You can see which nodes are in the same
group.
And eventually, you end up with just two
groups, which then you can compare.
Are these individuals the ones who split
off?
This next way of clustering the network,
was proposed by Mark Newman and Michelle
Girbaun, and it's very computationally
inefficient.
But it's also quite intuitive.
So I'll cover it just as a way of building
our intuition.
And also using this approach where we're.
Allowing the clustering algorithm to, to
work on its own, rather than saying, oh,
there must be a clique, and then, just
having different stopping criteria, just
like we did with the hierarchical
clustering in Payek, where we had vertex
similarity, deciding who's going to be
joined.
In this, eh, case, we're going to be
starting with a complete network and we're
going to be taking edges away, so we're
going to be deconstructing it and getting
finer and finer grained communities.
Now the basic idea behind this is that.
There's some edges that have high
betweenness.
Edge betweenness is, you know, really the
same definition as node betweenness.
It just counts the number of different
shortest paths that pass through an edge.
And if an edge has high betweenness, that
means it's between different sets of
nodes.
So, removing that edge might then reveal
what these different sets of nodes are
because it might actually, if you keep
doing this, disconnect those communities
completely.
So.
Say we have a network such as this one
with two fairly clear communities.
We might expect that these edges in
between here are the ones with high
betweenness.
And, what we're going to do is we're going
to iteratively find the one with highs
betweenness, remove it.
Now we recalculate.
And this computation is expensive.
That's why this algorithm is slow, and
doesn't scale to really large networks.
But, we'd find the next one, remove it.
We'd find the next one, remove that one.
And by doing this iteratively, we get.
Successively finer and finer, communities.
For example.
First, in this case, separating out into
two destroyed communities.
And then, four smaller ones plus two kind
of, nodes which become isolated.
And, if we evaluate this algorithm, we, we
find that for the Zachary Karate Club at
least, there's only one node which was,
miscategorized.
And, you know, who's to say that this
wasn't a more true, affiliation for that
node, but for whatever other factors, it
went the other way when, when the split
happened.
The problem with, you know, hierarchical
clustering and with this between-ness of
community finding algorithm is that there
isn't a clear stopping criterion, right?
It's, it's great that you can stop it
different resolutions.
But how do you know which one is optimal?
Which one might be the true community
structure of the network.
So.
Germin and Newman went back and they,
formulated this measure of modularity,
which is going to tell us, you know, at
some point, we're going to maximize this
quantity.
And when we do that, we're going to have
the most edges.
Within the community, much more so than
you would expect at random, with this
particular community partition.
So what we do is for each node, we, assign
a community, C.
So vertex V is in commun-, C, in community
C sub V, and ver, vertex W is in community
C sub W.
And now, this is just a delta function.
So this is going to be one if W and, and V
are in the same community.
And it's going to be zero if they're not.
So this function is going to sum just.
Over the nodes which are assigned in the,
into the sin community.
And really this is.
Algorithm agnostic, so you could be doing
the betweenness Clustering, you could be
doing hierarchical clustering.
It does, doesn't really matter, you can
always calculate the modularity.
So the question is, if V and W are in the
same community, how, how many edges do we
observe between such nodes in the same
community.
So we are going to sum over the adjacency
matrix and then we are going to subtract
how many edges we would expect at random,
because.
C and W have deg, degrees, so, say, oh,
sorry.
V and W have degrees, so case of V is the
degree of V, and case of W is the degree
of W.
And so just by chance, these two may have
linked to each other.
The higher their degree, if they're, if
they're two really large hubs, there's
relatively higher likelihood that they'll
be linking together than if they each have
degree one.
And so, that's just what we're doing.
We're looking at the actual number of
links within the community, versus.
Versus how many links you would expect
Based on the degree of those nodes that
have been assigned to the same community.
And we're doing this for all of all pairs
of nodes.
And for a random network.
There would be no difference between, or,
or actually also for a random community
assignment, there would be no difference
between what you observe and what you
expect on average.
And so your modularity would be zero.
So, an algorithm that can then use
modularity is, again, a hierarchical
approach, where you start with all
vertices as isolates.
But now, rather than joining together
vertices or groups of vertices that are
similar according to some measure, we're
going to join the ones such that the
modularity increases maximally.
And so we can keep doing this until the
modularity no longer increases.
Or we can actually go beyond that point,
allow modularity to decrease.
But we still have a way of kind of
minimizing that decrease, and also getting
larger communities.
So, this is very scalable up to very large
graphs.
And there is, code available if you want
to just download it standalone.
But very nicely, it's also implemented in
Gaffey.
A reminder of why you may want to do this,
here is some work again by Mark Newman.
Where he looked at, I think these are the,
the scientific collaborations at the Santa
Fe Institute And rather than looking at,
oh there's this big network, and
everyone's working on something.
You can find groups of researchers who are
working on the same thing.
And then you can even do something like
visualized metanodes, where one metanode
represents everyone in the same community.
And now you can start to see the
relationships between these different
groups.
In this case, it would be how different
groups or researchers, cross collaborate.
One, thing that I haven't mentioned that
explicitly so far is that, for the
algorithms that I've mentioned, we're
really partitioning the network.
We can't have one node be a member of two
different communities.
However in a, a real world, And that work,
this is hardly.
The case, right?
When you look at your facebook network,
you may have seen distinct communities.
However, you have to.
Be aware that, that was a slice.
That was a slice of that individual's
network that pertains to you.
And they probably know you through a
single contacts or you know, at most two
contacts.
So that's someone you know from school,
that's someone you know from work.
But each of those individuals.
Has lots of other contacts so their other
school or their other work that's, that's
not related to you, and this give a very
dense, inter interlinked structure that's
very hard to partition in the way that a
lot of these algorithms would like to do
it.
And Jure Leskovec and his collaborators at
Stanford have found that for many large
social networks, the huge ones, precisely
the ones that you would really like to be
able to partition so you can study little
parts of it, it's almost impossible to do
so.
So networks such as Flickr, Orkut.
The Microsoft Instant Messaging, graph.
None of these are easily partitionable.
And they found that, at most, you know,
communities of 100 nodes can be separated.
And everything else is too overlapped to,
to do it.
So, what comes to the rescue, then, are.
Community-finding algorithms, which allow
for overlap.
Which allow nodes to be members of more
than one community.
One such software, which you can download
for free, is called Clique Finder.
And their approach is Having rolling
cliques, so in a way have clique
percolation.
And these cliques are going to roll around
and in each, at each time step you have a
clique.
And then you can drop one node as long as
the next node that you add is again going
to be a clique of the same order.
So let me just show you here, these four
nodes are a four clique, so if we were to
roll this now, we could.
Leave, this node, out, and.
One such piece of software that allows you
to find o-, overlapping communities is
Clique Finder, which you can download for
free.
The basic idea there is that you are going
to roll cliques around.
It's a, it's a, it's a form of clique
percolation.
You're going to see how many steps you can
take when the rules are as follows.
You are going to choose a certain size
clique.
Say a four clique, that is four nodes who
each have, Links to everyone else with in
the clique.
And then in each step you can omit one of
the nodes, and add another one.
As long as that step allows you to form
another clique.
And you keep doing that, until you can't
move any further.
So for example, here we have these four
nodes, in a clique.
And then we can leave this one out.
And.
And oops, sorry.
[laugh].
And get this clique here.
And then, finally, we can leave this guy
out, and get this clique here.
And, in this way, we can get, overlapping
communities.
Which you know, is very relevant for
social networks.
It's very relevant for biological
networks.
And it's just, it's just plain, more
flexible to, to find overlapping
communities than to partition the network
in a, in a choppy way.
So just to wrap up.
What we've tackled this week is that large
networks can be giant hairballs.
And if we can identify distinct regions
within the network, that can give us
important insights.
Are these functional groups within the
cell?
Are these.
Areas of research within, you know,
science.
Are these individuals within an
organization.
Now how we approach that.
Discovery of interesting structure is
partitioned into two, tuh, two different
themes.
The first one is that you're going to look
for specific structures.
For example, you're going to look for
cliques or K-cores.
But if the network actually doesn't
exhibit this structure and it exhibits
some other structure, these, this approach
can be too rigid.
So what we talked about now most recently,
and what's been popular definitely in the
past ten years or so, is looking for more
organic.
Approaches which let the community
structure show itself to you.
And you can use methods or metrics such as
modularity to see whether.
Well, first of all to try to find that
organic partition but also to evaluate any
sort of community finding algorithm.
In so far as did it place nodes in the
same community in a way that had much
greater density of edges within the
community than from those nodes to other
places, other parts of the network.
Now, for the assignment.
You'll be looking at ingredient networks.
So here is, the network of ingredients
compliments.
These are things that go, together often
or that co-occur often.
And here is, Oh shoot.
What's the sandwich called?
Sauerkraut and corned beef and, and Swiss
cheese.
How can it?
Oh, it's a Reuben sandwich.
That's right.
And I wanted to show you one other web
application that isn't going to be a part
of your assignment, in part because I
don't want to overload their server.
But that I think is very neat and uses an
information theoretic approach that I will
provide the article for and you can check
it out yourself.
I, I mean, I think that, that article is
just testimony to the many different
creative approaches, really fun
approaches, that people have taken to.
Discovering communities and networks.
So let me try and switch over.
To that site.
Okay, so I'm going to load my, network of,
substitutes, and I'm going to do the
directed network.
And I'm going to calculate clusters.
Cool.
So each one of these clusters now is a set
of ingredients.
So if I double click on this one I can
find that.
It's clustered chicken, and turkey, and
beef, and sausage, and chicken breasts,
together.
As ingredients that are frequently
substituted for one another.
We can also, for example, look at olive
oil.
And find olive oil substituted by butter,
substituted by applesauce.
I didn't know this until I was doing the
research.
But, I guess applesauce is often a low
fat, alternative, that, that gets,
substituted in.
Now, let me see if I can.
Find, there's a neat kind of, sub-graph.
Oh, explore sub-network.
Cool.
So here we have the sub-network of the
most common, substitutions.
So it looks like maybe, applesauce.
Is common both for butter and oil.
But not, as I said just a second ago, for
olive oil.
Right?
So maybe if you're going the, putting in
the extra effort to use olive oil instead
of any old oil, you're also less likely to
then, go for the applesauce.
Which, you know, may be lower calorie.
But maybe doesn't taste as good as, as
olive oil.
So with that, I'll, close out week four.
I hope you have fun with the assignment.
And next week we'll be talking about small
world networks.
So, going back a little bit to modeling
and understanding the structure of these
networks.
Where does the community structure come
from?
And what implications does it have for
things such as diffusion of information?
Or, the ability of infor-, of individuals
to find information within the network.
So, see you next week.