 ## Subtitles section Play video

• The following content is provided under a Creative

• Your support will help MIT OpenCourseWare

• To make a donation or to view additional materials

• from hundreds of MIT courses, visit MIT OpenCourseWare

• at ocw.mit.edu.

• JULIAN SHUN: Hi, good afternoon, everyone.

• So today, we're going to be talking

• And as a reminder, on Thursday, we're

• going to have a guest lecture by Professor Johnson of the MIT

• Math Department.

• And he'll be talking about performance

• of high-level languages.

• So please be sure to attend the guest lecture on Thursday.

• So here's an outline of what I'm going

• to be talking about today.

• So we're first going to remind ourselves what a graph is.

• And then we're going to talk about various ways

• to represent a graph in memory.

• And then we'll talk about how to implement

• an efficient breadth-first search algorithm, both serially

• and also in parallel.

• And then I'll talk about how to use graph compression and graph

• reordering to improve the locality of graph algorithms.

• So first of all, what is a graph?

• So a graph contains vertices and edges,

• where vertices represent certain objects of interest,

• and edges between objects model relationships between the two

• objects.

• For example, you can have a social network,

• where the people are represented as vertices

• and edges between people mean that they're

• friends with each other.

• The edges in this graph don't have to be bi-directional.

• So you could have a one-way relationship.

• For example, if you're looking at the Twitter network,

• Alice could follow Bob, but Bob doesn't necessarily

• have to follow Alice back.

• The graph also doesn't have to be connected.

• So here, this graph here is connected.

• But, for example, there could be some people

• who don't like to talk to other people.

• And then they're just off in their own component.

• You can also use graphs to model protein networks, where

• the vertices are proteins, and edges between vertices

• means that there's some sort of interaction

• between the proteins.

• So this is useful in computational biology.

• As I said, edges can be directed,

• so their relationship can go one way or both ways.

• In this graph here, we have some directed edges and then also

• some edges that are directed in both directions.

• So here, John follows Alice.

• Alice follows Peter.

• And then Alice follows Bob, and Bob also follows Alice.

• If you use a graph to represent the world wide web,

• then the vertices would be websites,

• and then the edges would denote that there is a hyperlink

• from one website to another.

• And again, the edges here don't have to be bi-directional

• because website A could have a link to website B.

• But website B doesn't necessarily

• have to have a link back.

• Edges can also be weighted.

• So you can have a weight on the edge that

• denotes the strength of the relationship

• or some sort of distance measure corresponding

• to that relationship.

• So here, I have an example where I am using a graph

• to represent cities.

• And the edges between cities have

• a weight that corresponds to the distance between the two

• cities.

• And if I want to find the quickest way to get from city A

• to city B, then I would be interested in finding

• the shortest path from A to B in this graph here.

• Here's another example, where the edge weights now

• are the costs of a direct flight from city A to city B.

• And here the edges are directed.

• So, for example, this says that there's

• a flight from San Francisco to LA for \$45.

• And if I want to find the cheapest

• way to get from one city to another city,

• then, again, I would try to find the shortest path in this graph

• from city A to city B.

• Vertices and edges can also have metadata on them,

• and they can also have types.

• So, for example, here's the Google Knowledge Graph,

• which represents all the knowledge on the internet

• And here, the nodes have metadata on them.

• So, for example, the node corresponding to da Vinci

• is labeled with his date of birth and date of death.

• And the vertices also have a color

• corresponding to the type of knowledge that they refer to.

• So you can see that some of these nodes are blue,

• some of them are red, some of them are green,

• and some of them have other things on them.

• So in general, graphs can have types and metadata

• on both the vertices as well as the edges.

• Let's look at some more applications of graphs.

• So graphs are very useful for implementing queries

• on social networks.

• So here are some examples of queries

• that you might want to ask on a social network.

• So, for example, you might be interested in finding

• all of your friends who went to the same high school as you

• So that can be implemented using a graph algorithm.

• You might also be interested in finding

• all of the common friends you have with somebody else--

• again, a graph algorithm.

• And a social network service might run a graph algorithm

• to recommend people that you might know and want

• to become friends with.

• And they might use a graph algorithm

• to recommend certain products that you

• might be interested in.

• So these are all examples of social network queries.

• And there are many other queries that you

• might be interested in running on a social network.

• And many of them can be implemented

• using graph algorithms.

• Another important application is clustering.

• So here, the goal is to find groups of vertices

• in a graph that are well-connected

• internally and poorly-connected externally.

• So in this image here, each blob of vertices of the same color

• corresponds to a cluster.

• And you can see that inside a cluster,

• there are a lot of edges going among the vertices.

• And between clusters, there are relatively fewer edges.

• And some applications of clustering

• include community detection and social networks.

• So here, you might be interested in finding

• groups of people with similar interests or hobbies.

• You can also use clustering to detect fraudulent websites

• on the internet.

• You can use it for clustering documents.

• So you would cluster documents that

• have similar text together.

• And clustering is often used for unsupervised learning

• and machine learning applications.

• Another application is connectomics.

• So connectomics is the study of the structure, the network

• structure of the brain.

• And here, the vertices correspond to neurons.

• And edges between two vertices means

• that there's some sort of interaction between the two

• neurons.

• And recently, there's been a lot of work

• on trying to do high-performance connectomics.

• And some of this work has been going on here at MIT

• by Professor Charles Leiserson and Professor Nir Shavit's

• research group.

• So recently, this has been a very hot area.

• Graphs are also used in computer vision--

• for example, in image segmentation.

• So here, you want to segment your image

• into the distinct objects that appear in the image.

• And you can construct a graph by representing the pixels

• as vertices.

• And then you would place an edge between every pair

• of neighboring pixels with a weight that corresponds

• to their similarity.

• And then you would run some sort of minimum cost cut algorithm

• to partition your graph into the different objects that

• appear in the image.

• So there are many other applications.

• And I'm not going to have time to go through all of them

• today.

• But here's just a flavor of some of the applications of graphs.

• So any questions so far?