0:00

'Kay, hi again.

Â Now, that we have welcome you to the course,

Â we have say a few words about what algorithm main thinking is about.

Â We will start with the actual material in the course, and

Â we will start with the very first problem that we will see and, and deploy or

Â employ algorithm thinking to solve that problem.

Â And the problem is go,

Â is going to deal with something that, with a phrase that you probably have seen.

Â Or has said.

Â Or, friends that you have heard from someone or have rated somewhere.

Â Which is, it's such a small world.

Â We, I have stated many times, you probably have said, or

Â again have read it somewhere.

Â You travel to a different country, you see someone that turns out to know someone,

Â that is your cousin, or your friend, and so on.

Â And they say it's a small world.

Â So, in this, in this part of the course,

Â we are going to talk about that small world statement that we make.

Â What is a small world?

Â What does it mean?

Â What does it imply?

Â What, should we care about it?

Â And how do we test if the world is really small?

Â Okay?

Â So in this, in this part of the course, we are going to do, use algorithmic thinking.

Â To reason about the world.

Â If it is small and, how we, how do we decide if it is small?

Â Or how do we test algorithmically if it is small?

Â Okay, now what does it mean to say the world is small?

Â We usually use it in the context of who knows whom.

Â Right, in the sense that, again, I travel to a country.

Â I meet a person there, and that person we start chatting, having conversation and

Â that person all of the sudden mentions another person,

Â that turns out to be my colleague, or my cousin, and so on.

Â So, we usually think about the, the issue of small world in terms of whom know whom.

Â So, if you think about individual X knowing Y, Y knowing Z, Z knowing W, and

Â so on, the question is, does X know W, for example.

Â And, and if I take any two individuals, what is the,

Â what is the chance that they are connected through a very short path.

Â Okay, so when we talk about small world, and we talking about the world as

Â the individual world, and who know, and who knows whom.

Â Then that when we talk about small world we are basically saying if I

Â take any two individuals in the world, what is the shortest path that

Â connects these two people in terms of who knows whom relationship.

Â 2:28

Okay.

Â Now, why do we care about the small world?

Â Of course, this is an algorithmic thinking class.

Â It's not about, let's just try to quantify what people mean by, it is a small world.

Â No, being, the world being small is actually a phenomenon that

Â doesn't just apply to the world as individuals and their relationships.

Â It applies to a network, for example.

Â You can basically look at a computer network.

Â And say, if I take any two nodes in that network, how far apart are they?

Â If I take two nodes at random, how far apart are they?

Â If I take any kind of connectivity map, for example of proteins, of proteins in

Â the cell, if I look at your cell and I map all the proteins and their connections,.

Â If I take any two proteins at random, how far apart are they?

Â In terms of connections, okay?

Â Protein A talks to protein B.

Â B talks to C.

Â C talks to D.

Â So, we have a path of length three between A and D.

Â How far apart are they?

Â Now.

Â This, this phenomenon of small world, again the applies to protein networks,

Â to computer networks to networks of humans, and individuals, and

Â how they know each other has great implications on many, in many areas.

Â For example, if we have a small world phenomenon, or

Â a small world effect in a certain system.

Â Like if every individual.

Â Is connected to every other individual by a path.

Â By like at most three, and other individuals.

Â Then you can think about information flowing through that

Â population very quickly.

Â If you, if someone starts a rumor that rumor is going to spreads very,

Â is going to spread very quickly.

Â But for more interesting applications, for example, in the area of ep, epidemiology.

Â If the, if the individuals in a, in a city, for

Â example, are connected so tightly that we have a small world effect,

Â that we have between any two individuals, we have such a short route.

Â Then if, if someone gets infected with infectious disease, then there's

Â also very good chance that, that disease is going to spread through the community.

Â Very quickly.

Â So, there's more world, the small world phenomenon.

Â It started by, basically by thinking about how people are connected and

Â how far apart are any two individuals that we choose at random.

Â But its implications and

Â its interest are way beyond just looking at individuals in a society.

Â So we care about this.

Â And when we have a system of, of interconnections, we are interested,

Â one of the things that we are interested in knowing.

Â Does that system exhibit the small walled effect?

Â 5:06

Okay?

Â The, one of the main, the main experiments or, the first experiments that were done.

Â To look at whether humans, or

Â individuals are connected very tightly in the sense that any two individuals

Â are connected by a short path was done in the early 60s by Stanley Milgram.

Â And you can look up, for

Â example, the Milgram experiment, it's a very famous experiment.

Â It was done in such a low-tech fashion that they were basically mailing letters.

Â Among individuals, and they wanted to see how long it takes a letter to,

Â to reach from person A to person B, even if, even though A and B have no

Â knowledge of the relationships of the, of the individuals in the, in the community.

Â 5:50

However, the, the, our, our access today then,

Â our access to information and technology have tremendously since the early 60s.

Â So today, we have access to very large so, skill, social data from Facebook,

Â from instant messaging, from Twitter, from Emails and so on,.

Â That will allow us to ask these kind of questions at the much larger scale from

Â much large scale data and in a much more systematic way.

Â Instead of us mailing letters among individuals, we can now go and

Â mine data, sources of data, from Facebook, or

Â Twitter again or, or emails for example and try to quantify that question.

Â And try to understand is the world really small.

Â 6:34

Okay?

Â So, the first thing is we need to understand the problem.

Â Again remember that we want to em, em, employ algorithmic thinking.

Â We need to understand the problem here.

Â So, let's assume that we have access for example, to all the Facebook data, okay?

Â So, we have information about all the individuals that have accounts

Â on Facebook.

Â We have also all the information about who's a friend of whom, okay?

Â We would like to know, understanding the problem basically tells us that we

Â would like to understand if, using Facebook data, the world is small, okay?

Â So, what that means is that if I look at the Facebook data, and

Â I take any two accounts in the Facebook network.

Â What is the, the distance of these two accounts?

Â If I take any two accounts at random again.

Â 7:19

So, then the problem in this case is not actually very hard to understand.

Â We have all the Facebook data.

Â We need to see if that Facebook did the exhibits small world effect.

Â Next we move next to the, the formulation phase.

Â And we need to think now about how do we formulate the input to the problem.

Â Now it makes sense when we look at again individuals, and their connections,

Â that we have a representation that says, okay I have here this individual 0,

Â individual 1, individual 2, 3.

Â Four and so on.

Â Again when we locate the,

Â the entire Facebook data, we have many more than five notes.

Â But for the sake of illustration let's assume that we have five accounts for

Â five individuals.

Â Then we have five individuals, in addition we

Â know also from this individual who's connected to who, who's a friend of who.

Â For example zero is connect, has a friend of one, zero is a friend of two.

Â Of three and of four.

Â One is a friend of just zero, two is a friend of three and of four.

Â These are the connections, so if I take a snapshot of Facebook this is what I get.

Â I have five individuals this is how they are connected on Facebook.

Â So, this will be the input.

Â And in this case it makes most sense to think about the input in

Â terms of a graph again.

Â Nodes, and edges.

Â Because the system is amenable to a representation with graphs, okay?

Â Once I have this input, what is the output?

Â How do I test the small world effect?

Â I have to look at, for every pair of nodes here, I need to ask the question,

Â what is the distance between these, these nodes, okay?

Â So, one way to look at this is by producing what we call a distribution of

Â the pair wise distances.

Â What is a distribution of pair wise distances?

Â I have to tabulate all of pair wise distances here.

Â I have to say what is the, I have to look at ever pair of nodes.

Â 9:19

Since we are looking here at who knows who we don't have a way to the edge.

Â We are not asking who knows who best or communicate five times a day or

Â anything like that.

Â All we are saying is that who knows now.

Â So, now when we talk about the distance, the next question we ask,

Â what is the distance here.

Â In this case basically, what is the minimum number of

Â connections that will take me from individual i to individual j.

Â So, the distance between nodes zero and one is one.

Â They are connected by one connection.

Â From zero to two, it's one.

Â From zero to three it is one.

Â From zero to four it is one.

Â 10:17

From 1 to 4, it is 2.

Â And so on.

Â Once I have these pair-wise differences for every pair of nodes, their distance,

Â I can tabulate this and say, okay, how many pairs of nodes have distance one.

Â Then I can look at all of them, I can count them one, two,

Â three, four, five, and so on.

Â Let's assume we have seven pairs that have distance one.

Â 10:43

How many nodes are, how many pairs of nodes are distance two,

Â it might be four, for example, and I put a bar.

Â How many are distance three?

Â This and so on.

Â This is what we call the distribution.

Â [NOISE] Distribution of pair wise distances.

Â This distribution is going to tell me whether the world is small or not.

Â Whether this Facebook network exhibits a small world effect or

Â not because I can look at it and say.

Â For example, if this is the entire distribution,

Â I will say any two individuals you take a trend on, they are connected by the,

Â by the path of length one or two or three, whichever is short.

Â In this case, actually.

Â they might not be too short because this is the number of

Â individuals is already five.

Â But you get the point that if I take this input.

Â And this output, basically I have formatted the problem cleanly, and

Â it will allow me to answer that question whether Facebook network exhibits

Â worldwide defect, okay.

Â So, this is what we basically mean when we say that this is the formulation of

Â the problem, and we formulated the problem as a graph theoretic problem.

Â It is a problem that involves graphs.

Â Okay, so now we are going to move to graphs, what the graphs are and, and

Â some basic concepts.

Â