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.