Webwhompers

Our understanding of collective decision-making relies on the notions of popularity and influence. Popularity is the quality of being commonly liked; it is often used to measure the outcome of a collective decision (e.g., counting votes). Influence is the power to affect others; it is often used to shape the process of a collective decision (e.g., lobbying). These two distinct qualities are often combined -- such as when popularity confers influence.

In the context of the Web, we mathematically model popularity and influence with indegree and PageRank™, respectively.

Indegree and PageRank™ are two ways of measuring network centrality. Despite its intuitive appeal, network centrality is hard to define. For example, which node is most central in the following graph?

There is no one right answer, because saying a node is "central" is ambiguous. A few ways to compute which node is most central include:

• Indegree Centrality: Just another way of saying indegree. Node 4 above has the highest indegree centrality: it is the only node with 3 incoming links.

• Outdegree Centrality: Just another way of saying outdegree. For a Web page, this indicates author activity. In the above graph, node 5 has the highest outdegree centrality: it is the only node with 3 outgoing links.
• PageRank™: An enhanced version of indegree centrality. In the above graph, node 2 has the highest PageRank™.

In this chapter we will explain PageRank™, including the reasons why node 2 is most "influential" in the above graph. Our explanation combines basic concepts of set theory, graph theory, and algorithms -- all drawn from previous chapters. Those who explore PageRank™ in more depth will find the literature full of references to matrix algebra and recursion, which are useful topics in more advanced courses of mathematics and computer science. For a head-first dive into these topics, see Eigenvector centrality, which is the mathematical foundation on which PageRank™ is built.