0:00

So, in the last lecture we talked about graphs, and we undirected and directed

Â graphs, how we representing using them adjacency, less than adjacency matrix.

Â And in that lecture, also, we, we dealt with these two examples of graphs.

Â This is an undirected graph, on four north, has four edges.

Â This is a directed graph with four nodes and three edges.

Â So now, we need to introduce a few more concepts about graphs that we

Â will need them in order to define the problems that we will be dealing with,

Â the first of which is the concept of of, of neighbors and degrees.

Â So, when we look at an undirected graph.

Â We say that two nodes are adjacent or

Â neighbors, if there is an edge that connects them.

Â So for example, in this graph nodes zero and one are neighbors, nodes 0 and

Â 2, 3 are, are neighbors, nodes 0 and 2 are not neighbors, okay?

Â And the second concept, we talk about is the degree of a node.

Â What is the degree of a node in an undirected graph?

Â In an undirected graph the degree of a node is the number of neighbors it has.

Â 1:01

Okay? So, if I look at this here and I look at,

Â each one of the nodes I can tabulate their degrees, [SOUND] by counting for

Â every node the number of neighbors it has.

Â So, how many neighbors does node zero have?

Â It has one neighbor, two neighbors.

Â 1:25

And three has two neighbors as well, 0 and 2.

Â So this are the degree of a node.

Â When we talk about undirected when we talk about directed graph.

Â Then we talk about.

Â We don't talk about the degree usually.

Â We talk about two types of degrees.

Â There's an in-degree and there's the out-degree.

Â The N degree of a node is the number of edges incoming into that node, and

Â the out degree of a node, is the number of edges outgoing of that node.

Â So, if we look at, again as before, we can tabulate.

Â 2:08

Now we can look at the four nodes.

Â And ask for each node, what is its in-degree, what is its out-degree.

Â What is the in-degree of node 0?

Â How many edges are incoming into node 0?

Â There are none.

Â What is the in-degree of node 1?

Â There are three edges incoming into node 1, so, it is in degree 3.

Â What is the end degree of node 2?

Â There are none incoming into it.

Â Same thing for 3.

Â There are no edges incoming into it.

Â These are the in-degrees.

Â What are the out-degrees?

Â Node 0, there's one edge outgoing of it.

Â For node 1 there is, there are no edges outgoing of it.

Â And for node 2, there is 1, for node 3, a 1.

Â So, for undirected graph we talk about the degree of a node.

Â For a directive graph we talk about the in-degree and out-degree of a node.

Â Okay?

Â 2:57

Now the, the last concept we need to introduce in this case, for the,

Â for the small world problem, is the concept of connectivity.

Â Again, what it does it mean for two, for two nodes to be connected?

Â What is the path between two nodes?

Â What is the length of a path between two nodes?

Â And ultimately what is the distance between two nodes.

Â And for this, we can illustrate it on the undirected graph for example.

Â [SOUND] And, let's assume that we have this graph.

Â G, and let's take two nodes that are different and

Â designate them as our source and target.

Â Again, in, think about it in the case of the GPS system, or,

Â in the GPS system is your current location and the destination.

Â In the case of the small world phenomenon on Facebook graph, we want to compute for

Â every pair of nodes the distance.

Â So, we can take any pair of nodes and consider them as our two designated nodes.

Â So let me take now nodes 0 and 2 from here.

Â So I will take, I will call them I and J.

Â 4:07

So, I have 2 nodes in G that are 0 and 2.

Â And I want to ask the question, of course, what is the distance between node 0 and 2.

Â Before we, we answer that question we have to talk about the concept of a path.

Â 4:20

We say that there's a path between two nodes, I and J of length K.

Â If there are K minus 1 nodes, K minus 1 nodes,

Â U1, U2 all the way to UK minus 1.

Â 4:36

Such that, if I put them somehow between I and J, I have an edge from I to U1,

Â an edge from U1 to U2, an edge from U2 to U3, and so on.

Â And from UK minus 2 to UK minus 1.

Â And finally, from UK minus 1 to G.

Â If you count the number of edges on this path, there is one, two, K minus 1, K.

Â This is a path of length k.

Â So, we say there is a path of length K between two nodes, I and J.

Â If I can find K minus 1 nodes, other nodes in the graph.

Â Such that I can arrange in a way, that there is an edge from I to U1,

Â U1 to U2 and so on.

Â Okay? So it's a matter of getting K minus 1

Â nodes, a subset of K minus 1 nodes, arrange them in such away; that

Â between every two consecutive nodes in that arrangement, there is an edge.

Â If this is the case we say there's a path from, between I and J of length K.

Â 5:33

I'm illustrating things on undirected graphs.

Â In the case of directed graphs, when we.

Â If I want to say there's a path from I to J,

Â from I to J, then I have to take edges that, indeed exist.

Â And I transverse their, their direction.

Â This on the direction in the graph.

Â So I cannot put this if there is no h from I to U1.

Â I cannot say that is a pass from I to J if the edges are connected like this.

Â Okay.

Â In the case of directed graph it has to be from I to U1,

Â U1 to U2, U2 to U3, UK minus 2 UK minus 1 and so on.

Â Okay?

Â So, this is what it means for a path of length to exist between two nodes.

Â Notice that the length of the path is measured in terms of the number of edges.

Â The key is the number of edges.

Â On that path, okay?

Â We say that a path is simple if it does not use the same node more than once.

Â It does not use any node more than once.

Â So, I can have a path from 0 to 2 that goes 0, 1, 2, 3, 2.

Â This is not a simple path.

Â It's repeated at least one node more than once.

Â Okay?

Â 6:51

Finally, now that we have defined what a path means and

Â what is the length of a path, the distance between two nodes,

Â the distance between node I and J is the smallest K.

Â Such that there is a path of length k between I and J.

Â So the length, the distance between 0 and

Â 2 is the smallest K such that there is a path length K between 0 and 2.

Â The smallest K for example I can think about it that could be a candidate is 1.

Â Then I ask myself is it a path of length one between 0 and 2.

Â No it isn't, because a path of length one means there's an edge between 0 and 2.

Â So that I put an X on it, there is no path of length one.

Â Then I move to length two.

Â I ask is there a path of length two between 0 and 2?

Â Yes there is.

Â There are in fact two of them.

Â So that the distance between 0 and 2, is 2.

Â Because it's the smallest K,

Â for which there is a path of length K between 0 and 2.

Â Same thing again for directed graphs.

Â It's what is the smallest K, for which there is a path from I to G, of length K.

Â Now that we have defined, what is the connectivity, the connectivity in graphs,

Â and the distance between two nodes in a graph?

Â Now that small world problem is cleanly defined as follows.

Â The input is just a graph and

Â undirected graph whose nodes correspond to the accounts on Facebook for example, and

Â the edges correspond to friendship on Facebook.

Â And the output is the distribution of all the distant,

Â the pairwise distances of nodes in that graph, okay?

Â So now, that we introduced these concepts and graphs.

Â Now we are capable of formulating the problem in a graph theoretic sense.

Â And now, we can proceed to solve this problem.

Â And now ,we are going to go on for our first attempt at solving it.

Â