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. So, this behavior of people ignoring their private signal to follow the public actions before them, is one model of viralization that we will see. And we also see some kind of influence motto that describes synchronization, 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.