Network Metrics: Centrality, PageRank, Clustering, and Communities

Complex Systems · 5/8 · Series index · Notation

Graph representations and connectivity are developed in Network fundamentals.

Network Metrics and Algorithms

Unless stated otherwise, formulas refer to simple, undirected, unweighted graphs without self-loops. There are $n$ nodes and $M$ edges.

Distance, Eccentricity, Diameter, and Radius

The shortest-path distance $d_{ij}$ is the length of the shortest feasible path from $i$ to $j$. In an unweighted graph, length counts edges. If weights represent distances or costs, length is the sum of the weights along the path. A stronger connection need not represent a greater distance: interpret the weights before choosing an algorithm.

$$\begin{aligned} L&=\frac{1}{n(n-1)}\sum_{i\ne j}d_{ij} =\frac{2}{n(n-1)}\sum_{i<j}d_{ij},\\ \varepsilon(i)&=\max_jd_{ij},\\ D&=\max_i\varepsilon(i),\qquad R=\min_i\varepsilon(i). \end{aligned}$$

$L$ is the mean shortest-path length, also called the characteristic path length. The eccentricity $\varepsilon(i)$ measures the greatest distance from $i$; $D$ is the diameter and $R$ the radius. The center consists of nodes with $\varepsilon(i)=R$, and the periphery of nodes with $\varepsilon(i)=D$. A connected undirected graph satisfies $R\le D\le2R$: any two nodes can be connected via a center node by a walk of length at most $2R$.

Conditions: finite whole-graph distance formulas require all relevant pairs to be reachable. Disconnected graphs contain pairs with $d_{ij}=\infty$. One can instead analyse the largest connected component or average over reachable pairs, but must state the convention. In directed graphs, retain edge directions; reachability for every ordered pair requires strong connectivity.

Degree, Closeness, and Betweenness: Different Meanings of Importance

Degree centrality is

$$C_D(i)=\frac{k_i}{n-1}.$$

It measures the number of direct neighbours. Directed versions use $k_i^{\mathrm{in}}$ or $k_i^{\mathrm{out}}$. If $i\to j$ means “$i$ follows $j$,” having many followers means high in-degree, while following many accounts means high out-degree. An interpretation such as “influence equals out-degree” cannot be separated from the meaning of an edge.

Closeness centrality is

$$C_C(i)=\frac{n-1}{\sum_{j\ne i}d_{ij}}.$$

It is the reciprocal of mean distance: a larger value means a node is closer, on average, to the others. In a directed graph distinguish outward distances, from the node to others, from inward distances, from others to the node. NetworkX uses inward distances by default; call the function on the reversed graph for outward closeness. Its default correction for disconnected graphs is, with $r_i$ other nodes able to reach $i$,

$$C_C^{\mathrm{WF}}(i)=\frac{r_i}{n-1}\frac{r_i}{\sum_{j:\,j\leadsto i,\,j\ne i}d_{ji}}.$$

The value is zero when no other node can reach $i$.

For betweenness centrality, let $\sigma_{st}$ be the number of shortest paths from $s$ to $t$, and $\sigma_{st}(i)$ the number passing through $i$ as an internal node. For $n>2$, normalized undirected betweenness is

$$C_B(i)=\frac{2}{(n-1)(n-2)} \sum_{\substack{s<t\\s,t\ne i}}\frac{\sigma_{st}(i)}{\sigma_{st}}.$$

If the sum instead includes ordered pairs $s\ne t$, use the prefactor $1/[(n-1)(n-2)]$. Unreachable pairs contribute zero, and endpoints are excluded from internal passage. Betweenness measures a node's role as a bridge between regions. When several shortest paths exist, divide the contribution among them instead of selecting just one.

Choosing a metric: use degree for direct connection count, closeness for average reachability distance, and betweenness for shortest-path bottlenecks between communities. These measures can produce different rankings; no single centrality is best for every task.

Eigenvector Centrality and Katz Centrality

Eigenvector centrality gives more credit for connections to important neighbours. For an undirected graph,

$$x_i=\frac1\lambda\sum_jA_{ij}x_j, \qquad A\boldsymbol x=\lambda\boldsymbol x.$$

Choose a nonnegative eigenvector corresponding to the spectral radius $\rho(A)$ and specify its normalization. For a connected graph, the Perron–Frobenius properties of its nonnegative adjacency matrix give a unique positive direction. Disconnected graphs can introduce nonuniqueness or zero components.

Our convention is $A_{ij}=1$ for $i\to j$, so importance received through incoming edges satisfies

$$x_i=\frac1\lambda\sum_jA_{ji}x_j, \qquad A^{\mathsf T}\boldsymbol x=\lambda\boldsymbol x.$$

This is a left eigenvector of $A$, or a right eigenvector of $A^{\mathsf T}$ when written as a column. NetworkX uses this incoming-edge definition. To receive scores from outgoing neighbours instead, use $A\boldsymbol x$.

Left/right eigenvectors and in/out-degree must be interpreted using a consistent adjacency convention. A directed acyclic graph (DAG) has only zero adjacency eigenvalues, making ordinary eigenvector centrality degenerate. This does not mean every mathematical eigenvector must be the zero vector. The issue is that the usual propagation rule with a positive eigenvalue does not provide an appropriate unique positive ranking.

Katz centrality adds a baseline score $\beta>0$ to every node. Set $B=A$ for an undirected graph and $B=A^{\mathsf T}$ for incoming-edge centrality in a directed graph:

$$\begin{aligned} \boldsymbol x&=aB\boldsymbol x+\beta\boldsymbol1,\\ \boldsymbol x&=\beta(I-aB)^{-1}\boldsymbol1,\\ 0&\le a<\frac1{\rho(B)}. \end{aligned}$$

Expanding the inverse as a geometric series gives

$$\boldsymbol x=\beta\sum_{\ell=0}^{\infty}a^\ell B^\ell\boldsymbol1.$$

Thus walks of length $\ell$ receive weight $a^\ell$. The parameter $a$ controls the influence of distant walks. A uniform $\beta$, often set to one, changes only the overall scale. Changing $a$ can alter relative scores and potentially the ranking; knowing only $a/\beta$ is insufficient. The inverse gives an unnormalized solution; nx.katz_centrality normalizes its Euclidean norm to one by default. If $\rho(B)=0$, as for a DAG, the series terminates after finitely many terms, so there is no finite $1/\rho$ upper bound.

PageRank: Probability Flow with Random Teleportation

Katz transfers importance without dividing each node's contribution by its out-degree. PageRank instead describes a random walk: node $j$ divides its score equally among the nodes it points to, while teleportation occurs with probability $1-d$. The damping factor satisfies $0<d<1$, commonly $d=0.85$; this differs from Katz's spectral-radius condition.

Let $P$ be a row-stochastic matrix. For an unweighted graph without dangling nodes, $P_{ij}=A_{ij}/k_i^{\mathrm{out}}$. When $k_i^{\mathrm{out}}=0$, replace that row with the teleportation distribution $\boldsymbol v^{\mathsf T}$; uniform teleportation has $v_i=1/n$. In column-vector notation,

$$\begin{aligned} \boxed{\boldsymbol p=dP^{\mathsf T}\boldsymbol p+(1-d)\boldsymbol v},\\ p_i\ge0,\qquad\sum_i p_i=1. \end{aligned}$$

With uniform teleportation, every node receives baseline probability $(1-d)/n$. For normalized PageRank with uniform teleportation, the baseline vector is $(1-d)\boldsymbol1/n$. Equivalently, the Google matrix is

$$G=dP+(1-d)\boldsymbol1\boldsymbol v^{\mathsf T},\qquad G^{\mathsf T}\boldsymbol p=\boldsymbol p.$$

A quick check is to sum the components: both sides must sum to one. Replacing dangling rows by the teleportation distribution keeps the transition matrix row-stochastic.

Worked example: suppose the only edge is $1\to2$, with uniform teleportation. Replace the second transition row by $(1/2,1/2)$. Then

$$\begin{aligned} p_1&=\frac d2p_2+\frac{1-d}{2},\qquad p_1+p_2=1,\\ p_1&=\frac1{2+d},\qquad p_2=\frac{1+d}{2+d}. \end{aligned}$$

At $d=0.85$, the scores are approximately $(0.350877,0.649123)$. Node 2 does not absorb and destroy the total probability merely because it has no outgoing edges.

Cores, Local Clustering, and Global Transitivity

A $k$-core is the maximal induced subgraph obtained by repeatedly removing nodes whose current degree is below $k$. Every remaining node has degree at least $k$ within the subgraph. A node's core number is the largest $k$ for which it belongs to a $k$-core. Degrees must be updated within the remaining subgraph after each removal. A node with a large original degree can still have core number one if it is connected only to leaves, as in a star.

A node in a $k$-core needs at least $k$ neighbours within that core; those neighbours may have higher core numbers. They need not all have exactly the same coreness. A $k$-core also need not be the innermost core.

For the local clustering coefficient, let $t_i$ count triangles containing $i$, equivalently edges between its neighbours. Then

$$\begin{aligned} C_i&=\frac{t_i}{\binom{k_i}{2}}=\frac{2t_i}{k_i(k_i-1)},\qquad k_i\ge2,\\ C_i&=0,\qquad k_i<2. \end{aligned}$$

The mean local clustering $\bar C=\frac1n\sum_iC_i$ weights nodes equally. In a simple undirected graph, useful checks are $(A^3)_{ii}=2t_i$ and the total triangle count $T=\operatorname{tr}(A^3)/6$.

Global transitivity is

$$C_{\mathrm{trans}}=\frac{3T}{\sum_i\binom{k_i}{2}} =\frac{\sum_i\binom{k_i}{2}C_i}{\sum_i\binom{k_i}{2}}.$$

NetworkX defines transitivity as zero when there are no connected triples. The denominator counts pairs of neighbours centred on a node; each triangle contributes three closed triples. Transitivity weights local coefficients by neighbour-pair counts, so it generally differs from $\bar C$. Neither is universally larger. Transitivity can be smaller when high-degree nodes have low local clustering.

Assortativity, Communities, and Modularity

Assortativity measures the correlation of attributes at the two ends of an edge. For each directed edge $e=(i,j)$, write $u_e=f(i)$ and $v_e=f(j)$. Count both orientations of undirected edges to avoid arbitrary endpoint asymmetry. With endpoint means $\bar u,\bar v$,

$$r=\frac{\sum_e(u_e-\bar u)(v_e-\bar v)} {\sqrt{\sum_e(u_e-\bar u)^2\sum_e(v_e-\bar v)^2}}.$$

This is Pearson correlation. Positive $r$ indicates assortative mixing, negative $r$ disassortative mixing, and zero no linear correlation of these attributes. It is undefined when an endpoint attribute has zero variance. Undirected degree assortativity uses $f(i)=k_i$. For directed graphs, specify the degree type at each endpoint; NetworkX defaults to source out-degree and target in-degree (x="out", y="in"). Sampling is by edge endpoints, not uniformly over nodes.

In BA growth, new nodes start with low degree and preferentially connect to high-degree nodes; finite samples may exhibit weak negative degree correlations. The sign in one simulation is not a theorem for every BA parameter choice and size. Political networks can exhibit different connection patterns within and between groups.

A community usually means a set of nodes with denser internal than external connections. A partition may be supplied by domain labels or inferred algorithmically. Louvain is an unsupervised community-detection method and does not require pre-existing correct labels.

Modularity compares observed within-community edges with a random baseline that incorporates node degrees. For an unweighted undirected graph with $M>0$, a non-overlapping partition $c_i$, and resolution parameter one,

$$\begin{aligned} Q&=\frac1{2M}\sum_{i,j}\left(A_{ij}-\frac{k_ik_j}{2M}\right)\delta(c_i,c_j)\\ &=\sum_C\left[\frac{l_C}{M}-\left(\frac{K_C}{2M}\right)^2\right]. \end{aligned}$$

Here $l_C$ counts internal edges of community $C$, while $K_C=\sum_{i\in C}k_i$ sums its nodes' degrees in the original graph. The baseline is not an unspecified “purely random graph”: its expected edge counts depend on degree. A larger $Q$ indicates more internal edges than this baseline predicts, but does not guarantee a unique true community structure. Putting every node in one group gives $Q=0$.

Giant Components, Small Worlds, and Reading Empirical Network Tables

The fraction of nodes in the largest connected component is $S=|C_{\max}|/n$. Strictly, a giant component occupies a nonzero fraction as the network grows, with size of order $n$. Being the largest component of a finite graph does not by itself establish this asymptotic property.

Increasing the edge probability in $G(n,p)$ can merge many small components into a large one.

The small-world property means typical shortest paths are short, often growing slowly with network size. A power-law degree distribution, short paths, and high clustering are three distinct properties. “Six degrees of separation” is an empirical description of social networks, not a theorem that every pair of people is exactly six steps apart.

Empirical networks can be compared using $n,M,c,S,L$, the degree-tail exponent, transitivity, mean local clustering, and $r$. Social networks often have short distances, high clustering, and positive assortativity; information and biological networks may have heavy-tailed degrees and negative assortativity. These tendencies have exceptions and must not be treated as universal laws.

A power law does not necessarily have infinite variance. An ideal unbounded power-law tail with $1<\gamma\le3$ has no finite second moment, while $\gamma>3$ can have finite variance. A finite observed sample of finite values still has a computable sample variance.

BFS and Computational Complexity: State the Representation

An adjacency list uses $O(n+M)$ space; an adjacency matrix uses $O(n^2)$. If the graph is sparse, $M=O(n)$, adjacency-list storage is approximately linear. A hub can nevertheless have a large degree, so enumerating every individual node's neighbours cannot always be treated as constant-time work.

Breadth-first search (BFS) finds shortest paths in an unweighted graph. Set the source distance to zero and enqueue it. Remove the next node $u$ from the front of the queue; for each unvisited neighbour $v$, set $d(v)=d(u)+1$ and enqueue $v$. Because the search visits distance layer $d$ before layer $d+1$, first discovery gives the shortest distance.

Task	Typical adjacency-list complexity	Reason and conditions
Enumerate neighbours of node $i$	$O(k_i)$	Each neighbour must be visited
Retrieve an unweighted degree	Can be $O(1)$	If the container or a cache stores the neighbour count; scanning costs $O(k_i)$
Compute mean degree $2M/n$	$O(1)$ or $O(n)$	Constant time if $M,n$ are known; summing retrieved node degrees costs $O(n)$; scanning edges costs $O(n+M)$
Single-source BFS or a two-node shortest path	$O(n+M)$ worst case	Nodes and edges are visited a constant number of times; early stopping need not improve the worst-case order
One node's eccentricity	$O(n+M)$	Run BFS, then take the largest distance
All-pairs distances and exact whole-graph $D,R,L$	$O(n(n+M))$	Run BFS from every node

The last row becomes $O(n^2)$ for sparse graphs. With an adjacency matrix, a BFS typically costs $O(n^2)$ because it scans whole rows. Weighted distances generally require another algorithm; Dijkstra is commonly used for nonnegative distance weights.

Worked Example: A Triangle with One Leaf

Consider $V=\{1,2,3,4\}$ and $E=\{(1,2),(1,3),(2,3),(3,4)\}$.

1 ----- 2
 \     /
  \   /
    3 ----- 4

$$(d_{ij})=\begin{pmatrix}0&1&1&2\\1&0&1&2\\1&1&0&1\\2&2&1&0\end{pmatrix}.$$

There are four edges, degrees $(2,2,3,1)$, mean degree two, and density $2/3$. The six unordered pair distances sum to eight, so $L=4/3$. Also $D=2$, $R=1$, the center is $\{3\}$, and the periphery is $\{1,2,4\}$.

Node	$C_D$	$C_C$	$C_B$	$C_i$	Core number
1	$2/3$	$3/4$	0	1	2
2	$2/3$	$3/4$	0	1	2
3	1	1	$2/3$	$1/3$	2
4	$1/3$	$3/5$	0	0	1

Node 3 lies on the shortest paths for $(1,4)$ and $(2,4)$, giving normalized betweenness $2/3$. There is one triangle and $1+1+3=5$ connected triples, hence $\bar C=7/12$ and $C_{\mathrm{trans}}=3/5$.

For the partition $\{1,2,3\},\{4\}$, we have $l_1=3,K_1=7,l_2=0,K_2=1,M=4$, so

$$Q=\frac34-\left(\frac78\right)^2-\left(\frac18\right)^2=-\frac1{32}.$$

Degree assortativity is $r=-5/7$: the mean degree sampled at edge endpoints is $9/4$, the covariance is $-5/16$, and each endpoint variance is $7/16$. High-degree endpoints therefore tend to connect to lower-degree endpoints in this example.

The negative modularity means that separating the leaf into its own community does not improve on the degree-based random baseline. The code in the next section checks these results.

---

← Network fundamentals · Series index · Working with NetworkX →