0:08

Okay. Recall now that our original problem that

Â we are interested in is testing whether the,

Â the small world effect or phenomenon holds for a given system of interactions.

Â For example give a Facebook network we want to see.

Â If we see, if we observe the small world phenomenon.

Â Or if we have even a computer network, a network of computers,

Â we want to see if the small world phenomenon also holds there.

Â Because, again, you can think, for

Â example, for a network of computers, if the, small world phenomenon holds for

Â that system, it means that information can flow between these computers very quickly.

Â Or, you can think about, about bad situations where an attack on

Â the network can flow also through the system very quickly.

Â So if one of the computers in the system is infected with a virus,

Â that virus might spread throughout the network very quickly.

Â So that was our original problem, is given a network.

Â Which in it, by now, we know that we can represent its connectivity in terms of

Â a graph, of nodes and, and edges, we want to check if that network,

Â satisfies the war, the small world phenomenon and we, as we said,

Â we took that problem, we formulated it as a graph theoretic problem of

Â computing pair wise distances between every pair of nodes in the graph.

Â And then plotting a distribution.

Â And our first attempt was, okay let's come up with an algorithm that

Â follows the definition of what is a distance in a graph.

Â And that led us to what we call a brute force algorithm.

Â And, that algorithm, we showed that it is easy to implement,

Â it is easy to reason about its correctness.

Â However, we also showed, that from the perspective of time efficiency, how long.

Â The algorithm will take on any reasonable input of any reasonable size.

Â We showed that that algorithm is not feasible in practice.

Â We couldn't even run it on, on a graph, that had 100 nodes.

Â Okay? So, the question is what do we do then?

Â I mean, is that, is that the end of story?

Â We cannot test if a network, if a large network has a small world phenomenon or

Â satisfies a small world phenomenon.

Â The answer is fortunately no.

Â We don't, this is not the end of the story.

Â In fact, we can think about computing distances in a undirected,

Â unweighted or even directed and unweighted graph.

Â Very quickly, okay?

Â So we can come up with with an algorithm that's much more intelligent than brute

Â force way of looking at every possible path of every possible length that led to,

Â to to exponential, at least exponential amount of time.

Â So, let's reason about how would we go about coming up with an algorithm that

Â computes distances in a graph, in an unweighted graph, graph that has no.

Â No weights on the edges, much more intelligently.

Â And I will illustrate with a, with a, with a specific graph, just for the sake

Â of illustration.

Â [SOUND] So I will illustrate with this graph here.

Â This is a, an undirected graph that has six nodes.

Â And, we will, we will try to for example here I'm going to focus on one case of

Â let's compute distances for example from zero to every other node.

Â Remember that in the original problem we want to compute the,

Â distance between every pair of node.

Â Okay? So let me now focus on the problem that I

Â want to compute the distance between zero and every other node in this graph.

Â Now, [SOUND] the way we can do it more intelligently is to

Â start thinking about looking at this graph and

Â thinking how can I find the distance from node zero to every other node.

Â 3:58

I will denote by dj for example the distance,

Â [SOUND] between node 0 and node j okay.

Â So here the source node.

Â Is, is fixed.

Â I'm, I'm always focusing on node 0 and

Â I want to compute the distance from 0 to every other node.

Â The distance from node 0 to node 5 is going to be represented by

Â d sub 5 for example.

Â So, when I look at this graph,

Â the easiest thing to say is what is the distance from node 0 to itself.

Â So the route from d, from node 0 to itself, which we call d0, is 0, okay.

Â So now I know that at least, I can compute the distance from the node to itself.

Â Then, what are the next nodes that are easy for me to compute distances?

Â If I look at this graph and I know that the distance to node 0 is 0,

Â now I can look at the neighbors of that node,

Â remember the neighbors are nodes that are connected by an edge, okay.

Â So if, if the, if my distance, if the distance to me from node 0 is 0,

Â now I look at my neighbor.

Â Going from node 0 to my neighbor is going to go through me, okay?

Â If I am a node here the, the distance is going to go through me to that node.

Â Now, a distance that goes through from 0 to one is going to

Â be the distance to node 0 plus one edge, right?

Â So if I look at all the neighbors of node 0, their distance from node 0.

Â Is 1 plus the distance from 0 to itself.

Â Okay. So I know that if I look at

Â node 0 the distance itself is 0.

Â Then I know that the distance from 0 to all its neighbors is 1.

Â So I can immediately say, okay, for

Â node 1, d1 [SOUND] is 1, d3 is one, d4 is 1.

Â Now, notice I didn't go to node 1 and then node 2.

Â I'm looking first at all the neighbors of 0.

Â Okay?

Â So, think about it as, I'm going to proceed in layers.

Â At layer 0, [SOUND] I'm looking at the initial node.

Â Okay? The node, node 0.

Â Then, at, at layer 1.

Â I'm going to look, [SOUND] I'm going to look at all

Â nodes that are at distance 1, one edge away from node 0.

Â And this is easy, again, because we have, if, if we for

Â example, have, have an adjacent illustrative presentation of the graph.

Â Then I look at node 0, I look at all the adjacent nodes of it.

Â For each one of them I say the distance to these nodes are, is 1.

Â Okay.

Â 6:48

After I'm done, I'm done with layer 1 now I can go to layer 2.

Â What is layer 2?

Â If I start from node 0 and I have computed the distance to its neighbors.

Â I next move, I move in the next step, to the neighbors of the neighbors of node 0.

Â So these are the neighbors at layer 1 of node 0.

Â Now for each one of them, I look at its neighbors.

Â Okay? So for node 1.

Â It has two neighbors.

Â Th, it has three neighbors.

Â Node 0.

Â Node 3.

Â And node 2.

Â Okay?

Â So I look at node 1.

Â It has three neighbors.

Â But these two neighbors their distances has been computed.

Â Okay?

Â They have been computed already so I am done.

Â Now I look at, at nodes for

Â the which then the, the distance has not been computed yet.

Â Now.

Â What is the distance to node 2 from node 0?

Â I know that I can get to node 1, from node 0 in one step, right?

Â So the distance from 0 to 1 is 1.

Â Node 2 is away from 0 by 1 edge from node 1, so I can take

Â the length of the path to 1, add to it 1 and I will get the distance to node 2.

Â [SOUND] Okay. So I can think of the distance to node 2

Â is the distance to node 1 plus one.

Â Because 2 is a neighbor of 1.

Â But what is the distance to node 1 if there's 1.

Â 8:07

So it is 2.

Â Okay.

Â Now, as I said, 3 is also a neighbor of 1, and I can say that

Â d3 is d1 plus one, which will give it 2, but 2 is larger than the distance

Â that they already have computed and I don't need to update it, okay?

Â So we do, we do this.

Â Node 3 has, now, we, we are done with node 1,

Â we are done with all the neighbors of node 1.

Â We go to node 3 that we have already processed, and I look at its neighbors.

Â They have already been processed, their distances have been computed.

Â I look at neigh, at node 4 this the distance to

Â its neighbor 0 is already computed, we don't already have to, to update it.

Â And it has this neighbor 2, the distance have been computed from node 0.

Â We have another node, node 5, which is, [SOUND] we need to compute it's distance.

Â The, the distance to 5 is that I can go through 4,

Â through distance, [SOUND] from 0 to 4, plus 1 more edge, right?

Â Which is 1 plus 1, which is 2.

Â Okay.

Â And, this way, I have dealt with these at layer 2, okay.

Â And, given this spec, specific graph, I am done actually.

Â The algorithm is done.

Â So we, we, we traversed the graph in, in, in the in layers.

Â At layer 0, we deal with the source node that we specified.

Â To, to compute distances from.

Â At layer 1 all the notes that are, that are neighbors of the original node.

Â At layer 2, all the neighbors of the neighbors and so on.

Â 9:39

Okay?

Â This kind of algorithm, that looks at, at the node, then at all it's neighbors.

Â Then for each neighbor at all its neighbors.

Â This is known as,

Â breadth [SOUND] first search or BFS.

Â Okay?

Â This is a very, famous algorithm for graph exploration or traversing graphs.

Â That works in the breadth-first manner.

Â The, the the reason we call it breadth-first is that when we

Â look at the node we al, always look at the neighbors of

Â that node before we move from this node to its neighbors.

Â Okay?

Â So, a breadth-first search algorithm is going to explore the graph.

Â And while exploring, the graphic it can update these values of these djs and

Â give us the distances, okay?

Â Now, [COUGH] this, this is how the algorithm works and

Â it's easier to describe, but will before we go to the, go the point where we

Â write the algorithm, we have to pay attention to a few details here.

Â So, the first detail that we have to pay attention to is, when I,

Â when we compute the distance d0, then we started looking at, at the neighbors.

Â I said okay, we have d1 is 1, d3 is 1, d4 is 1.

Â When we were done we said let's go to layer 2.

Â How did we go to layer 2?

Â Now we went to the neighbors of 1, then the neighbors of 3, then the neighbors of

Â 4, in this order, because I compute the distance to 1 first, then to 3, then to 4.

Â When I want it to go to layer 2, I want it to go to 1, and

Â it's neighbors, to 3, look at it's neighbors, to 4, look at it's neighbors.

Â So how do I keep track of this information?

Â How do I keep track.

Â Of this, order, that I was the 1 then 3 then 4, so that next time when I

Â go to layer 2, I go to neighbors of 1, then neighbors of 3, then neighbors of 4.

Â So this is where, the, the concept of data structure has come into the picture,

Â that we have to use some sort of data structure that is going.

Â To, to allow me to save this information and keep, keep track about

Â how the nodes were visited, so that the next time I look at their neighbors for

Â the next layer, I also visit the neighbors of nodes in the right order.

Â So, let's look again at this case.

Â When I visit node 0, after that I look at it's neighbors.

Â I looked at node 1, then 3, then 4, so I want once I,

Â once I computed the d1, I want to put it in a data structure such that,

Â 12:13

this is node 1 here, then I, put 3, then I put 4 here.

Â And next time when I look at for

Â layer 2, I need to look at this node first, then this, then this, okay?

Â So, remember what happened here.

Â I insert, I insert node 1, then I insert node 3, then I insert node 4, okay?

Â So when I, when I am done with this,

Â I have this list of nodes that has these three nodes here.

Â That next time, when I go to layer 2, I can come back here and say okay, now,

Â let's look at node 1, then node 3, then ne, node 4.

Â Okay?

Â So, the way we, we deal with this kind of, of algorithm, or

Â with this type of data structure is that,

Â we have this type of list that we are, we are going to, to have.

Â I'm going to have two endpoints to it.

Â I'm going to label them as the head, [SOUND] and

Â I'm going to label this as the tail, okay?

Â And every time I see, when, when I'm processing the neighbors of a given node,

Â I'm going to add, once I compute the distance to a neighbor,

Â I'm going to add that neighbor to this list.

Â In such a way that I maintain the order in which they were visited.

Â So the way to do this is always to insert a node and a tail.

Â Okay? So I insert one.

Â So, if I want to work through this.

Â 13:38

[SOUND] In the beginning, the list was, empty.

Â It had nothing. So the head.

Â [SOUND] N tail are pointing to the same place.

Â So I, I, I encounter node 1 first.

Â I said insert it at the whatever the tail is pointing to.

Â It's here so it becomes, [SOUND] node node 1 here.

Â Sorry, node 1.

Â Now this is the head.

Â And this is the tail now, the tail moves to the right.

Â When I see node 3, I add now node 3 here at the tail and

Â I move the tail to the right.

Â [SOUND] When I see node 4, I,

Â put node 4 here and I move the tail here.

Â [SOUND] Okay.

Â So this is how we grow this list.

Â Now this list, is maintained in a very specific way,

Â that, I always add things at the tail.

Â When I want, when next, time when I come to process la,

Â layer 2, I want to start with node 1, then 3, then 4,

Â so I look at the neighbors of 1, then the neighbors of 3, then the neighbors of 4.

Â So then I come and access things from the head side, okay.

Â So the next time, when I want to, when I want to process at layer 2,

Â I want to look at all the neighbors of, of of node 1, which is exists at the head.

Â So I can look at this, deal with all its neighbors, I get done with it,

Â and I move the head.

Â 15:13

I deal with this. I get done with it.

Â I move ahead and so on.

Â But notice also that when I da, when I deal with, when I process node 1,

Â I have to add all the neighbors that have not been processed to the queue.

Â So once I'm done with 1, also node 2 was added at the tail.

Â [SOUND] And the tail moved, [SOUND] okay?

Â Then when we process 3, 3 has no neighbors that have not been processed, so

Â we process it and we move the head without adding anything.

Â [SOUND] Then, we process node 4.

Â It has only one neighbor that has not been processed yet.

Â We added it to the, to the tail, and we move the head here, and

Â we move the tail to the right.

Â [SOUND].

Â Okay.

Â And we keep, proceeding like this.

Â This type of list, where we add things to the tail.

Â And we remove things from the head is known as a queue.

Â Okay.

Â So this data structure is called a queue.

Â