In this and the next three chapters, we will walk through a remarkable landscape of intellectual foundations. But sometimes we will also see significant gaps between theory and practice.

A Short Answer

We continue with the theme of recommendation. Webpage ranking in Chapter 3 turns a graph into a rank-ordered list of nodes. Movie ranking in Chapter 4 turns a weighted bipartite user–movie graph into a set of rank-ordered lists of movies, with one list per user. We now examine the aggregation of a vector of rating scores by reviewers of a product or service, and turn that vector into a scalar for each product. These scalars may in turn be used to rank order a set of similar products. In Chapter 6, we will further study aggregation of many vectors into a single vector.

When you shop on Amazon, likely you will pay attention to the number of stars shown below each product. But you should also care about the number of reviews behind that averaged number of stars. Intuitively, you know that a product with two reviews, both 5 stars, might not be better than a competing product with one hundred reviews and an average of 4.5 stars, especially if these one hundred reviews are all 4 and 5 stars and the reviewers are somewhat trustworthy. We will see how such intuition can be sharpened.

In most online review systems, each review consists of three fields:

1. rating, a numerical score often on the scale of 1–5 stars (this is the focus of our study),

2. review, in the form of text, and

3. review of review, often a binary up or down vote.

In the last chapter, we saw the importance of topology to functionality. In this and the next chapters, we will focus on generative models of network topology and reverse-engineering of network functionality. These are mathematical constructions that try to explain widespread empirical observations about social and technological networks: the “small world” property and the “scale free” property. We will also highlight common misunderstandings and misuse of generative models.

A Short Answer

Since Milgram's 1967 experiment, the small world phenomenon, or the six degrees of separation, has become one of the most widely told stories in popular science books. Milgram asked 296 people living in Omaha, Nebraska to participate in the experiment. He gave each of them a passport-looking letter, and the destination was in a suburb of Boston, Massachusetts, with the recipient's name, address, and occupation (stockbroker) shown. Name and address sound obvious, and it turned out that it was very helpful to know the occupation. The goal was to send this letter to one of your friends, defined as someone you knew by first name. If you did not know the recipient by first name, you had to send the letter via others, starting with sending it to a friend (one hop), who then sent it to one of her friends (another hop), until the letter finally arrived at someone who knew the recipient by first name and sent it to the recipient. This is illustrated in Figure 9.1.

A Short Answer

Principles of distributed congestion control

When demand exceeds supply, we have congestion. If the supply is fixed, we must reduce the demand to alleviate congestion. Suppose the demand comes from different nodes in a network, we need to coordinate it in a distributed way.

As the demand for capacity in the Internet exceeds the supply every now and then, congestion control becomes essential. The timescale of congestion control is on the order of ms, in contrast to shaping consumer behavior through pricing in Chapters 11 and 12. The need for congestion control was realized in October 1986, when the Internet had its first congestion collapse. It took place over a short, three-hop connection between Lawrence Berkeley Lab and UC Berkeley. The normal throughput was 32 kbps (that is right, kbps, not the Mbps numbers we hear these days). That kind of dial-up modem speed was already low enough, but during the congestion event, it dropped all the way down to 40 bps, by almost a factor of 1000.

The main reason was clear as we saw from the last chapter on routing: when users send so many bits per second that their collective load on a link exceeds the capacity of that link, these packets are stored in a buffer and they wait in the queue to be transmitted. But when that wait becomes too long, more incoming packets accumulate in the buffer until the buffer overflows and packets get dropped.

A Short Answer

ISPs charging consumers on the basis of usage is just one corner of the overall landscape of Internet economics. We will pick consumers' monthly bills to focus on in this chapter, but there are many other key questions.

• The formation of the Internet is driven in part by economic considerations. Different ISPs form peering and transit relationships that are based on business and political decisions as much as on technical ones.

• The invention, adoption, and failure of Internet technologies are driven by the economics of vendor competition and consumer adoption.

• The investment of network infrastructure, from purchasing wireless licensed spectrum to deploying triple-play broadband access, is driven by the economics of capital expenditure, operational expenditure, and returns on investment.

The economics of the Internet are interesting because the technology-economics interactions are bidirectional: economic forces shape the evolution of technology, while disruptive technologies can rewrite the balance of economic equations. This field is also challenging to study because of the lack of publicly available data on ISPs' cost structures and the difficulty of collecting well calibrated consumer data.

Smart data pricing

There is a rapidly growing research field and industry practice on network access pricing. What we described on usage pricing in the last chapter, in the form of tiered and then metered/throttled plans, is just a starter.

We have mentioned the Internet many times so far, and all the previous chapters rely on its existence. It is about time to get into the architecture of the Internet, starting with these two chapters on the TCP/IP foundation of the Internet.

A Short Answer

We will be walking through several core concepts behind the evolution of the Internet, providing the foundation for the next four chapters. So the “short answer” section is going to be longer than the “long answer” section in this chapter.

It is tricky to discuss the historical evolution of technologies like the Internet. Some of what we would like to believe to be the inevitable results from careful design are actually the historical legacy of accidents, or the messy requirements of backward compatibility, incremental deployability, and economic incentives. It is therefore not easy to argue about what could have happened, what could have been alternative paths in the evolution, and what different tradeoffs might have been generated.

Packet switching

The answer to this chapter's question starts with a fundamental idea in designing a network: when your typical users do not really require a dedicated resource, you should allow users to share resources. The word “user” here is used interchangeably with “session.” The logical unit is an application session rather than a physical user or device. For now, assume a session has just one source and one destination, i.e., a unicast session.

A Short Answer

Much of the web services and online information is “free” today because of the advertisements shown on the websites. It is estimated that the online ad industry worldwide reached $94.2 billion in 2012. Compared with traditional media, online advertisements' revenue ranked right below TV and above newspapers.

In the early days of the web, i.e., 1994–1995, online advertisements were sold as banners on a per-thousand-impression basis. But seeing an ad does not mean clicking on it or buying the advertised product or service afterwards. In 1997, GoTo (which later became Overture) started selling advertisement spaces on a per-click basis. This middle ground between ad revenue (what the website cares about) and effectiveness of ad (what the advertisers care about) became a commonly accepted foundation for online advertising.

With the rise of Google came one of the most stable online ad market segments: search ads, also called sponsored search. In 2002, Google started the AdWords service where you can create your ad, attach keywords to it, and send it to Google's database. When someone searches for a keyword, Google will return a list of search results, as well as a list of ads on the right panel, or even the main panel, if that keyword matches any of the keywords of ads in its database. This process takes place continuously and each advertiser can adjust her bids frequently. There are often many ad auctions happening at the same time too. We will skip these important factors in the basic models in this chapter, focusing just on a single auction.

A Short Answer

Now we turn to the other links you see on a search-result webpage; not the ads or sponsored search results, but the actual ranking of webpages by search engines such as Google. We will see that, each time you search on www.google.com, Google solves a very big system of linear equation to rank the webpages.

The idea of embedding links in text dates back to the middle of the last century. As the Internet scaled up, and with the introduction of the web in 1989, the browser in 1990, and the web portal in 1994, this vision was realized on an unprecedented scale. The network of webpages is huge: somewhere between 40 billion and 60 billion according to various estimates. And most of them are connected to each other in a giant component of this network. It is also sparse: most webpages have only a few hyperlinks pointing inward from other webpages or pointing outward to other webpages. Google search organizes this huge and sparse network by ranking the webpages.

More important webpages should be ranked higher. But how do you quantify how important a webpage is? Well, if there are many other important webpages pointing towards webpage A, A is probably important. This argument implicitly assumes two ideas:

1. • Webpages form a network, where a webpage is a node, and a hyperlink is a directed link in the network: webpage A may point to webpage B without B pointing back to A.

2. We can turn the seemingly circular logic of “important webpages pointing to you means you are important” into a set of equations that characterize the equilibrium (a fixed-point equilibrium, not a game-theoretic Nash equilibrium) in terms of a recursive definition of “importance.” This importance score will then act as an approximation of the ultimate test of search engines: how useful a user finds the search results.

A Short Answer

In June 2011, Apple announced its iCloud service. One of the eye-catching features is its digital rights management of music content. The other part is its ability to let you essentially carry your entire computer hard drive with you anywhere and stream music to any device.

Cloud is more than just storage. For example, in the same month, Google introduced ChromeBook, a “cloud laptop” that is basically just a web browser with Internet connectivity, and all the processing, storage, and software are somewhere in Google servers that you access remotely.

These new services and electronics intensify the trends that started with web-based emails (e.g., Gmail), software (e.g., Microsoft Office 365), and documents (e.g., Google Docs and Dropbox), where consumers use the network as their computers, the ultimate version of online computing.

In the enterprise market, many application providers and corporations have also shifted to cloud services, running their applications and software in rented and shared resources in data centers, rather than building their own server farms. Data centers are facilities hosting many servers and connecting them via many switches. Large data centers today is typically over 300,000 square feet, house half a million servers, and cost hundreds of millions of dollars to build.

There are three major cloud providers as of 2012: Amazon's EC2, Microsoft's Azure, and Google's AppEngine. A pioneering player in cloud services is actually Amazon, even though to most consumers Amazon stands for an online retail store.

A quick recap of where we have been so far in the space of online services and web 2.0. In Chapter 3, we discussed the recommendation of webpages with an objective metric computed by Google from the graph of hyperlinked webpages. In Chapter 4, we discussed the recommendation of movies with subjective opinions estimated by Net ix from movie–user bipartite graphs.

Then we investigated the wisdom of crowds. In Chapter 5, we discussed aggregation of opinion in (more or less) independent ratings on Amazon. In Chapter 6, we discussed resolution of opinion conflicts in Wikipedia.

In this chapter, we will talk about dependence of opinions, taking a macroscopic, topology-agnostic approach, and focusing on the viral effect in YouTube and tipping in Groupon. Then in the next chapter, we will talk about the effect of network topology on the dependence of opinion.

As will be further illustrated in this and the next chapters, network effects can be positive or negative. They can also be studied as externalities (e.g., coupling in the objective function or the constraint functions, where each user's utility or constraint depends on other users' actions), or as information dependence (e.g., information cascades or product diffusion as we will see in this chapter).

A Short Answer

Viralization

YouTube is a “viral” phenomenon itself. In the space of user-generated video content, it has become the dominant market leader, exhibiting the “winner takes all” phenomenon. More recently it has also featured movies for purchase or rental, and commissioned professional content, to compete against Apple's iTunes and the studios.

To study a network, we have to study both its topology (the graph) and its functionalities (tasks carried out on top of the graph). This chapter on topology-dependent influence models does indeed pursue both, as do the next two chapters.

A Short Answer

Started in October 2003 and formally founded in February 2004, Facebook has become the largest social network website, with 900 million users worldwide as of spring 2012 at the time of its IPO. Many links have been formed among these nodes, although it is not straightforward to define how many mutual activities on each other's wall constitute a “link.”

Founded in July 2006, Twitter attracted more than 500 million users in six years. At the end of 2011, over 250 million tweets were handled by Twitter each day. Twitter combines several functionalities into one platform: microblogging (with no more than 140 characters), group texting, and social networking (with one-way following relationships, i.e., directional links).

Facebook and Twitter are two of the most influential communication modes, especially among young people. For example, in summer 2011's east-coast earthquake in the USA, tweets traveled faster than the earthquake itself from Virginia to New York. They have also become a major mechanism in social organization. In summer 2009, Twitter was a significant force in how the Iranians organized themselves against the totalitarian regime.

A crude answer is that interference management in WiFi does not scale well beyond several devices sharing one access point. When the crowd is big, the “tragedy of the commons” effect, due to mutual interference in the unlicensed band, is not efficiently mitigated by WiFi. To see why, we have to go into the details of WiFi's medium access control in the link layer of the layered protocol stack.

A Short Answer

How WiFi is different from cellular

Since their first major deployment in the late 1990s, WiFi hotspots have become an essential feature of our wireless lifestyle. There were already more than a billion WiFi devices around the world by 2010, and hundreds of millions are added each year. We use WiFi at home, in the office, and around public hotspots like those at airports, in coffee shops, or even around street corners.

We all know WiFi is often faster than 3G cellular, but you cannot move around too fast on WiFi service or be more than 100 m away from an Access Point (AP). We have seen many letters attached to 802.11, like 802.11a, b, g, and n, shown on the WiFi AP boxes you can buy from electronic stores, but maybe do not appreciate why we are cooking an alphabet soup. We have all used hotspot services at airports, restaurants, hotels, and perhaps our neighbor's WiFi (if it does not require a password), and yet have all been frustrated by the little lock symbol next to many WiFi network names that our smartphones can see but not use.

Introduction

In the previous chapter we discussed analysing and interpreting the assignment topic and compiling a work plan. In this chapter we will learn how to search for and find relevant information so we can write an appropriate and relevant assignment answer. We are going to look at what information we need to retrieve; where we will find this information; how we will retrieve the information; and how we know which retrieved information is best for our task.

The keywords, headings and subheadings on the work plan are a good place to start. They indicate what information we need but now we need to consider where we will find this information.

What does retrieving information involve?

Retrieving information involves two steps:

1. 1. Locating relevant sources

2. 2. Selecting the information

These two steps involve several activities. To retrieve information we need to locate sources in a collection either by physically going to the library or accessing sources via the Internet and then selecting relevant information from these sources. Relevant information is information that directly applies to the assignment topic. For example, look at the following assignment question:

Relevant information has a direct relationship to the keywords and headings which we have jotted down on the work plan. We identified the keywords as Internet search engine; Google; Yahoo; evaluate website. Also on our work plan we jotted down various subheadings under the main headings. (Refer back to the work plan in Chapter 8 for these headings.)

When we start looking for information it is generally easiest to turn to our own collection of books and periodicals. However, our own collection of books and sources are generally not extensive and will therefore not give us enough relevant information for completing an assignment. An external collection, such as a library, on the other hand, contains so many different information sources that our search for information will be more complicated. Either way, the steps involved in searching for information are the same, whether they relate to an internal or an external collection. The steps are just simpler when the collection is small and when we are familiar with using it.

Introduction

In the previous chapters we have already focused on many of the prewriting activities necessary for writing an essay assignment. We have discussed the work plan and taking notes; evaluation of your information and ensuring your information is relevant to the topic. In this chapter and the next chapter we are going to focus on the main activities involved in the actual writing process including the prewriting activities, drafting, rewriting, organisation and structure, final editing and proofreading. We hope by giving you some pointers and showing the various techniques you will be better equipped to face this task and feel less anxious about writing an essay assignment.

Writing is not an easy process even for experienced writers. To write well you constantly need to reshape, refine, and rewrite. Inexperienced writers often write poorly because they do not realise that writing is not a linear process but requires constant reworking and revision of their initial ideas. In other words it is an iterative process.

Prewriting

Prewriting activities are the processes you go through before you even begin writing. Prewriting activities give us a better idea of what we want to communicate, how we are going to say it and why we want to communicate it to a reader. In writing you need to first identify your audience and your purpose. These are both important prewriting activities that you need to do before you can begin writing.

Some of the important questions you need to ask yourself before beginning are:

• • Who are your readers?

• • What do they expect?

• • What do they know about the subject?

• • What special terms or concepts might you use that will have to be explained to your readers?

• • What is the purpose of your writing?

Time spent in prewriting activities will not be wasted because these help you to make sure that you answer the assignment question, and are aware of your purpose and audience.

Lecturer as an audience

When you write an academic assignment it is a particular situation with particular requirements that have to be met. Although you know that the lecturer reading and evaluating your assignments is knowledgeable about the topic, you have to write as if he or she knows nothing about the topic.

Introduction

Read the following scenario and then answer the questions below:

If we look at the scenario above we can see that Veli had problems with her assignment because she wanted to start writing as soon as possible. She skipped the interpretation and planning stage and began immediately looking for information. As a result she read sources and took notes without a clear idea of what was relevant. All she had was a very general idea of the topic. Then when she sat down to write the assignment she found that some of her notes were irrelevant and she did not have enough information on some of the important aspects of the topic. She also found that her marks did not reflect the amount of work that she had put into the assignment. This could have been avoided by spending some time interpreting the topic.

• • Do you take time to read and analyse an assignment question? Yes/No

• • When you start working on an assignment do you have a work plan? Yes/ No

• • Do you identify the keywords in the assignment topic before you begin finding information? Yes/No

If you answered no to these questions then it is very important for you to study this chapter because in this chapter we will learn how to analyse an assignment topic and develop a work plan.