Degrees of separation
In a small network of friends, find how many links separate two people: a friend is 1 link away, a friend of a friend 2. A shortest-path search spreads out from one person, nearest friends first, and finds the fewest links, or shows that someone cannot be reached at all.
Core concept
A network of friends is a graph; when every link counts as 1, the shortest path is the fewest links, found by settling people in order of how many links away they are, nearest first
Topic: Algorithms
A group of friends can be drawn as a graph: each person is a node, and a line joins two people who are friends. Your friends are 1 link away from you; their friends, whom you may not know, are 2 links away. How many links separate two people is called their degree of separation. People say that almost anyone in the world is only about six links from anyone else. A computer finds the fewest links by searching outward from one person: first everyone 1 link away, then everyone 2 links away, and so on, never visiting anyone twice. In this lab every link counts as 1, so the shortest path search settles people in that order, nearest first. If no chain of links leads to someone, they cannot be reached.
What you will learn
- Draw a network of friends as a graph of nodes and links.
- Find the degree of separation between two people.
- Explain why a search that goes nearest first finds the fewest links.
- Recognise a person who cannot be reached.
Before you start
- Know what a graph is: points (nodes) joined by lines (links).
Materials
- A notebook to draw the network
Equipment
- None
Procedure
- Find the links from Aarav to Dipa.
- Find the person farthest from Aarav.
- Try to reach Hari, who has no friends in the group yet.
- Answer the practice challenges.
How this simulation is simplified
- Friendship goes both ways, and every link counts as 1.