
タイトル：
Magic Trick  Intro to Algorithms

概説：

If you did this right, it should be the case that all of these edge boxes are checked off,

and you ended up with an actor.

Nowthis is the magic trick partI'm going to tell you which actor you ended up with.

The answer is Kevin Bacon. Ta da! Pretty neat, huh? Let's try it.

I'm going to follow maybe a different path than you did, but I'm going to do my best to try it.

Just to try to thwart this, maybe I'll do directly to Kevin Bacon.

I'll visit this edge. Now I'm at Kevin Bacon.

I go to Dustin Hoffman.

I go to Susan Saradon. I go to Julia Roberts.

I can't go do Kevin Bacon now, because I'll be at a dead end.

I visited all the other edges that have gone through Kevin Bacon,

so I'll go to Dustin Hoffam to Robert Deniro to Meryle Streep again

to Ann Hathaway back to Julia Roberts, and now I can go to Kevin Bacon and be done.

It may or may not have been the same path that you followed,

but I did end up at Kevin Bacon.

You can try this a couple different ways, and you'll see that you'll always end up with Kevin Bacon.

So that's our magic trick.

This example illustrates two things that are central to this course.

The first is the idea of a social network.

We often think of social networks as being particular websites that exist these days,

but really what a social network is is connections between individuals

that capture relationships between them.

These days, of course, they ubiquity and scope of social network data is exploding.

Clever computer software is needed to reveal interesting patterns

and answer important questions about this data.

It's a really neat area.

The second focus of this course is on the magic of algorithms.

Algorithms are just how we organize computations to solve a particular problem.

Some algorithms are really straightforward,

but other algorithms take advantage of subtle mathematical properties

to quickly and accurately provide an answer.

Those are the ones that feel like magic.

With that said, now I'm going to try to tell you how this trick actually worked

and what it tells us about these kinds of structures.

Let me first point out that this kind of structure where you've got a set of circles and lines

connecting between them is what we in computer science and discrete math call graph.

In this particular graph, the actors are playing the role of nodes, sometimes called vertices.

And the movies are playing the role of edges or links.

I'll probably mostly say "nodes" and "edges,"

which kind of mixes a metaphor, but that's how I'm used to saying it.

We can also talk about the degree of a node in a network.

For example, this Dustin Hoffman node here is a node in the network.

It's got degree 4 because there are 4 edges coming out of it1, 2, 3, 4.