Graph Degrees and Centrality

What is this?

The "degree" of a dot is simply how many lines touch it — how many friends a person has, how many roads meet at a junction. It's the easiest measure of how important or well-connected something is. The surprising lesson here is that you often don't need any fancy exploration at all: many "find the most popular node" or "find the special node everyone points to" questions are answered by just counting the lines, one quick pass and you're done.

💡 Fun fact: Google's original PageRank is a souped-up version of degree counting. Instead of just tallying how many links point to a page, it weighs each incoming link by how important the linking page itself is — so a single link from a famous site can outweigh thousands from obscure ones. Degree was the seed of a company worth trillions.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: before you reach for BFS or DFS, ask whether a node's degree — how many edges touch it — already answers the question. A surprising number of "find the special / most-connected node" problems are pure counting: one pass over the edges builds a degree array, and the answer falls out in O(V + E) with no traversal at all.

1. What degree & centrality really mean

The degree of a node is the number of edges incident to it — the simplest possible measure of "how connected" or "how important" that node is. In a directed graph it splits in two:

• In-degree counts arrows pointing in; out-degree counts arrows pointing out. Their roles are not interchangeable — mixing them is the classic bug.
• Undirected degree is a single count: edges touching the node.

Degree is the cheapest centrality measure — a node's raw connectivity. Its richer cousins answer subtler "importance" questions and cost more to compute (conceptually, you don't need them for this chapter):

• Betweenness centrality — how many shortest paths run through a node (a bridge / chokepoint).
• Closeness centrality — how short the node's average distance to everyone else is (a fast broadcaster).
• PageRank — importance weighted by the importance of who points to you (recursive degree).

This chapter stays on the ground floor — degree — because it alone cracks a whole family of problems.

2. Where you'll actually meet this

Degree counting is a real, everyday analysis primitive:

• Distributed systems. Hub / leader detection (the node everyone acknowledges that defers to none = in-degree n-1, out-degree 0); load hotspots (the shard or broker with the most connections is the one to split first).
• Networking. Critical routers — high-degree nodes whose failure fragments the network; pairs of routers whose combined link count bounds a failure domain.
• Social & recommendation graphs. Influencer detection (high in-degree = many followers), universally-followed accounts, highest-reach co-promotion pairs.
• Dependency & build graphs. A foundational module is a degree sink — everything imports it, it imports nothing.

If a problem says find the node everyone points to, the most-connected vertex, the busiest pair, the trusted root — reach for degrees before traversal.

3. The degrees toolkit (patterns to recognise)

1. Build a degree array in one edge pass. For each edge (a, b), bump the relevant counter(s). Directed: out[a] += 1, in[b] += 1. Undirected: deg[a] += 1, deg[b] += 1. One O(E) sweep, done.
2. The in-minus-out trick. When the special node is defined by both a high in-degree and a zero out-degree, fold them into a single signed score: degree[b] += 1, degree[a] -= 1 per edge a→b. One number, one comparison.
3. Adjacency set for "are these two connected?" Store each undirected edge as a frozenset({a, b}) (or a sorted tuple). Membership is O(1) and memory scales with edges, not n² — essential when a pair's answer depends on whether they share an edge.
4. Degree as an O(V + E) pre-pass. Compute degrees once, then run the cheap logic on top — an O(n²) pair sweep or an O(V) scan for the special node. The expensive-looking part becomes pure arithmetic over precomputed counts.

4. A 30-second worked example (count degrees)

Undirected graph, who's most connected?

One pass over four edges, no traversal — the most-connected node reads straight off the array. That counting reflex powers every problem below.

5. Problems in this chapter

▶ Find the Town Judge

Find the one node everyone points to that points to nobody (a trusted root / elected leader). Fold each edge into a signed score degree = in − out; the unique node ending at exactly n-1 is the answer.
Pattern: signed in-minus-out degree. Target: O(V + E), O(V).

▶ Maximal Network Rank

Find the pair of nodes whose combined edge count is highest (the busiest two-router slice). Precompute degrees + an adjacency set, then sweep all pairs: deg(a) + deg(b), minus 1 if they share an edge.
Pattern: degree precompute + pairwise sweep with shared-edge correction. Target: O(E + n²), O(n + E).

6. Common pitfalls 🚫

• Mixing in-degree and out-degree. In a directed problem, "trusts" vs "is trusted" are opposite counters. Swapping them silently returns the wrong node — keep their roles straight (or use the signed trick where the sign encodes direction).
• Forgetting the shared-edge subtraction. When a pair's score combines two degrees, an edge between them was counted twice. Miss the −1 and connected pairs are over-ranked.
• Assuming highest-degree wins. For pair problems, two top-degree nodes that are directly connected lose 1; a lower-degree unconnected pair can beat them. Always check the shared edge.
• Reaching for BFS/DFS. If the answer is a degree signature, traversal is wasted work — count edges instead.
• Off-by-one / indexing. 1-based labels (1…n) vs 0-based (0…n-1), and the n-1 in-degree threshold, are where these problems are quietly won or lost.

7. Key takeaways

1. Degree first, traversal later. Many "special / most-connected node" questions are answered by counting edges in O(V + E) — no BFS/DFS needed.
2. One edge pass builds every degree. Directed → separate in/out (or a signed score); undirected → one count per endpoint.
3. The in-minus-out trick packs "high in-degree and zero out-degree" into a single number and a single comparison.
4. An adjacency set answers "connected?" in O(1) with edge-sized memory — the key to pair problems with a shared-edge correction.
5. Degree is the simplest centrality; betweenness, closeness, and PageRank are its richer cousins — good to name, unneeded here. Interviewers lean on this family because it rewards spotting counting over traversal.