Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Strength of Connections - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. To motivate the algorithms that we're going to talk about in this unit.
  2. Let's go back to the Marvel data again. So here's three superheroes.
  3. We're going to call them Black Widow, Spider Man, and the Hulk.
  4. Remember that they're connected in the graph, in the original graph by an edge,
  5. if the comic book character is in a particular comic book.
  6. This is a set of comic book characters and a set of comic books,
  7. and we add links like so depending on which comic book characters are in which comic books.
  8. Now, we're often interested in connections between the individual characters.
  9. Up to now, we said that there's an edge linking, say Black Widow and Spider-Man,
  10. in and only if there exists a comic book such that Black Widow and Spider Man
  11. both appear in that comic book in the original data set.
  12. There's really two different graphs that we're working with here.
  13. There's the graph between comic book characters and then there's the bipartite graph
  14. between comic book characters and comic books.
  15. Now this edge appeared, as long as there's at least one book they had in common,
  16. even if that book had a zillion comic book characters in it
  17. and it was the only book that they were in together as opposed to, let's say,
  18. it's like Batman and Robin which is probably not Marvel.
  19. But anyway, two comic book characters that appear together very often,
  20. they would also just get a link between them and that doesn't seem quite right.
  21. What we'd like to do is put a weight on this edge
  22. where the weight equals the number of books they co-appear in.
  23. All right, so what you need to do is compute connection strength.
  24. Write a Python program to read the Marvel graph and put a strength value on each link.