Skip to content
Tutorials Center
My learning

Topics

Lesson 60 of 68 ยท Projects

Project: Social Network Analyzer

Model a small social network as a graph and compute degrees, components, shortest paths and centrality by hand, then draw the result with matplotlib.

Every social network, from a classroom to a continent, is a graph: people are vertices and friendships are edges. The questions people ask about such networks are graph questions. Who knows the most people? Is everyone connected to everyone else, even indirectly? How many introductions separate two strangers? Who sits in the middle, so that removing them would split the group?

In this project you will build a small analyzer using only dictionaries, sets and a few lines of matplotlib. There is no graph library on purpose: each measurement is a short function you can read and check. The network is a fictional club of fourteen people with two friendly clusters, a loner pair and a few well-placed bridges.

You should know the terms from Graphs: Terms and Representations, the search algorithms from Paths, Cycles and Connectivity and the weighted-graph ideas in Shortest Paths, Matching and Flows.

What the analyzer measures

Degree How many friends each person has.
Components Which groups are cut off from each other.
Distance Fewest introductions between two people.
Centrality Who sits in the middle of the action.
1 / 2

Step 1: build the graph

The network is stored as an adjacency dictionary that maps each person to the set of their friends. Friendship is mutual, so the graph is undirected and every edge must be recorded twice, once in each direction. A helper function does this so we cannot forget one side.

Using sets rather than lists has two benefits: adding the same friendship twice changes nothing, and checking whether two people are friends is a quick lookup. By the handshake lemma, the sum of all degrees equals twice the number of edges, so we use that identity as a built-in sanity check.

Python Building the network and its degrees

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are 13 people and 14 friendships. Seven people (Ben, Cleo, Dev, Eli, Fay, Gus and Hana) have 3 friends each, Ana and Ivy have 2, Jon, Kim and Lou have 1, and Max has none. The average degree is 28 divided by 13, about 2.15, and the density (the fraction of all possible pairs that are friends) is 14 out of 78, about 0.179. Real social networks are usually sparse like this: each person knows a tiny fraction of everyone.

Notice that Max appears in PEOPLE but in no friendship. Building the dictionary from a list of people, not only from the edges, keeps isolated vertices in the graph. Building it from edges alone would silently lose them.

A connected component is a maximal group of people who can all reach each other through chains of friends. Breadth-first search (BFS) from one person visits exactly their component, so repeating BFS from every unvisited person lists all components.

BFS explores in layers: first the start, then friends of the start, then friends of friends, and so on. Because it expands one layer at a time, the layer number at which a person is first reached is also their shortest distance from the start. That gives us the second tool we need, distances, for free.

Python Components and distances with BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The club splits into three components: a main group of ten people from Ana to Jon, the pair Kim and Lou, and Max alone. Ana reaches Ben and Cleo in one step, Dev in two, Eli in three, Fay and Gus in four, Hana in five, Ivy in six and Jon in seven. Kim never appears in Ana's distance table, because no chain of friendships joins them.

The diameter of a component is the largest shortest distance between any two of its members. Here it is 7, between Ana and Jon. The long tail Hana, Ivy, Jon stretches this club out: it is far from a "small world".

Step 3: who is in the middle?

Degree counts friends, but it misses position. Someone with two friends can still be vital if those friends lead to two different halves of the network. Two classic measures capture position, and we compute both by hand.

Closeness centrality rewards being near everyone. For a person v in a component of n people, take the sum S of the distances from v to the others. Closeness is (n โˆ’ 1) / S, which is 1 when v is a direct friend of everyone and falls as distances grow. We only measure within the person's own component.

Betweenness centrality counts how often a person lies on shortest paths between other pairs. To compute it, for every pair (s, t) we count the shortest paths and note which people appear inside them. A person who appears on many shortest paths is a bridge. We use a straightforward method that runs BFS from each start, counts shortest paths with a dictionary, and walks them back. It is easy to read, and it is plenty fast for a club of fourteen.

The idea behind counting: let sigma[v] be the number of shortest paths from the start to v. When BFS finds a neighbor w one layer farther than v, then every shortest path to v extends to a shortest path to w, so sigma[w] increases by sigma[v].

Python Closeness and betweenness by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table is sorted by betweenness. Eli (20.0), Dev (18.0) and Hana (14.0) come first, followed by Ivy (8.0), the twins Fay and Gus (7.5 each) and the pair Ben and Cleo (3.5 each). These people sit at junctions on the long chain through the network, even though their degree is only 2 or 3. Eli also has the best closeness in the main group (0.474), because he is in the middle of the chain. Kim and Lou show closeness 1.000 only because each is a direct friend of everyone in their tiny component; Max gets 0.000 because there is nobody to measure. This is why closeness is only meaningful within a component.

Ana and Jon sit at the two ends of the chain and score 0: no shortest path between two other people needs to pass through them. Kim, Lou and Max score 0 as well.

Step 4: does it match a second method?

A measurement function that is wrong looks just as confident as a right one, so verify. For betweenness we can check against a completely different, slower method: enumerate all shortest paths for every pair by brute force and count how often each person appears inside them, weighted by the fraction of shortest paths that pass through the person. This is the definition of betweenness, written directly.

Python Checking betweenness against the definition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The enumeration prints the same values as the faster method: Eli 20.0, Dev 18.0, Hana 14.0, Ivy 8.0, Fay and Gus 7.5, Ben and Cleo 3.5. The two Eli to Ana paths (through Dev, then Ben or Cleo) show why betweenness uses fractions: when two shortest paths exist, each middle person gets credit 1/2 for that pair.

Step 5: draw the result

A network is easiest to understand as a picture. Real tools use force-directed layouts, but a layout can be as simple as placing each vertex at fixed coordinates we choose. Here we place the main group left to right along its chain, put the loner pair and Max below, and size each circle by betweenness so the bridges stand out. Edges are drawn as lines first, then vertices on top, then labels.

The result is a PNG figure in the output.

Python Drawing the network

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The picture makes the story visible at once: a left cluster around the triangle Ana, Ben, Cleo, a right cluster around the triangle Eli, Fay, Gus, a thin chain through Dev and Hana, Ivy and Jon hanging off the end, a separate pair, and Max alone. If Eli left the club, the left cluster would be cut off from the right one, so Eli is a cut vertex, a fact the numbers hinted at and the drawing makes obvious.

Ideas to extend the project

  • Add a function that finds all cut vertices by removing each person and counting components again.
  • Compute the clustering coefficient: for each person, the fraction of pairs of their friends who are also friends of each other.
  • Make friendships weighted (hours spent together per week) and use Dijkstra's algorithm to find the strongest chain.
  • Suggest friends: for each person, rank non-friends by the number of friends they have in common.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the build step create the dictionary from the list of people, not only from the edges?

    Building from edges alone drops isolated vertices such as Max. Starting from the list of people keeps them with an empty set of friends.
  2. 2. In BFS, what does the layer in which a person is first reached tell you?

    BFS expands one layer at a time, so the first time a vertex is reached is along a path with the fewest edges.
  3. 3. What does betweenness centrality measure?

    Betweenness counts, for every pair of other people, the fraction of their shortest paths that pass through the person, and sums those fractions.
  4. 4. The sum of all degrees in the club equals 28. How many friendships are there?

    By the handshake lemma, the degree sum is twice the number of edges, so there are 28 / 2 = 14.
  5. 5. Why is a vertex with high betweenness but low degree possible?

    A bridge person may have only two or three friends, yet if they lead to different groups, many shortest paths must pass through them.

Summary

  • Store an undirected social network as a dictionary of sets, adding every friendship in both directions, and start from the list of people so isolated ones are kept.
  • The handshake lemma (degree sum = 2 ร— edges) is a cheap correctness check.
  • BFS finds components and shortest distances in one pass; the diameter is the largest distance within a component.
  • Closeness rewards being near everyone; betweenness rewards sitting on shortest paths. Both are short functions on top of BFS.
  • Check a clever algorithm against a slow, obviously correct definition, and draw the graph to see what the numbers mean.

Next: Project: Modular Arithmetic and Toy RSA, a return to number theory.