0:00

We will start our journeys together throughout these twenty questions with a

question on our wireless, cellular mobile network.

And this shows a typical picture of a cellular network.

The entire physical space is divided into many cells, a hexagon area here.

With a base station here, and many mobile stations, like your cell phones or

tablets. And in this course, we ask the question,

how does my smartphone work in CDMA network?

In both main versions of 3G networks, CDMA is a key component of the technology,

okay? And we will look at two critical issues.

Number one is a technical one, okay? How can we control interference in the

air? Your signal will case interference to my

transmission, just like in a coctail party.

Well, maybe controlling the transmit power is a degree of freedom we can use and that

is something we'll talk about. Transmit power control including a very

simple but clever algorithm that can distributively control the transmitted

powers, so that we don't end up shouting at the top of our lungs altogether.

And this is the algorithm that was implemented in all the 2.5G and the 3G

standards. And this shows us a particular way to

control what we call the Tragedy of the Commons or so called Negative Network

Effect. Another purpose of this lecture in

answering this question is to introduce two powerful modeling methodologies.

One is called Optimization Theory. We're looking at a special case called a

linear programing here. Now, optimization is something we do all

the time in our daily lives. For example, if you want to maximize your

happiness and your degree of freedom is to chose between taking this course versus

going to the movie theater. Okay?

And the constraint is, you will have a limited number of hours each day, you may

decide to pick one or the other and optimization theory is a mathematical way

to make precise many of those English languages.

We also introduce, in addition to constrained decision making, a model to

think about strategic behavior of intelligent agents which could be human

beings, which could be networking devices and that's called game theory.

Introduce the basic terminology of both, and both would be used a lot throughout

the course. And, indeed, the next question, which is,

how does Google sell this add spaces? On a search page, we'll be using game

theory to model and analyze a particular mechanism of allocating resources, in this

case, as spaces and that mechanism is called auction.

The auction is something that some of us are familiar with, and we'll look at

different forms of auction and how an object is allocated among competing buyers

and what price shall it be charged for. We look at a graph like this, so could buy

part a graph, skipping the details to the actual lecture.

This preview suffice to say, there are many potential buyers, and many objects

and we need to find a match. What kind of match will provide a fair and

efficient allocation? That is the question we'll have to answer.

We'll look at examples from Google as well as from eBay allocation of a single

object. We'll see that a smart idea is to say that

object, if there's only one, goes to the highest bidder but the price is actually

charged based on the second highest bidder's price which sounds very counter

intuitive at the beginning. But we will see, this turns out to be a

smart way to mitigate the negative network effect or to, so called, internalize

network externality. Now, of course, Google's main business is

provide a search service and to provide a ranking of relevant web pages to your

search query. Now, how can Google rank relevant pages?

Let's say there are four relevant webpages, the actual problem is much, much

bigger scale than this. But, suppose we just have four, and there

are some links among these node, the node are the webpages, each link is a

directional hyperlink between one page and the other.

You might think, if a lot of pages point to a given page, that page should be more

important. Turns out, that is a good starting point

of a line of thoughts that lead to what's called, Page Rank Algorithm, named after

one of the two co-founders of Google. This is a powerful algorithm.

We'll see efficient way to execute it and to compute different node importance

scores. We'll pick up this theme later in Lecture

eight. We'll also show how page rank by Google is

strikingly similar, in fact, there's an exact mathematical parallel to Qualcomm's

CDMA power control algorithm. We'll see that while the networks are very

different when it's a webpage network, there is a wireless device networks.

There are many underlying commonalities in how they treat the challenging problems

there. And then, we'll move on in question four

to Netflix. If you have used Netflix, whether DVD, or

online streaming service, you have noticed that Netflix recommends movies to you.

How does Netflix do that? That is the question.

And we will talk about the interesting story behind the famous Netflix prize, an

open online international competition a few years ago where Netflix offered $one

million for teams that can do a better job of recommendation.

We're going to define, what is the job of a recommender?

Specifically, in Netflix's case, what is the figure of merit?

How can you compare one recommender's performance versus the other?

And it turns out, a powerful idea in the winning solution of Netflix prize is

collaborative filtering. It leverages the fact that different users

have different similarities and, in their behavior, and their, tendency to like or

dislike certain movies. So, if I want to estimate how user one

might like certain movies that she has watched yet, I may actually leverage my

knowledge about the other user's ratings of this movie and we see a smart idea to

leverage that understanding to enable up very accurate a recommender system.

Along the way we'll also expand our portfolio of optimization theory from so

called a Linear Programming, LP to the so called least squares, which is non-linear

quadratic optimization and we will see how that extension can be carried out.

Now, question five is something that perhaps, all of us have encountered.

We probably have all have used Amazon to do some shopping online.

And when you go to Amazon and say I want to buy a new HDTV.

You see there are two, or in fact, many options, okay?

Now, one product may have three and a half stars, the other may have five stars, as

of the average number of stars in the ratings.

And they say, well, it looks like this is a better product by average rating count

at least. But suppose I also tell you, which Amazon

does, that there are 500 reviews behind this average, and there are only two

reviews behind this average. This is a little extreme case to

illustrate a point, but in this extreme case, you can say that, well, then, I'm

not quite sure if I should trust this average of four stars anymore because

somehow the sample size is not big enough. Was there 500 of these maybe this is more

trustworthy and I rather prefer this 3.5 star product.

So, when can we trust an average rating? And, how can we incorporate the size of

the reviewer population? And, do we trust that 500 reviewers will

all be independent in the way that they evaluate?

It turns out that assuming independence and unbiased opinion, there is very

interesting way to incorporate the size of the review a population in the so called

Bayesian analysis. And we'll see how ranking can change once

you take that into account and we'll try to reverse engineer how Amazon does the

job by looking at the trend of the review scores, by looking at the size of reviewed

population and the reputation of the reviewers.

Now, these are what we called opinion aggregation problems, okay?

We try to summarize different opinions by many different users in a network into a

single number, and we know simple averaging doesn't always work.

The opinion aggregation becomes even more challenging if the result aggregation is a

binding resolution. So in question six, we will ask how could

Wikipedia even work? Wikipedia, as well know, is a free open

online and dynamic encyclopedia. While has many limitations, it by large

has worked very well over the years. Now, one of the issues that for certain

articles there's a lot of debates, certain political, religious article for example.

So, how can these contributors and the editors come to any agreement?

How can they form consensus? And we're going to look at consensus

modeling through two things, one is voting, the other is bargaining.

We'll look at the classical result of voting theory, okay?

By Arrow's is an impossibility results that says that, even when you are facing a

very mild situation, okay? For example, all the votes make perfect

sense. You can still come up with a, a voting

output, the final voting results that doesn't make sense.

For example, if there are three candidates, A, B, and C.

Then, the output may say that A is better than B, B is better than C, and C is

better than A, which is a cyclic and therefore logically inconsistent result.

And we'll look at how that could that become the case and how we can better

internalize so called network externalities to enable a more meaningful

voting system. Then, we'll also look at bargaining.

How two parties can bargain to try to reach an agreement even though the

agreement points may be different and therefore, their individual utilities, or

payoffs, or happiness will be different as a result.

Now, consensus formation is a tough subject, and we will see some gap between

the theory and the practice. Now, that gap actually will become even

bigger as we go into the next two questions.

Question seven is on how can we viralized the YouTube video?

Now, understanding, the viralization of a product or service art is something that

is very important and yet hard to accomplish.

And we will take a look at a particular model for a viral phenomena in a crowd,

where independence of opinion breaks down and we have what we call cascade of

information. After some point, everybody simply follows

what's already been done by the crowd at that point.

For example, you have may have one guy on the street corner, with a nosebleed, and

decide to tilt his head to look at the sky.

And then, if you got a few other people tilting their heads, then you may see that

many people start to aggregate and cause a cascade.

They all start tilting their head towards the sky to see what's going on up there.

14:29

people start to behave with the same face. We'll look at models that talk about

influence on a macroscopic scale. For example, when Apple first introduced

iPad, maybe only five percent of the population use it.

But then, it start to become more and more popular, and eventually it may reach a

certain equilibrium. Okay.

Maybe say 65 percent of the population will be iPad users.

So how can we model, understand that behavior.

That will be question seven. And question eight continues on the

influence model, but this time with the help of topological information.

That is, where we know who connects to whom, and then we want to understand which

nodes and which links are more important, or more central, or more influential than

others. And a, a very famous story goes back to

the Renaissance, Italian families in Florence where everybody appreciated that

the Medici family was, by far, the most influential.

But, if you just count the so called degree, that is the number of neighbors

this node has, it's got six as the degree which is indeed the largest.

But there are also families with degree of four, okay?

And, if you just look at the 50 percent difference that Harley describes, the much

higher influential power of the Medici family in this graph of family

relationships. So, how can we understand other notions of

node importance. And then, how can we use that to

understand phenomenon such as contagion of opinion, okay?

Based on the local topology of a node and to understand infection including actual

infection of, diseases. And we will see an example of how certain

diseases, can, be treated by providing enough immunity in the population so that

it does not start to become a pandemic at all.

We'll also take a look at how do we define different groups in a network.

Okay. If I give you a Facebook network, how can

you divide that into x number of groups? Now, that is an interesting discussion of

the impact of connectedness or the topology, who connects to whom, on the

functionality of influence. In the, in the next two questions we'll be

dealing with two famous topological features and the relationship between

topology and functionality in the network. Question number nine, we will ask

ourselves the question raised by many people and then codified by an experiment

by Stanley Milgram in the early 60's, the small world network.

In Milgram's example, okay? He tried to give a letter and ask people

in Nebraska to find a way to send it to the destination, which is a suburb in

Massachusetts. And it turns out that, among those

actually eventually arrived, the median length of this chain of search is actually

very small. It's actually the median is six and that

led to this famous six degrees of separation.

In late 2011, some people measured the degrees of separation on Facebook at that

time and said it's actually even smaller, it's under five.

Now, what does that mean to say there's a link between two Facebook users, that's

another debate. Now, but we're going to look at why this

small number is a surprise and we'll see it's a surprise not only because there are

short path, but also there are short path despite the fact that, in many social

networks, like nodes tend to aggregate. And therefore, your friend's friends tend

to be your own direct friends already. Despite that, there are short chains

between any two pairs of, any two nodes in the pair.

And even much deeper than that, we'll try to explain why a greedy routing letters

like in Milgram's experiment, can led to a discovery of short chains.

So, it's not just about existence off shore chains but also the computability or

the discovery of some shore chains using only very limited voter information, and

that is the true surprise we try to explain through different models of small

world networks. Another famous topological feature is

called the scale free network, that has been observed in many kinds of networks.

Including biological network, social network and certain technological

networks, like the internet router graph. Now, we'll say a few words about why those

measurements might have a problem. But, let's assume that the internet's

router connectivity pattern does follow this free, scale free feature.

Now, what is scale free? Roughly speaking, it says that, if you

look at the degrees of all the nodes in a network and you tally that into a

histogram, you would see what's called a long tail distribution which is very

different behavior than a typical, say, Gaussian or normal distribution.

There are nodes that have a huge number of degrees.

Now the question is, where are they? In year 2000, there was a rumor that says

the internet has an Achilles heel. These extremely highly connected routers

sits in the middle of the internet and they become an easy targeted attack.

And if they are taken out, then the internet is broken into many pieces.

Now the question is, if we call this kind of vulnerability, the Achilles heel

vulnerability of the internet, does the internet actually have Achilles heels?

And the answer actually is no. While the internet has many vulnerability

and security and privacy concerns, it does not have this particular type of

vulnerability. It does not have an Achilles heel.

In fact, the highly connected nodes of the internet tend to sit on the edge of the

network, and those routers in the core of the network tend to have medium to sparse

number of connectivities. And this interesting story, the lack of

the Achilles heels on the internet topology illustrates a very important

message that not only have to look at the graph of the topology of the network, but

you also have to have domain specific models on the functionalities.

In this case, the functionality of performance maximization under router

constraints in order to have meaningful conclusion about networks.