Hidden communities: finding the groups inside a network and proving they're real

Data: Part A uses a real network — Zachary’s Karate Club, the founding example of community detection, which ships inside the networkx library (no download). Part B uses a synthetic graph with planted communities, generated locally by data/make_data.py (seeded, reproducible). Free, no signup, no GPU. Synthetic is the right call for Part B: to score a community-detection method you need to know the true groups, and only a graph you built yourself gives you that.

Before you start

New to this? Two minutes of vocabulary, because the whole project turns on it.

A network (or graph) is dots joined by lines: nodes (people, computers, proteins) and edges (a friendship, a message, an interaction). Networks show up everywhere, and one question comes up again and again:

Community detection — are there groups in this network that talk to each other far more than to outsiders? A community is a cluster of nodes densely wired inside and sparsely wired to the rest. Finding those clusters, using only the edges, is community detection.
Centrality — which nodes are “important”? Two flavours you’ll use: degree (how many connections a node has) and betweenness (how often a node sits on the shortest path between others — a broker or bridge).
Ground truth — the real answer, when you happen to know it. Zachary’s karate club really did split into two factions, and that split was recorded, so we can check whether the network structure alone predicts it.

A tiny example — picture two friend groups with one person who knows people in both. Degree centrality says that person is well-connected; betweenness says they’re the bridge; community detection puts everyone else cleanly into one group or the other and leaves that bridge as the interesting, ambiguous case.

What you’ll learn: to load a network, find its important nodes and its hidden groups with networkx, and — crucially — to validate the groups you found against a known answer instead of just trusting a pretty picture.

New to Python? Section 4 (“Where to write and run code”) starts from zero.

1. The Brief

You’ll take a real social network — 34 members of a 1970s karate club, and who was friends with whom — and, using nothing but the friendship edges, cut it into two groups. Then you’ll compare your cut to what actually happened: the club split in two after a fight between the instructor and the president, and the real sides were recorded. Your structural guess matches the real split with about 94% accuracy. Then, in Part B, you’ll face a bigger network where the groups are hidden and you’re not even told how many there are, and you’ll recover them and prove how well you did with a proper score.

This is the everyday reality of network analysis — org charts from email traffic, fraud rings from transactions, topics from citation graphs, protein modules from interaction data. The trap is stopping at a colourful graph and asserting the groups are real. The skill that matters is finding structure and then validating it: scoring your communities against ground truth (or a planted answer) so “I found four groups” becomes “I found four groups that match the truth with an adjusted Rand index of 0.93.” One is a vibe; the other is a result.

2. Difficulty & time

Difficulty 5 / 10. It’s about level with #reorder-point-trap and #accuracy-is-lying (both difficulty 5): each chains several steps around a genuinely non-obvious idea (here: structure predicts a real split, and you must score that claim, not eyeball it), with one main tool and a fully guided Part A. It’s harder than the difficulty-3 builds #silent-row-loss and #idempotent-loads, which each turn on a single mechanic; this project asks you to combine centrality, a graph-cut, community detection, and a validation metric, and Part B is open-ended (you don’t know how many communities exist). It stays below 7–8 because you use well-known library algorithms rather than designing one, and there’s no scale or second-system constraint. Anchored to the rubric’s level-5 band and those four named ledger projects (G10).

Time is separate from difficulty: the scripts run in about a second (measured Part A wall-clock 1.46s). Part A is roughly 60 minutes of reading and running; Part B is 2–3 hours of your own work.

3. What you’ll be able to do after

Load a network into networkx from an edge list and compute degree and betweenness centrality to find its key nodes.
Split a network into communities with a graph algorithm — both a two-way cut (Kernighan–Lin) and a general method that finds the number of groups itself (modularity maximisation).
Validate communities against a known answer with the adjusted Rand index, and say what the score means (0 = random, 1 = perfect) rather than trusting a plot.
Recover hidden structure when you don’t know how many groups there are, and report how good the recovery is.

The finished result

By the end of Part A you’ll have cut a real social network into two groups from its friendships alone — and scored that cut against what actually happened:

34 members, 78 friendships   ->   two communities of 17 and 17
key members   by degree: 33, 0, 32     by betweenness: 0, 33, 32
accuracy vs the real split: 0.941     adjusted Rand index (ARI): 0.772

The friendship structure alone recovers the real faction split almost perfectly; in Part B that same skill recovers four hidden teams at an adjusted Rand index of 0.93.

4. Prereqs & time box

You can write a for loop and a function, and you’ve seen a pandas DataFrame. No graph theory or network-science background is assumed — the vocabulary is in the primer above, and each networkx call is explained on first use. You do not implement any algorithm from scratch; you call and interpret well-tested ones.

Where to write and run code

Two ways to run this project — pick either:

In your browser (no install). If the project page shows a ▶ Run button, click it to run Part A right here — nothing to set up. Part A uses pandas, numpy, networkx, and scikit-learn, which run in the browser.
On your computer. The one-time setup — installing Python, downloading the code from the course site (no GitHub, no git), opening a terminal, creating a virtual environment, installing the requirements, and running Part A step by step — is covered once in Start Here. Come back here once python -c "import networkx" runs without error. Part B (writing your own solution) needs this local setup.

Time box

Part A — Guided Build: 45–75 minutes. Hard cap 90.
Part B — Your Turn: 2–3 hours. Hard cap 4.

5. Setup & data

Part A (real). One command reads Zachary’s Karate Club from networkx and writes it locally (git-ignored, never committed):

python data/get_data.py

That writes data/karate_edges.csv (the friendships) and data/karate_truth.csv (the real faction each member joined).

Part B (synthetic). One command generates the planted-community graph (seeded, byte-for-byte reproducible):

python data/make_data.py

That writes data/sbm_edges.csv — a company messaging graph with hidden teams and shuffled node ids, so you can’t read the groups off the numbering; you recover them from the edges. The true teams are documented in data/make_data.py and used by the grader — not handed to you.

6. Part A — Guided Build

Run the full script and read along:

python data/get_data.py           # once
python part_a/analyze_network.py

Prefer the browser? If this page has a ▶ Run button, click it instead of the command above — Part A runs in your browser with nothing to install. The STEP output and every checkpoint below are identical either way.

The full, commented script is in part_a/analyze_network.py. Every networkx function is linked in the “Functions you’ll meet” table at the end of this section.

Step 1 — Load the real network and its recorded outcome.

Checkpoint: 34 members, 78 friendships; the real split is 17 / 17 (Mr. Hi’s side vs the Officer’s side).

Step 2 — Find the key members with two kinds of centrality.

Checkpoint: by degree, the top nodes are 33, 0, 32; by betweenness, 0, 33, 32. Node 0 (the instructor, “Mr. Hi”) and node 33 (the president, the “Officer”) top both — the two people the club actually split around.

Step 3 — Cut the graph into two communities, using the edges only. Kernighan–Lin bisection ignores the faction labels and splits on structure alone.

Checkpoint: two communities of 17 and 17.

Step 4 — Score the cut against what really happened.

Checkpoint: accuracy 0.941, adjusted Rand index 0.772. The friendship graph alone recovers the real split almost perfectly. The two or three it gets “wrong” are members whose real-life choice genuinely surprised the researchers — the method isn’t buggy; those people were ambiguous.

Why this and not that

Why score against ground truth instead of trusting the split? Any algorithm will hand you some partition — it always “finds communities,” even in a random graph. The only way to know the groups mean something is to check them against an answer you didn’t feed the algorithm. Here that’s the recorded split; in Part B it’s the planted labels. Without that check you have a picture, not a finding.
Why both centrality and community detection? They answer different questions. Centrality finds individuals who matter (the bridge, the hub); community detection finds groups. Reporting one when the question is the other is a common mix-up — the broker with high betweenness is often the node the group split leaves ambiguous.
Why the adjusted Rand index, not plain accuracy? Accuracy needs you to line up “your group 1” with “their group A”, which is awkward past two groups and impossible when the counts differ. ARI compares two groupings directly, is corrected for chance (0 means no better than random), and doesn’t care how you numbered the groups — so it’s the metric that still works in Part B, where you find your own number of groups.

Functions you’ll meet (and where to read more)

Function	What it does here	Docs
`nx.from_pandas_edgelist`	Build a graph from an edge-list DataFrame	from_pandas_edgelist
`nx.degree_centrality`	Rank nodes by how many neighbours they have	degree_centrality
`nx.betweenness_centrality`	Rank nodes by how often they bridge others	betweenness_centrality
`kernighan_lin_bisection`	Cut a graph into two balanced communities	kernighan_lin_bisection
`greedy_modularity_communities`	(Part B) find communities, and their number, by modularity	greedy_modularity_communities
`adjusted_rand_score`	Score a grouping against the truth (0 = random, 1 = perfect)	adjusted_rand_score

If something looks off

get_data.py didn’t download anything — is this really the “real” data? Yes. Zachary’s Karate Club is a small, canonical dataset that ships inside the networkx library, so get_data.py reads it straight from the installed package and writes the CSVs locally — no internet, no download, nothing to 404. The wrote karate_edges.csv (78 edges) … line is the confirmation it worked; it’s the same recorded 1977 network every network-science course uses.
A checkpoint number doesn’t match. The data is seeded (or ships inside networkx), so the numbers are exact. Re-run the data step, then re-run Part A.
Setup problems (Python not found, pip, FileNotFoundError, re-activating the venv): see the troubleshooting list in Start Here.

7. Part B — Your Turn

Part B is the optional “your turn” half — a guided fill-in-the-blank, not a blank page. You get a working starter (part_b/starter.py) that already handles the easy version; your job is to finish the # TODO it marks out. More open than Part A’s step-by-step, but you are never staring at an empty file. If you finished Part A and want to prove the skill, this is where it happens. New to Python? It’s completely fine to stop after Part A and come back later.

Different network, harder job. data/sbm_edges.csv is a company’s internal messaging graph: 165 people who mostly message within their own team and occasionally across teams. The teams are hidden, the node ids are shuffled (so the numbering gives nothing away), and — unlike Part A — you are not told how many teams there are.

Your job: assign every node to a community, recovering the hidden teams as well as you can, and report how well you did. Same core skill as Part A (find groups, then validate), now with an unknown number of groups and no labels to peek at.

Acceptance criteria (checkable)

Fill in part_b/starter.py, then:

python part_b/starter.py            # writes part_b/out/
pytest part_b/test_solution.py -q

If pytest reports everything as skipped, it just means the output files don’t exist yet — run python part_b/starter.py first (once your solution fills in the TODOs), then re-run.

Your solution writes into part_b/out/:

assignments.csv — node, community (a community id for every node).
report.json — n_nodes, communities_found, ari, achieved_metric.

You’re done when the tests pass. The grader regenerates the true planted teams from the seed (you never see them) and scores your grouping with the adjusted Rand index. It requires a community for every node and ARI ≥ 0.80. The reference solution reaches 0.93; putting everyone in one group scores ~0.

Constraints — what must be true, not how to get there

Recover the groups from the edges, not from node ids or by reading the hidden labels out of make_data.py.
Let the method decide the number of communities — don’t hard-code “there are four.”
Your reported ari must be the real score of your grouping (the grader recomputes it).

Hints

Hint 1 — the shape of the problem

Part A’s two-way bisection won’t do here — there are more than two teams. Reach for a method that discovers the number of communities on its own. networkx.algorithms.community has several; modularity maximisation is a good default.

Hint 2 — turning communities into the output

Most networkx community functions return a list of sets of nodes. Number the sets 0, 1, 2, … and build a {node: community_id} mapping so every node gets a label, then write it out.

Hint 3 — checking yourself (still not the code)

You can’t see the true labels, but you can sanity-check: a good grouping on this graph finds roughly four communities of similar size. If you get one giant community or dozens of tiny ones, the method or its resolution is off. The ARI the grader reports is the real test — a random labelling scores ~0, so anything near the 0.80 floor means you genuinely recovered structure.

8. Self-check

You don’t need the answer key. You’re done when:

You can say, in one sentence, why the karate-club split was recoverable from friendships alone — and why a couple of members were misassigned.
You can explain what your Part B ARI means (why 0.9 is strong and 0.1 is noise).
Your Part B method chose its own number of communities, and it landed near four of roughly equal size.
You did not use node ids or the hidden labels to cheat — only the edges.

9. Stretch

A second algorithm. Run a different community method (e.g. label propagation, or the Louvain method) and compare its ARI to modularity’s. Do they agree on the hard-to-place nodes?
How noisy can it get? Regenerate the Part B graph with a higher cross-team edge rate (edit P_OUT in make_data.py) and plot ARI as the teams blur together. Find the point where recovery collapses — the “detectability limit.”
(Genuinely hard) Overlapping communities. Real people belong to more than one group. Explore an overlapping-community method (e.g. clique percolation) and think about how you’d even score overlap against ground truth, since ARI assumes each node has exactly one label.

10. Ship it

Put this in a portfolio repo and it counts. In that repo’s README:

Lead with the one-liner anyone gets: “A 1970s karate club split in two — I predicted who went where from the friendship graph alone, at 94% accuracy, then recovered hidden teams in a bigger network and scored the result.”
Show the karate-club graph coloured by your split next to the real factions, and name the two or three members the structure got “wrong.”
State the Part B result as a number, not a vibe: the ARI you reached and what it means. That habit — validating structure instead of asserting it — is the whole point.

Keep get_data.py, make_data.py, and the tests in the repo so anyone can reproduce your numbers from zero.

11. Sources

Rendered from SOURCES.md.

Field	Value
Part A dataset	Zachary’s Karate Club (real), bundled in `networkx`
Citation	Zachary, W. W. (1977), Journal of Anthropological Research 33(4): 452–473
License	Freely available for research/education; shipped in networkx (BSD-3-Clause)
Part B dataset	Synthetic — stochastic block model, `data/make_data.py` (seed 20260718)
Access / verification date	2026-07-18
Redistribution	Karate club fetched from the installed package, never committed; SBM synthetic

The karate-club results are about that real network; the Part B numbers are about a synthetic graph and teach the mechanic (recovering and scoring planted communities), not a real-world finding.

Next up

Finished this one? Continue the Open-Source Libraries track:

Polars Analytics: window functions for the questions group-by can’t answer → · Browse all courses