Project idea: broadcasting to a Twitter network, part 2

Loading...

From the course by University of California San Diego

Capstone: Analyzing (Social) Network Data

78 ratings

University of California San Diego

Capstone: Analyzing (Social) Network Data

78 ratings

Course 5 of 5 in the Specialization Object Oriented Java Programming: Data Structures and Beyond

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.

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.

Week 2 introduction2:02

Project idea: information flow in a social network12:00

Project idea: broadcasting to a Twitter network, part 16:24

Project idea: broadcasting to a Twitter network, part 26:29

Project idea: detecting communities11:44

Meet the Instructors

Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering
Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Leo Porter
Assistant Teaching Professor
Computer Science and Engineering

[MUSIC]

So on the last video we solved the problem we are talking about.

And that problem is trying to find the minimum set of users you need to

send out announcement so that it reaches everyone.

That problem is actually hard.

And relates very well to the dominating set problem.

What we're going to do in this video is try and get a better feel for

what we can do when we recognize that problem is hard,

just like we did back in course three with the travelling salesperson problem.

So, at the end of this video you should be able to recognize available steps to

help you solve your problem whether it be this problem or other problems.

And then implement at least one possible approximation algorithm to this specific

problem.

All right, so the end again of the last video,

we realized that finding a minimum dominating set is a known NP-Hard problem.

So, this means we're not going to be able to come up with a perfect solution.

What's our next step?

Well Researching possible options is really your next step so

the places you may want to go are text books or websites and here you'll be

looking for approaches that been taken in the past to solve minimum dominating set.

The other thing that you can look at are research papers, and

the best website to find research papers in my opinion is scholar.google.com.

And if you look on scholar.google.com you'll almost always find research

papers on computer science problems and I bet you'll find some really good resources

associated with minimum dominating set.

So your first step really is to find out what have other people done, and

then try to get a good feel for what you're going to do to solve your problem.

And what I want to do is walk through now one potential approach you could take.

And this is a fairly obvious greedy algorithm solution to this problem.

So what we're going to do is we're going to mark all vertices.

And what I'll do is I'll walk through all these steps of the algorithm carefully,

but let me just give you a first idea.

Right at the beginning we're going to say that all of the vertices are uncovered.

And we're going to create a dominant set and we're just going to make it empty.

And then we're going to essentially go through, as long as we haven't

covered all the vertices, we're going to find the vertex that's going to cover

the most uncovered vertices, and we're going to add it to our set.

So, let's see what this looks like.

So I've got this graph here in the upper left, and

in the first iteration of the loop, I'm going to start looking for

the vertex which, if added to the dominant set, is going to cover the most vertices.

So if you look around you're going to find that it's actually,

this vertex is going to cover the most.

It's going to cover itself, along with seven other vertices so that's

a pretty big covering, that's the one that's going to cover the most you select

that to be part of your dominate set, you add into the dominate set and then you

mark everything that's adjacent to as covered, so we mark all those as covered.

Now we're not done because there are still uncovered vertices.

So next Iteration loop, we're going to find what vertex is going to

cover the most uncovered vertices.

And this case,

it's going to be this one because this is going to cover five vertices.

We're going to mark that as covered or we're going to add that to the dominant

set and we're going to mark all of his neighbors covered.

Itself and all his neighbors is covered.

At this point we actually cover everything in this graph.

So for this graph,

our greedy algorithm has actually found the minimum dominant set.

Every time it's going to find a dominant set,

this time it's actually found the minimum dominant set.

But will you always find the minimum dominant set.

So what I want you to do is the best way to learn these algorithms

is by doing samples on your own.

So if you can, pause the video, try and

come up with a counter example before you keep watching.

I'll see you back in just a moment.

All right, I hope you were able to find a counter example on your own.

One where this greedy algorithm will fail to find you the minimum dominant set.

But here's an example of one that will fail that I found.

And again, there's plenty of examples that you can find.

But let's just walk through why on this graph

it actually fails as using greedy algorithm.

So, greedy algorithm is going to select the vertex.

It's going to cover the most vertices and in doing so

it's going to select to that center vertex.

That's average select in a vertex,

it's going to mark all the ones adjacent to it as covered.

And now it's got these two other ones that haven't been covered yet.

So in a net second iteration of loop

it's going to select one of these two kind of at random.

It will pick one of them and then it'll mark its neighbors as covered.

It has no other neighbors to mark.

And in the third iteration loop, it's going to find that the remain vertex,

include that in the dominant set, and we'll be done.

So this finds me the dominant set, but not a minimum dominant set.

In fact, if you look at this graph you can tell that it's really just these two nodes

that we need to have a minimum dominant set.

So, greedy algorithms can be effective, but

again remember that they have limitations.

They won't always find you the perfect solution.

So there's a couple questions I want you to look into about this problem.

So first is,

I've given you a greedy algorithm, just figure out what the runtime of it is.

The second piece is a larger question and

that is, are there better algorithms to try to solve this problem?

And better can mean a couple of different things, right?

Better could be that it's more apt to find the minimum dominant set,

it's more apt to find smaller dominating sets, or that it just runs more quickly.

And this is where your research is going to come in.

So you're going to be reading the textbooks or

websites about this problem or research papers about this problem.

In through that reading you're going to get better feel for the algorithms

that are out there and which one you want to employ in your solution.

I do want to give you this one quick heads up that if you're really comfortable with

theory of computation and complexity theory and

I mean really comfortable with it.

You could look into fixed-parameter tractability.

It actually applies fairly well to this problem, but again,

it's an extremely advanced topic.

Don't dive into it unless you really are comfortable with those areas.

All right, now that we have a better feel for this problem, and

recognize that this problem is actually hard, and that we're probably going to

have to use some kind of approximation algorithm to solve this problem,

you can continue exploring this problem as your focus for your project.

But I also want you to explore other problems and what we're going to do next

is actually show you another kind of problem that you might want to solve and

we'll dive into that in the next video.

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.

Download on the App Store

Get it on Google Play