Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 36 Ā· Applications

Centrality Measures in Networks

Find the most important vertices in a network: implement degree, closeness, betweenness (Brandes) and eigenvector centrality in Python and learn when each one is the right tool.

Which person in a social network is the most influential? Which router, if it fails, hurts the most? Which protein is essential to a cell? Each question asks for the importance of a vertex, but "important" can mean very different things: having many friends, being close to everyone, sitting on the only route between groups, or knowing other important people. Graph theory formalizes each meaning as a centrality measure.

This lesson implements the four classic measures from scratch and compares them on one network, so you can see how they disagree and why.

The example network

Two tight friend groups are joined by one person who knows members of both (a "broker"), plus a pair of hangers-on.

flowchart LR
    a1((a1)) --- a2((a2))
    a1 --- a3((a3))
    a2 --- a3
    a2 --- a4((a4))
    a3 --- a4
    a4 --- br((broker))
    br --- b1((b1))
    b1 --- b2((b2))
    b1 --- b3((b3))
    b2 --- b3
    b3 --- b4((b4))
    b2 --- b4
    br --- x((x))

Group A on the left, group B on the right, and the broker between them.

1. Degree centrality

Degree centrality is simply the number of neighbors, usually divided by n āˆ’ 1 so it lies between 0 and 1. It measures local popularity and is trivial to compute, but it ignores where the neighbors are. A vertex with ten neighbors that all know each other is less of a hub than one whose ten neighbors lie in ten separate groups.

2. Closeness centrality

Closeness rewards vertices that are near everybody: C(v) = (n āˆ’ 1) / Ī£ d(v, u), where d is the shortest-path distance. It is computed with one breadth-first search per vertex. For disconnected graphs, use the sum of reciprocal distances (harmonic centrality) so unreachable vertices contribute 0 instead of infinity.

3. Betweenness centrality

Betweenness counts how often a vertex lies on shortest paths between other pairs:

B(v) = Ī£ over pairs s ≠ v ≠ t of σ_st(v) / σ_st

where σ_st is the number of shortest paths from s to t and σ_st(v) is how many of those pass through v. High betweenness marks bridges and bottlenecks: removing such a vertex lengthens many routes or disconnects the graph. The naive formula costs O(n³); Brandes' algorithm accumulates path dependencies backwards from each BFS in O(n·m) total for unweighted graphs.

Four kinds of importance

Degree How many neighbors
Closeness How near to everyone
Betweenness How often on shortest routes
Eigenvector Knows important people

Pick the measure that matches your question

1 / 2
Python Degree, closeness and Brandes betweenness

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 broker has the highest betweenness by a wide margin (every route between the groups passes through it) and also the best closeness, but its degree (3) is no larger than that of a2 or a3. Degree alone would miss it entirely.

4. Eigenvector centrality

Eigenvector centrality says a vertex is important if it is connected to important vertices: x_v = (1/λ) Σ over neighbors u of x_u, i.e. A x = λ x. The Perron-Frobenius theorem guarantees that for a connected graph the leading eigenvector of the adjacency matrix has all positive entries. We can compute it by power iteration: repeatedly multiply by A and normalize. Variants fix its weaknesses: PageRank adds teleportation for directed graphs (see random walks), and Katz centrality adds a constant baseline so every vertex has some score.

Python Eigenvector centrality by power iteration versus eigh

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.

Here a4, b1 and the dense-group vertices score high because they sit among well-connected neighbors, while the broker scores lower than all of them: eigenvector centrality rewards clusters of importance, not bridging. That is the key lesson of this chapter: there is no single "most important vertex"; the measure encodes a question.

Choosing a measure

Question Measure
Who has the most direct contacts? Degree
Who can reach everyone fastest (spreading news)? Closeness
Whose removal breaks the network or who controls flow? Betweenness
Who is connected to the powerful? Eigenvector, Katz, PageRank

Remember the cost: betweenness is O(nĀ·m) and becomes heavy on millions of vertices, where approximations from sampled sources are used. Also compare ranks across measures rather than raw values, because the scales differ.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. Which centrality counts how often a vertex lies on shortest paths between other vertices?

    Betweenness sums, over all pairs, the fraction of shortest paths that pass through the vertex, so it highlights bridges and bottlenecks.
  2. 2. Why might a bridge vertex have low degree but high betweenness?

    A vertex with few neighbors can still lie on all shortest paths between two groups, which gives it large betweenness.
  3. 3. What does eigenvector centrality assume?

    The score satisfies A x = Ī» x, so each vertex's score is proportional to the sum of its neighbors' scores.
  4. 4. What is the time complexity of Brandes' algorithm for betweenness on an unweighted graph?

    One BFS plus one backward accumulation per source gives O(m) per source and O(nĀ·m) in total.

Summary

  • Centrality measures answer different questions about importance; no single ranking is the truth.
  • Degree counts neighbors, closeness measures average distance, betweenness counts shortest paths through a vertex, eigenvector centrality scores connection to important vertices.
  • Brandes' algorithm computes betweenness in O(nĀ·m); power iteration computes the leading eigenvector.
  • Always compare several measures and match them to the real-world question.

Next: Scheduling and Timetabling with Coloring