Core13 min read

Network measures

A social network is a graph. Degree, closeness, betweenness and eigenvector centrality answer four different questions about who matters.

Draw a graph of friendships and the first question is always the same: who is important? The honest answer is that "important" means several different things. Someone with many friends, someone who is a short hop from everyone, someone who sits on the path between otherwise separate groups, and someone who is connected to other important people are all "central" — and each has its own measure.

Edit the graph below and switch between the four centralities to see the rankings disagree.

Centrality is a question, not a number

Degree counts direct neighbours. Closeness measures how quickly you can reach everyone. Betweenness measures how much of the network's shortest-path traffic must pass through you. Eigenvector says you matter if your neighbours matter. A hub, a bridge and a broker can each top a different list in the same graph.

Click a node, then another, to add or remove an edge. Pick a centrality measure — the ranking and highlight update from real graph algorithms.

edges: 8
density: 0.53
top node: E
measure: betweenness

1.50

1.00

1.50

0.50

2.00

0.50

Select a node to start editing an edge.

Brandes betweenness, BFS closeness and adjacency power iteration, computed in-browser. Degree counts neighbours; closeness is inverse farness; betweenness counts shortest paths through a node; eigenvector borrows its neighbours’ importance.

The measures, precisely

Let the graph have $n$ nodes and adjacency matrix $A$ .

Degree centrality of $v$ is its number of neighbours, $d_v = \sum_u A_{vu}$ (often divided by $n-1$ to normalise).
Closeness centrality is the inverse of total distance: $C(v) = (n-1) / \sum_u d(v,u)$ , where $d(v,u)$ is the shortest-path length. High closeness is a short reach across the whole network.
Betweenness centrality counts shortest paths through $v$ : $B(v) = \sum_{s \neq v \neq t} \sigma_{st}(v) / \sigma_{st}$ , where $\sigma_{st}$ is the number of shortest $s$ – $t$ paths and $\sigma_{st}(v)$ those passing through $v$ . Brandes' algorithm computes all of them in $O(nm)$ .
Eigenvector centrality is the leading eigenvector of $A$ : $x_v \propto \sum_u A_{vu} x_u$ , so importance propagates along edges. PageRank is its directed, damped cousin.

Two closeness conventions

Some texts use the raw reciprocal $1/\sum_u d(v,u)$ (Freeman's original definition), others the normalised $(n-1)/\sum_u d(v,u)$ used here (Wasserman–Faust). The two rank nodes identically and differ only by the constant factor $n-1$ — so an exam solution may look different by that factor. State which definition you use.

Beyond the individual

Whole-network summaries matter too. Density is the fraction of possible edges present, $2m/(n(n-1))$ . The clustering coefficient measures how often a node's neighbours are themselves connected — triangles locally. Diameter and average path length describe how far apart the network is. Many real networks are small-world: highly clustered yet with short paths, so local structure coexists with global reachability.

Communities

Social networks also cluster into communities — densely connected inside, sparsely between. Detecting them means partitioning the graph to maximise a quality function such as modularity, the excess of within-community edges over what a random graph would produce. The communities, not the individual nodes, often carry the meaning.

Centrality is comparative, not absolute

Centrality scores depend on the graph you drew and the edge set you chose. Add one missing edge and the ranking can change; study a subgraph and the "most central" node can be an artifact of the boundary. Always report the graph's provenance (who was included, which ties were recorded) alongside the measure, and treat any single centrality number with suspicion.

Illustrative vs real

The widget runs genuine BFS closeness, Brandes betweenness and power-iteration eigenvector centrality on a small editable graph. Real studies work on networks with millions of nodes, handle directed and weighted edges, use randomised approximations where exact betweenness is too costly, and worry about missing edges and sampling bias far more than about the choice of measure.

Check yourself

Eduspheria wiki · Applied AI, Social network analysis

0 / 5 answered

1In a graph, node v is 1 hop from two nodes, 2 hops from three nodes and 3 hops from one node. Using (n−1)/sum of distances with n = 7 (6 other nodes), what is closeness?
Numeric answer
2Which centrality best identifies a broker connecting two otherwise separate communities?
Multiple choice
3A small-world network combines high clustering with short average path length.
True / false
4Which quality function rewards within-community edges beyond what a random graph would give?
Short answer
5A simple undirected graph has 10 nodes and 15 edges. What is its density?
Numeric answer

From the exam paper

Modeled on NITJ AI-603, End-Sem May 2025

0 / 5 answered

1A 5-node undirected graph has edges A–B, A–C, B–D, B–E, C–D and D–E. What is the degree of node B?
Numeric answer
2For that graph, compute the closeness centrality of node B as (n − 1) divided by the sum of shortest-path distances (n = 5). Give three decimal places.
Numeric answer
3For the same graph, what is the closeness centrality of node A under the same (n − 1)/Σd definition? Give three decimal places.
Numeric answer
4Which nodes have the highest closeness centrality in this graph?
Multiple choice
5In this graph every node has degree at least 2.
True / false

Where next: with measures in hand, we ask the dynamic question — how influence spreads through a network, and how missing links can be predicted.

The measures, precisely #

Beyond the individual #

Communities #

The measures, precisely

Beyond the individual

Communities