[MUSIC]

So we're ready to tackle the problem of detecting communities

within a social network.

And we've thought about this problem a couple of times so far, but

by the end of this video,

you'll be able to describe both the notion of communities within a social network,

and think about how to implement an algorithm for finding these communities.

So remember our motivation is to try to make sense

of huge number of interconnected nodes that appear in this network.

But they are somehow clustered into subcommunities within the big network.

And so we'd like to capture this notion of communities really being

groups of people who have more connections to one another

than to people who are outside of the group.

And so, if we want to translate that

intuition about what community might look like to graphs and

algorithms, we need to have a more precise definition of what a community is.

And in order to come up with that precise definition,

we could really attack the problem in two different ways.

The first way would be to look for those tight links, and

try to group together nodes that have a lot of edges between them.

And somehow build up communities from kernels, starting from within a community,

so maybe like the heart of the community, find vertices that have lots and

lots of connections between them.

And then add on additional vertices if they have a fair number of connections

between them, and then somehow grow communities from the middle out.

But on the other hand, we could attack the problem from the outside in.

And say, if I have a region in my graph where it looks like there's

not such a strong link between man part of the graph and another,

then there's probably not a community that encompasses both parts of that graph.

And so what we might want to do is look for links that we could cut, and

cutting those links wouldn't interfere with the community structures and

might help us subdivide our problem into smaller chunks.

That then we could iterate and look at within those new parts of the graph,

see if there's weak links there and cut those and weak links etc.

And that way hone in to those communities from the outside in.