In this capstone project we’ll combine all of the skills from all four specialization courses to do something really fun: analyze social networks! The opportunities for learning are practically endless in a social network. Who are the “influential” members of the network? What are the sub-communities in the network? Who is connected to whom, and by how many links? These are just some of the questions you can explore in this project. We will provide you with a real-world data set and some infrastructure for getting started, as well as some warm up tasks and basic project requirements, but then it’ll be up to you where you want to take the project. If you’re running short on ideas, we’ll have several suggested directions that can help get your creativity and imagination going. Finally, to integrate the skills you acquired in course 4 (and to show off your project!) you will be asked to create a video showcase of your final product.
Project idea: detecting communities
Loading...
From the course by University of California San Diego
Capstone: Analyzing (Social) Network Data
81 ratings
University of California San Diego
81 ratings
Course 5 of 5 in the Specialization Object Oriented Java Programming: Data Structures and Beyond
From the lesson
Project Definition and Scope
Now that you're warmed up, it's time to get started planning for the bulk of your capstone project. This week you will identify several questions you'd like to answer about the social network data. For each of these questions, you'll research and evaluate data structures and algorithms that would be useful in implementing a solution. Defining the scope of your project and anticipating bottlenecks and tricky spots is tough but extremely valuable. You'll use asymptotic analysis to guide and refine your design.
Meet the Instructors
Christine AlvaradoAssociate Teaching Professor
Computer Science and Engineering
Mia MinnesAssistant Teaching Professor
Computer Science and Engineering
Leo PorterAssistant Teaching Professor
Computer Science and Engineering
[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.
So, the algorithm that we will be talking about for this video is one of those
divisive algorithms that start from the outside and looks for those quick legs.
And the intuition that we'll use for
describing our communities is that if we have two separate communities
then what's going to happen is to get officially from one community to another,
we might always have to use one edge that sort of connects those communities.
The analogy we might want to think of is like communities geographically
located on either side of a highway.
So that if we ever want to travel from one of those communities to another, we have
to go through this bottleneck highway, and so anytime we want to travel between them,
our shortest path will tend to flow through a particular part of the network.
And so that particular part of the network is really like a border between
our two communities and acts to separate them.
So what we want to do is find those borders and then cut them.
And so our algorithm might exactly look for those borders.
So, what we want to do now is translate this intuition of traffic and
borders to graphs.
And so, let's look at a simple graph, a toy example.
And so we have this network here and let's think about path in this network for
getting from one vertex to another, and then see if information about those paths
can tell us something about how we might group these vertices together.
Now, as a spoiler a bit, just looking at the graph,
you probably have a sense of which vertices it would make sense to group.
So, think ahead about how you would, as a human without having to use an algorithm,
think about grouping these vertices into communities.
And then let's see how our algorithm plays out and
whether it matches up with your intuition, okay.
So let's think about notes 6 and 7 in this graph.
Let's think about what would be a shortest path from 6 to 7.
What do you think?
Well, you probably said there's an edge between them, so of course,
we are just going to jump along that edge and immediately get from 6 to 7.
All right, so let's do something a little bit more complicated.
We saw that there's just that one edge.
But what about if we went from 2 to 5?
These two vertices are no longer neighbors of one another.
We can't just jump along a single edge.
So what's the shortest path from 2 to 5?
What you may have seen is that there's actually two shortest paths.
So even though we said shortest, there's two ways of traversing the graph
from vertex 2 to vertex 5 or vice versa, they each take three hops.
We can either go up to 1, and then across to 5, or we can go down to 4 and
then across to 5.
If we started off at 2 and wanted to end at 5.
Now what's going to be really important for our analysis of these edges is that
either one of these shortest paths still has to take that edge between 3 and 5.
And so no matter how we traverse the graph from 2 to 5,
if we want to stick to efficient paths in the graph,
mainly shortest paths, we're going to need to use that really important edge.
And so that edge between 3 and
5 seems to somehow lie between the community of 2 and the community of 5.
So, this is what we're going to try to capture when we think about flow.
And the visualization you might want to have in mind here is think about traffic
flow or liquid flow where you can think about going from 2 to 5,
and we have 1 unit of water that we're pouring into the graph.
And that water is going to try and take the path of least resistance,
so the water's just going to use shortest paths through the graph and
try to get to 5.
And at the beginning, when we start at 2, half the water will go
into the blue path and half the water will go into the purple path because
they're both shortest paths and so they'll each take about half the flow.
That starts from 2 and goes to 5.
But then once they reach vertex 3, they'll join up together,
both of these quantities of flow will join up together and
the entire flow between 2 and 5 has to traverse that edge from 3 to 5.
On the other hand, we had this situation with 6 and
7 where the 1 unit of flow that was allowed to go between vertex 6 and
vertex 7 all had to go along that one edge.
It didn't separate.
There was exactly one unique shortest path between those vertices.
And so what we could now is think about this notion of flow between
every pair of vertices in the graph, and think about which edges
come up as really important edges between many pairs of vertices.
And so what we do is we compute the betweenness of edges.
So an edge has really high betweenness if it has this important function,
as being used within the shortest paths of many pairs of vertices.
So if we look at that edge between 6 and 7 again, it had all the flow that went
between 6 and 7, but it doesn't have any other contributions from any other flows,
because that edge doesn't lie on any shortest path
between any other pair of vertices, just between 6 and 7.
On the other hand, the edge between 3 and 5 lies on many many shortest paths.
It would lie on the shortest path between 2 and 5, as we saw, but
also between 1 and 5.
And also between 4 and 6.
And so that edge is really crucial,
it's lying on many shortest paths on this graph.
And so somehow we see that it's acting as a boundary between
the communities that many of these vertices occupy.
And so if we wanted to subdivide those communities we would probably cut that
edge, and thinking back to your intuition,
it's probably in line with what you were thinking of before.
If we were to group the vertices in this graph,
we would probably group the four vertices, 1, 2, 3,
4, as 1 community, and the 3 vertices, 5, 6, and 7, as a separate community.
Because there's only really one edge connecting the vertices between these two
communities, and most of the edges within these communities just stay within
those two groups of vertices.
And so, this notion of betweenness is capturing which edge we should cut
in order to make progress towards subdividing our vertices into groups
that represents communities.
And so that leads to our algorithm.
Because our algorithm now is compute the betweenness of all
edges by thinking of these flows through shortest paths.
Remove the edges of highest betweenness, we might have a tie,
in which case we might remove multiple edges, and then repeat.
We can repeat, and repeat, and repeat, and that way, we get a picture of slowly by
slowly how we refine the structure of the graph, so it gets into smaller and
smaller subdivisions that represent different levels of community.
Or we might have a particular end goal in mind,
where we wanted to keep going until we have exactly 3 communities or
17 communities and look at the graph structure with results.
And so, this is a very high level of description of the graph, but
we would probably be pretty hard-pressed to actually implement it at this point.
And so we might ask ourselves, well, how do we compute the betweenness?
What do we do?
And so for that we have to think back to that definition of betweenness, and
betweenness was accumulating that proportion of flow
that an edge was receiving as we looked at all pairs of vertices in the graph.
And so what we might want to do is think about each node v, and
the flow that it contributes to all other vertices.
And think about how much of that flow does each edge get?
So, how do we do that?
Well, the heart of that is to find the shortest path between that vertex of v and
all of the vertices in the graph.
And so we need to find the number of shortest paths from v to every other node,
but you already know how to look for shortest paths.
If you think back to course three, we talked about breadth-first search.
And breadth-first search was a way of exploring a graph and
we explored it from a central vertex out in all directions,
and every time we hit a new vertex we've got there,
we had a potential of finding the shortest path to that vertex.
And so we could explore our graph from our original node v, looking out for
shortest paths and just count them.
And so what we might do is do is do that breadth-first search,
compute the numbers shortest path from v to each of the nodes and
then proportional distribute the flow according to these paths.
And now we have a slightly lower level description of our task for the algorithm.
But if you're interested in looking at this problem more carefully and
implementing it as part of your project, you still have work to do.
You have to think about how do I do this breadth-first search?
What information do I need to capture as I'm traversing this graph and
as I'm accumulating flow over all the vertices?
How do I do this optimally?
What data structures should I use and how far should I iterate?
Because, even once I've computed the between the small edges
now I need to start removing those edges and
thinking about the community structure that results.
So at this point, we've got an algorithm but it's your turn to explore.
And you can explore optimizations to this algorithm,
you can compare it to a rich dataset where you already know something about
what the inherent communities in this data structure might look like.
And compare whether the algorithm that we've just outlined will agree with those
communities that come up from additional information beyond just the edges and
the nodes that we know in the Facebook data, for example.
And you can think about how we might use some of that ground truth rich data
to inform our algorithm as we're running it, perhaps to make it run faster, or
to make it run more accurately so we don't have to do as many iterations.
Or really anywhere your heart desires.
So hopefully, this gives you some ideas of what you might do in looking for
communities in the network data.
And if you're interested in thinking about this project further,
you can take it where you would like.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
