Answer key · Unit 5

Graphs and networks.

Each lesson’s practice questions, their correct answers and the mistakes they spot. Answers read off the Scene use the same setting the learner sees.

Misconception catalogue

Answer key 4

Lesson 1 of 4 · About 20 minutes

Nodes and edges

From a town to a graph: nodes, edges and degree, why the degrees always add up to twice the edges, and what a new bridge does to the degrees.

Open the lesson

The 5 steps and their answers

Step 1 of 5
Open this step
From a town to a graph
Practice · Predict, then look
Question
The four lands of Königsberg will be nodes, and the seven bridges edges. The degree of a node is the number of edges touching it. What is the degree of the island A?

Correct answer
5 ± 0.01
A number prediction counts as right within ± 0.01
Setup, choices and feedback
The Scene at this step
Bridges
7fixed
Town / Graph
Townfixed
Once the prediction is locked in, the Scene changes
Town / Graph
Graphfixed
The Scene then shows: 5 · Bridges touching the island A, its degree/nodes/town/outputs/degreeA
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Five bridges leave the island: two to the north bank, two to the south and one to the eastern land. In the graph each node is labelled with its degree.

Worked solution
1. Count the bridges touching the island: two to B, two to C, one to D.
2. $2 + 2 + 1 = 5$ ⁠.
Step 2 of 5
Open this step
Degrees
Practice · Calculate
Question
Add up the degrees of all four nodes. What is the total?

Correct answer
14 ± 0.01
Setup, choices and feedback
The Scene at this step
Bridges
7fixed
Town / Graph
Graph
Accepted within
± 0.01
Computed from the Scene at this step’s setting
The four degrees added: twice the bridges/nodes/town/outputs/degreeSum
Wrong answers it recognises
- 7 ± 0.01
  Misconception: Takes the sum of the degrees to be the number of edges, counting each edge once instead of twice.
  Feedback from the catalogue
  Every edge has two ends, and each end counts towards the degree of its node. So when you add up all the degrees, every edge is counted twice: the sum of the degrees is always twice the number of edges. In Königsberg $5 + 3 + 3 + 3 = 14 = 2 \times 7$ ⁠. Going back from the degrees to the edges, divide by $2$ ⁠.
Feedback for a right answer
$5 + 3 + 3 + 3 = 14$ ⁠: twice the seven bridges. Each bridge is counted once at each of its two ends.

Hint
The degrees are written beside the nodes.

Worked solution
1. The degrees: A 5, B 3, C 3, D 3.
2. $5 + 3 + 3 + 3 = 14$ ⁠.
3. Check: each bridge has two ends, $2 \times 7 = 14$ ⁠.
$7$ ⁠ is the number of bridges: each adds $2$ ⁠ to the total, not $1$ ⁠.
Step 3 of 5
Open this step
Handshakes
Practice · Choose
Question
Can there be a graph with exactly one node of odd degree?

Correct answer
- Correct No: the number of odd nodes is always even
Setup, choices and feedback
The Scene at this step
Bridges
7
Town / Graph
Graph
Choices
Shown in a random order.
- Correct No: the number of odd nodes is always even
- Wrong Yes, if you build it right
  Misconception: Thinks a graph can have an odd number of odd-degree nodes, such as exactly one.
  Feedback from the catalogue
  The sum of the degrees is twice the number of edges, so it is always even. Even nodes add an even amount to it, so the odd nodes together must add an even amount too, which happens only when there is an even number of them. A single odd node, or three, cannot exist. This is the handshake lemma.
- Wrong Only in a large enough graph
  Misconception: Thinks a graph can have an odd number of odd-degree nodes, such as exactly one.
  Feedback from the catalogue
  The sum of the degrees is twice the number of edges, so it is always even. Even nodes add an even amount to it, so the odd nodes together must add an even amount too, which happens only when there is an even number of them. A single odd node, or three, cannot exist. This is the handshake lemma.
Feedback for a right answer
The sum of the degrees is twice the number of edges, so it is even. One odd node would make it odd. Try any number of bridges in the Scene: always 0, 2 or 4 odd lands.

Worked solution
1. The sum of the degrees $= 2 \times$ ⁠ the number of edges, so it is even.
2. The even degrees add up to an even number.
3. So the odd degrees must add up to an even number too, which needs an even number of odd terms.
Step 4 of 5
Open this step
A new bridge
Practice · Reach the target
Question
Change the number of Bridges until the north bank B has degree 4, and press Check.

Goal
- 4 ± 0.01
  At the start of the step: 3
Setup, choices and feedback
The Scene at this step
Bridges
7
Town / Graph
Graph
Read from the Scene at
Bridges touching the north bank B/nodes/town/outputs/degreeB
One setting that reaches it
Bridges
8
Feedback for a right answer
The eighth bridge, west of the island, joins B to C, raising both their degrees by one. Every new bridge adds 1 to two nodes, so 2 to the total.

Feedback for a wrong answer
Not yet. Which added bridge touches B?

Worked solution
1. With 7 bridges B has degree 3.
2. The eighth bridge joins B to C, so with 8 bridges B has degree 4.
3. With 9 it is still 4: the ninth joins A to D.
Step 5 of 5
Open this step
Counting back
Practice · Calculate
Question
A graph of four nodes has degrees $3$ ⁠, $3$ ⁠, $2$ ⁠ and $2$ ⁠. How many edges does it have?

Correct answer
5 ± 0.01
Setup, choices and feedback
The Scene at this step
Bridges
5
Town / Graph
Graph
Accepted within
± 0.01
A fixed value in the question
Wrong answers it recognises
- 10 ± 0.01
  Misconception: Takes the sum of the degrees to be the number of edges, counting each edge once instead of twice.
  Feedback from the catalogue
  Every edge has two ends, and each end counts towards the degree of its node. So when you add up all the degrees, every edge is counted twice: the sum of the degrees is always twice the number of edges. In Königsberg $5 + 3 + 3 + 3 = 14 = 2 \times 7$ ⁠. Going back from the degrees to the edges, divide by $2$ ⁠.
Feedback for a right answer
$\dfrac{3 + 3 + 2 + 2}{2} = 5$ ⁠. It is exactly the graph of 5 bridges in the Scene.

Hint
Each edge is counted twice in the sum of the degrees.

Worked solution
1. The sum of the degrees: $3 + 3 + 2 + 2 = 10$ ⁠.
2. Each edge adds $2$ ⁠ to it.
3. $10 \div 2 = 5$ ⁠ edges.

Lesson 2 of 4 · About 25 minutes

Euler paths

Crossing every bridge once: why Königsberg has no such walk, Euler's rule about odd nodes, where a walk must start, and when it comes back to the start.

Open the lesson

The 6 steps and their answers

Step 1 of 6
Open this step
The puzzle
Practice · Predict, then look
Question
The people of Königsberg asked: can you walk through the town crossing each of the seven bridges exactly once? Predict.

Correct answer
- Correct No, there is no such walk
Setup, choices and feedback
The Scene at this step
Bridges
7fixed
Town / Graph
Townfixed
Choices
- Correct No, there is no such walk
- Wrong Yes, you just need the right order
  Misconception: Thinks a walk over all seven bridges of Königsberg exists and has just not been found yet.
  Feedback from the catalogue
  It is not a matter of searching: Euler proved there is no such walk. Every pass through a node in mid-walk enters by one edge and leaves by another, so a node that is neither the start nor the end needs an even degree. In Königsberg all four lands are odd, and only two can be the start and the end. So the best anyone can do is six bridges of the seven.
Once the prediction is locked in, the Scene changes
Town / Graph
Graphfixed
The Scene then shows: 0 · 1 when one walk crosses every bridge exactly once (an Euler path or circuit), else 0/nodes/town/outputs/walkable
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Euler proved in 1736 that there is none: all four lands have an odd degree. The walker on the graph crosses six bridges, and the seventh stays red.

Worked solution
1. The degrees: $5, 3, 3, 3$ ⁠, all odd.
2. Every node in mid-walk needs an even degree: you go in and out in pairs.
3. Only the start and the end can be odd, so at most two.
4. Four odd nodes: no walk.
Step 2 of 6
Open this step
The best walk
Practice · Calculate
Question
Without crossing any bridge twice, how many bridges at most can a walk cross in the Königsberg of 1736?

Correct answer
6 ± 0.01
Setup, choices and feedback
The Scene at this step
Bridges
7fixed
Town / Graph
Graph
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Bridges in the longest walk that crosses none twice (all of them when walkable)/nodes/town/outputs/longestWalk
Wrong answers it recognises
- 7 ± 0.01
  Misconception: Thinks a walk over all seven bridges of Königsberg exists and has just not been found yet.
  Feedback from the catalogue
  It is not a matter of searching: Euler proved there is no such walk. Every pass through a node in mid-walk enters by one edge and leaves by another, so a node that is neither the start nor the end needs an even degree. In Königsberg all four lands are odd, and only two can be the start and the end. So the best anyone can do is six bridges of the seven.
Feedback for a right answer
Six. Remove any one bridge and two nodes turn even, leaving two odd ones, and then there is an Euler path over the six that remain.

Worked solution
1. All seven bridges: impossible, with four odd nodes.
2. Leave out one bridge, and the two nodes at its ends turn even: two odd nodes are left.
3. With two odd nodes there is a walk over all the remaining edges: $6$ ⁠.
Step 3 of 6
Open this step
Fixing the town
Practice · Reach the target
Question
Add or remove Bridges until there is a walk that crosses every bridge exactly once, and press Check.

Goal
- 1 ± 0.01
  At the start of the step: 0
Setup, choices and feedback
The Scene at this step
Bridges
7
Town / Graph
Graph
Read from the Scene at
1 when one walk crosses every bridge exactly once (an Euler path or circuit), else 0/nodes/town/outputs/walkable
One setting that reaches it
Bridges
5
Feedback for a right answer
Each bridge you add or remove flips the parity of its two ends, so it brings the odd nodes down from four to two. Now the walker crosses them all.

Feedback for a wrong answer
Not yet. Count the odd nodes: more than two, and there is no walk.

Hint
You need 0 or 2 odd nodes.

Worked solution
1. With 7 bridges four nodes are odd.
2. Adding or removing a bridge between two odd nodes makes both even.
3. Any other number in the Scene, 5, 6, 8 or 9, works.
Step 4 of 6
Open this step
Where to start
Practice · Choose
Question
With 8 bridges the degrees are A 5, B 4, C 4, D 3, and there is a walk over them all. Where must it start?

Correct answer
- Correct At A or D, and it ends at the other
Setup, choices and feedback
The Scene at this step
Bridges
8
Town / Graph
Town
Choices
Shown in a random order.
- Correct At A or D, and it ends at the other
- Wrong On any land
  Misconception: Thinks an Euler path can start at any node, even when two nodes are odd.
  Feedback from the catalogue
  When exactly two nodes are odd, the path must start at one of them and end at the other. An odd node always has one edge left without a partner: if it is not the start or the end, after you enter it for the last time there is no way out. Only when every node is even can you start anywhere, and then the walk comes back to it: an Euler circuit.
- Wrong At B or C, the even lands
  Misconception: Thinks an Euler path can start at any node, even when two nodes are odd.
  Feedback from the catalogue
  When exactly two nodes are odd, the path must start at one of them and end at the other. An odd node always has one edge left without a partner: if it is not the start or the end, after you enter it for the last time there is no way out. Only when every node is even can you start anywhere, and then the walk comes back to it: an Euler circuit.
Feedback for a right answer
An odd node always has one edge without a partner, so it must be the start or the end. Open the graph: the walker sets out from A and finishes at D.

Worked solution
1. The odd nodes: A (5) and D (3).
2. A node in mid-walk is entered and left in pairs, so it is even.
3. A and D must be the start and the end.
Step 5 of 6
Open this step
A circuit
Practice · Reach the target
Question
An Euler circuit is a walk that crosses every edge once and returns to where it began. Change the Bridges until there is one, and press Check.

Goal
- 1 ± 0.01
  At the start of the step: 0
Setup, choices and feedback
The Scene at this step
Bridges
8
Town / Graph
Graph
Read from the Scene at
1 when that walk can end where it began (no odd lands), else 0/nodes/town/outputs/circuit
One setting that reaches it
Bridges
9
Feedback for a right answer
With 9 bridges the degrees are $6, 4, 4, 4$ ⁠, all even, and the walker returns to where it set out.

Feedback for a wrong answer
Not yet. A walk that ends elsewhere is an Euler path, not a circuit. Every degree must be even.

Hint
To return to the start, no node can be odd.

Worked solution
1. A circuit needs 0 odd nodes.
2. With 8 bridges A and D are odd; the ninth bridge joins exactly those two.
3. Set Bridges to 9.
Step 6 of 6
Open this step
Euler's rule
Practice · Choose
Question
A graph is connected. When does it have a walk crossing every edge exactly once?

Correct answer
- Correct When it has 0 or 2 odd nodes
Setup, choices and feedback
The Scene at this step
Bridges
9
Town / Graph
Graph
Choices
Shown in a random order.
- Correct When it has 0 or 2 odd nodes
- Wrong When the number of odd nodes is even
  Misconception: Thinks any even number of odd nodes allows an Euler path, four included.
  Feedback from the catalogue
  Euler’s rule is 0 or 2, not “an even number”. Every odd node must be the start or the end of the walk, and one walk has only one start and one end. With four odd nodes, as in Königsberg, you need two separate walks. (The number of odd nodes is always even, so “even” says nothing.)
- Wrong Only when no node is odd
  Feedback
  0 odd nodes give a circuit, but 2 give a path too, starting at one and ending at the other.
Feedback for a right answer
That is Euler’s theorem: 0 odd nodes, a circuit; 2, a path from one to the other; more, no walk. The computer in the Scene finds the walk with Hierholzer’s algorithm.

Worked solution
1. Every odd node must be an end of the walk.
2. A path has two ends, and a circuit none.
3. So 0 or 2.
The number of odd nodes is always even, but with 4, as in Königsberg, there is no walk.

Lesson 3 of 4 · About 25 minutes

Routing packets

The internet as a graph of routers: the shortest route, detours when a cable is cut, a cut that splits the network, and packets that spread over several routes and arrive out of order.

Open the lesson

The 6 steps and their answers

Step 1 of 6
Open this step
The shortest route
Practice · Calculate
Question
The message travels from the laptop to the server by the shortest route, the one that glows. Through how many routers does it pass?

Correct answer
4 ± 0.01
Setup, choices and feedback
The Scene at this step
Links cut
0fixed
One message / Packets
One messagefixed
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Network: routers the message passes through on the shortest route, 0 with no route/nodes/mesh/outputs/routers
Wrong answers it recognises
- 5 ± 0.01
  Misconception: Confuses the links on a route with the routers on it, off by one (counting fence posts as gaps).
  Feedback from the catalogue
  A route is a chain: link, router, link, router, and so on to the end. Between the laptop and the server there is one more link than there are routers, as a fence has one more gap than posts between its two ends. A route of five links passes through four routers. Before counting, decide exactly what you are counting: edges or nodes.
Feedback for a right answer
Four routers, and five cables between them. Each router reads the destination address and sends the message on to the next neighbour on the way.

Hint
Count the boxes on the way, without the laptop and the server.

Worked solution
1. The route: laptop, four routers, server.
2. Between six stops there are five links.
3. The routers are the stops in between: $4$ ⁠.
$5$ ⁠ is the number of cables: one more than the routers.
Step 2 of 6
Open this step
A cut cable
Practice · Predict, then look
Question
We will cut the middle cable of the route the message now takes. What will happen to the next message?

Correct answer
- Correct It will go another way, a little longer
Setup, choices and feedback
The Scene at this step
Links cut
0fixed
One message / Packets
One messagefixed
Choices
- Correct It will go another way, a little longer
- Wrong It will not arrive
  Misconception: Thinks that cutting a link on the route loses the message, as if a network had only one path.
  Feedback from the catalogue
  The internet is built as a mesh with many routes between any two points. When a link is cut, the routers notice and work out the shortest route again over what is left, and the message takes a detour, a little longer. The network comes apart only when every link joining its two halves is cut.
- Wrong It will go another way, a shorter one
  Feedback
  If there were a shorter way, the message would have taken it already: that was the shortest.
Once the prediction is locked in, the Scene changes
Links cut
1fixed
The Scene then shows: 1 · Network: 1 while a route from the laptop to the server is left, 0 when the cuts sever it/nodes/mesh/outputs/reachable
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
The routers worked out the shortest route again without the cut cable, and the message goes round. The new way is about 3% longer.

Worked solution
1. The mesh has many routes between the laptop and the server.
2. The cut deletes one edge of the graph.
3. The shortest route in the remaining graph can only be as long or longer, and here it is longer, since the old one was the single shortest.
Step 3 of 6
Open this step
Cutting the server off
Practice · Reach the target
Question
Raise Links cut until the server is completely cut off from the laptop, and press Check.

Goal
- 0 ± 0.01
  At the start of the step: 1
Setup, choices and feedback
The Scene at this step
Links cut
0
One message / Packets
One message
Read from the Scene at
Network: 1 while a route from the laptop to the server is left, 0 when the cuts sever it/nodes/mesh/outputs/reachable
One setting that reaches it
Links cut
4
Feedback for a right answer
Four cuts, with 18 links still whole, and yet there is no way through: every link crossing from the left half of the mesh to the right has been cut.

Feedback for a wrong answer
Not yet. While the message gets through, there is a detour. Keep cutting.

Worked solution
1. Each cut hits a link on the current shortest route, and the message goes round.
2. Only four links join the left half of the mesh to the right.
3. After the fourth cut all of them are gone: set Links cut to 4.
Step 4 of 6
Open this step
A cut
Practice · Choose
Question
After four cuts, 18 of the 22 links are left, and yet the server is cut off. Why?

Correct answer
- Correct Every link joining the two parts of the mesh is cut, and all that is left joins only within a part
Setup, choices and feedback
The Scene at this step
Links cut
4
One message / Packets
One message
Choices
Shown in a random order.
- Correct Every link joining the two parts of the mesh is cut, and all that is left joins only within a part
- Wrong A network survives only three failures
  Feedback
  There is no such fixed number. What matters is which links were cut: four others would cut nothing off.
- Wrong The remaining routes are too long for the message
  Feedback
  There are no remaining routes: no path at all leads from the laptop to the server.
Feedback for a right answer
A set of links without which the graph falls into two parts is called a cut. Here the smallest cut between the laptop and the server is four links, so four cuts in the right places part them.

Worked solution
1. For a way through, at least one link must cross from the laptop’s part to the server’s.
2. There are exactly four such links, and all are cut.
3. The other links join nodes within one part, so they do not help.
Step 5 of 6
Open this step
Packets
Practice · Predict, then look
Question
The message is split into packets, six numbered packets, sent one after another. Will they all take the same route?

Correct answer
- Correct No, they will spread over several routes
Setup, choices and feedback
The Scene at this step
Links cut
0fixed
One message / Packets
One messagefixed
Choices
- Correct No, they will spread over several routes
- Wrong Yes, all by the shortest way
  Misconception: Thinks a message's packets all follow one route and arrive in the order they were sent.
  Feedback from the catalogue
  Each packet is routed on its own. Routers spread packets over several routes of similar length, so as not to overload one, so the packets of one message travel different ways and arrive in a different order from the one they were sent in. Each packet carries a sequence number, and the server puts them in order by it and asks again for any that did not arrive.
Once the prediction is locked in, the Scene changes
One message / Packets
Packetsfixed
The Scene then shows: 4 · Network: distinct routes the message's packets actually take/nodes/mesh/outputs/packetRoutes
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
The packets spread over four routes of similar length, so as not to overload one. Each router decides for each packet separately.

Worked solution
1. Each packet is a small message with its own destination address.
2. Each router decides for each packet where to send it, by load and by distance.
3. So the packets of one message can travel different ways: here four.
Step 6 of 6
Open this step
Putting it together
Practice · Choose
Question
The packets reached the server in a different order from the one they were sent in. How does the server put the message together?

Correct answer
- Correct By the sequence number each packet carries
Setup, choices and feedback
The Scene at this step
Links cut
0
One message / Packets
Packets
Choices
Shown in a random order.
- Correct By the sequence number each packet carries
- Wrong By arrival order, since they arrive in the order sent
  Misconception: Thinks a message's packets all follow one route and arrive in the order they were sent.
  Feedback from the catalogue
  Each packet is routed on its own. Routers spread packets over several routes of similar length, so as not to overload one, so the packets of one message travel different ways and arrive in a different order from the one they were sent in. Each packet carries a sequence number, and the server puts them in order by it and asks again for any that did not arrive.
- Wrong By the route each packet took
  Feedback
  The server does not know which route a packet took, nor does it matter. What counts is the number on it.
Feedback for a right answer
Each packet is numbered, and the server puts them in order by the numbers and asks again for any missing. It is part of the TCP protocol.

Worked solution
1. Different routes take different times, so the order gets mixed up.
2. Each packet carries a sequence number.
3. The server sorts by the numbers, and knows from a missing number that a packet has yet to arrive.

Lesson 4 of 4 · About 25 minutes

Ranking pages

How a search engine knows what matters: the random surfer, PageRank as a share of time on each page, why a link from an important page is worth more, the damping factor, and visits that settle.

Open the lesson

The 6 steps and their answers

Step 1 of 6
Open this step
The random surfer
Practice · Predict, then look
Question
Right now the surfer never clicks links, it only jumps to a random page, so all eight pages share one rank. When Chance of clicking a link goes up to 85%, which page will rise to the top?

Correct answer
- Correct The hub, which nearly every page links to
Setup, choices and feedback
The Scene at this step
Pages linking to yours
0fixed
Chance of clicking a link
0 %fixed
Ranks / Random surfer
Ranksfixed
Choices
- Correct The hub, which nearly every page links to
- Wrong The blog, which gives the most links
  Feedback
  Links going out do not lift a page; they lift the pages it links to.
- Wrong Your page, since the surfer starts there
  Feedback
  The starting point is forgotten after a few moves. What counts is where the links lead.
Once the prediction is locked in, the Scene changes
Chance of clicking a link
85 %fixed
The Scene then shows: 31.43 · The hub’s PageRank, percent/nodes/web/outputs/hubRank
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
The hub has seven links in, from every other page, and climbs to about a third of the rank. Every click on a link moves the surfer to a linked page, so a page many pages link to gets more visits.

Worked solution
1. PageRank is the share of its time the random surfer spends on each page.
2. When it clicks links, it lands on pages that are linked to.
3. All seven other pages link to the hub, so it lands there most.
Step 2 of 6
Open this step
Quiet links
Practice · Predict, then look
Question
No page links to your page, and its rank is about 1.9%. Now the blog, the photos and the shop, three quiet pages, will link to it. Where will its rank go?

Correct answer
- Correct It will rise a little, to about 5%
Setup, choices and feedback
The Scene at this step
Pages linking to yours
0fixed
Chance of clicking a link
85 %fixed
Ranks / Random surfer
Ranksfixed
Choices
- Correct It will rise a little, to about 5%
- Wrong It will rise a lot, past 10%: three links is a lot
  Misconception: Thinks every link counts the same in PageRank, so more links always beat fewer.
  Feedback from the catalogue
  PageRank does not count links, it weighs them. Each page splits its own rank among the links it gives, so a link from an important page is worth far more than a link from a page nobody visits. One link from the hub, whose rank is about a third of the whole web, lifts your page more than three links from quiet pages together.
Once the prediction is locked in, the Scene changes
Pages linking to yours
3fixed
The Scene then shows: 5.064 · The reader’s page’s PageRank, percent/nodes/web/outputs/yourRank
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
About 5.1%. These three pages have little rank of their own, and each splits it among several links, so they pass on little.

Worked solution
1. A link passes on $d \cdot \dfrac{PR}{L}$ ⁠: part of the giving page’s rank, divided by its number of links.
2. The blog, the photos and the shop have only a few per cent of rank each.
3. So the three together pass on only a few per cent.
Step 3 of 6
Open this step
A link from the hub
Practice · Predict, then look
Question
Three quiet pages already link to your page. Now the hub will add one link. Will your page gain more or less from it than it gained from the three links?

Correct answer
- Correct More
Setup, choices and feedback
The Scene at this step
Pages linking to yours
3fixed
Chance of clicking a link
85 %fixed
Ranks / Random surfer
Ranksfixed
Choices
- Correct More
- Wrong Less: one link against three
  Misconception: Thinks every link counts the same in PageRank, so more links always beat fewer.
  Feedback from the catalogue
  PageRank does not count links, it weighs them. Each page splits its own rank among the links it gives, so a link from an important page is worth far more than a link from a page nobody visits. One link from the hub, whose rank is about a third of the whole web, lifts your page more than three links from quiet pages together.
Once the prediction is locked in, the Scene changes
Pages linking to yours
4fixed
The Scene then shows: 11.94 · The reader’s page’s PageRank, percent/nodes/web/outputs/yourRank
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
From 5.1% to 11.9%: more than twice what the three links gave. The hub holds about a third of the rank, and even split among four links, your share is large.

Worked solution
1. The three quiet links lifted the page from about 1.9% to about 5.1%: about $3$ ⁠ points.
2. The hub passes $0.85 \times \dfrac{33}{4} \approx 7$ ⁠ points through each of its four links.
3. One link from the hub is worth more than the three quiet ones together.
Step 4 of 6
Open this step
Climbing
Practice · Reach the target
Question
Change Pages linking to yours until your page is in second place, behind only the hub, and press Check.

Goal
- 2 ± 0.01
  At the start of the step: 7
Setup, choices and feedback
The Scene at this step
Pages linking to yours
0
Chance of clicking a link
85 %fixed
Ranks / Random surfer
Ranks
Read from the Scene at
The reader’s page’s place in the ranking, 1 the highest (1 + pages ranked strictly above it)/nodes/web/outputs/yourPlace
One setting that reaches it
Pages linking to yours
5
Feedback for a right answer
With links from the hub and the news site your page reaches about 16%, above the news site itself. Links from important pages make a page important.

Feedback for a wrong answer
Not yet. Add links, and notice which page each one comes from.

Hint
Which pages would you want linking to you?

Worked solution
1. The links come in a fixed order: three quiet pages, then the hub, then the news site.
2. With four links your page is at about 11.9%, still behind the news site and the wiki.
3. With the fifth, from the news site, it is at about 16.1%, second only to the hub: set it to 5.
Step 5 of 6
Open this step
What a link passes on
Practice · Calculate
Question
The hub links to four pages, and the surfer follows a link on 85% of its moves. Read the hub’s rank off the board. How many percentage points does each of its links pass on?

Correct answer
7.116 ± 0.15
Setup, choices and feedback
The Scene at this step
Pages linking to yours
4fixed
Chance of clicking a link
85 %fixed
Ranks / Random surfer
Ranks
Accepted within
± 0.15
Computed from the Scene at this step’s setting
The hub’s PageRank, percent/nodes/web/outputs/hubRank
Wrong answers it recognises
- 8.372 ± 0.15
  Misconception: Forgets that the surfer follows a link only part of the time (the damping factor) when working out what a link passes on.
  Feedback from the catalogue
  The random surfer clicks a link on only 85% of its moves; on the rest it jumps to a random page. So a page passes on through its links only $0.85$ ⁠ of its rank, split among them: $d \cdot \dfrac{PR}{L}$ ⁠. The remaining 15% is shared equally by every page, which is what gives even a page with no links into it a small rank.
- 28.46 ± 0.15
  Misconception: Thinks each of a page's links passes on the page's whole rank, instead of a share of it.
  Feedback from the catalogue
  A page does not multiply its rank by adding links; it shares it out. The surfer on a page with four links out picks one of them, so each link gets a quarter of the flow. A page that links to everyone gives each of them very little.
Feedback for a right answer
$0.85 \times \dfrac{33.5}{4} \approx 7.1$ ⁠ points a link. One of them reaches your page.

Hint
$d \cdot \dfrac{PR}{L}$ ⁠, with $d = 0.85$ ⁠ and $L = 4$ ⁠.

Worked solution
1. The hub’s rank: about 33.5%.
2. On 85% of moves the surfer leaves it by a link, choosing one of four.
3. $0.85 \times 33.5 \div 4 \approx 7.1$ ⁠.
Without the $0.85$ ⁠ you get about $8.4$ ⁠; without dividing by four, about $28$ ⁠.
Step 6 of 6
Open this step
The surfer settles
Practice · Predict, then look
Question
The random surfer has made only a few clicks, and the visit bars beside the plinths are far from the ranks. What will happen to the bars when it has made twenty thousand clicks?

Correct answer
- Correct They will settle at the height of the plinths
Setup, choices and feedback
The Scene at this step
Pages linking to yours
4fixed
Chance of clicking a link
85 %fixed
Ranks / Random surfer
0.3 (Ranks → Random surfer)fixed
Choices
- Correct They will settle at the height of the plinths
- Wrong They will keep jumping, since the surfer is random
  Misconception: Thinks a random walk cannot give a definite answer: its share of visits will keep jumping however long it runs.
  Feedback from the catalogue
  Each of the surfer’s moves is random, but over many moves the chance evens out. The share of visits to each page settles towards a fixed value, the long-run chance of being there, and that is exactly the PageRank. After ten clicks the bars jump about; after twenty thousand they hardly move. This is the law of large numbers.
Once the prediction is locked in, the Scene changes
Ranks / Random surfer
Random surferfixed
The Scene then shows: 0.3331 · Largest visits-to-rank gap, points/nodes/web/outputs/gap
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
After twenty thousand clicks the largest gap between a page’s share of visits and its rank is under a percentage point. PageRank is exactly the share of time the surfer spends on each page in the long run.

Worked solution
1. Each move is random, but the long-run chance of being on each page is fixed.
2. The more moves, the closer each page’s share of visits comes to that chance.
3. That chance is the PageRank, so the bars settle at the height of the plinths.

Across the unit · 12 misconceptions

Misconception catalogue

Each common mistake this unit recognises, in a few words. Open one for what the learner reads when an answer matches it, and where it is asked.

Index

Nodes and edges

From a town to a graph

Question

Correct answer

The Scene at this step

Once the prediction is locked in, the Scene changes

Worked solution

Degrees

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

Handshakes

Question

Correct answer

The Scene at this step

Choices

Worked solution

A new bridge

Question

Goal

The Scene at this step

One setting that reaches it

Worked solution

Counting back

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

Euler paths

The puzzle

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Worked solution

The best walk

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Worked solution

Fixing the town

Question

Goal

The Scene at this step

One setting that reaches it

Hint

Worked solution

Where to start

Question

Correct answer

The Scene at this step

Choices

Worked solution

A circuit

Question

Goal

The Scene at this step

One setting that reaches it

Hint

Worked solution

Euler's rule

Question

Correct answer

The Scene at this step

Choices

Worked solution

Routing packets

The shortest route

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint