The problem with Eigen-centrality in directed networks
Recall: A cycle is a path that follows edge directions and returns to its starting node without repeating any edge or intermediate node along the way
A Directed Acyclic Graph (DAG) is a network made up of nodes (points or objects) and edges (arrows showing direction from one node to another), where:
A Directed Acyclic Graph (DAG) contains a strict hierarchical flow with zero loops or cycles. Because influence can only move forward and never recirculate, traditional feedback-based centralities fail.
\[ M = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix} \]
DAGs lacks cycles, a DAG’s adjacency matrix is nilpotent, meaning all of its eigenvalues are exactly zero (\(\lambda = 0\)), Which breaks Eigen-centrality formalism
Recall: An SCC (strongly connected component) is a maximal set of nodes in a directed graph where every node can reach every other node by following edge directions.
Collapse each SCC to a single node and you get the condensation, which is always a DAG.
Each nontrivial SCC has its own internal leading eigenvalue (its Perron root).
The global leading eigenvalue is just the largest of these, and the SCC that achieves it is dominant.
Centrality concentrates in the dominant SCC, flows downstream to whatever it can reach, and dies everywhere else.
The solution to this problem is tweaking the formalism a bit to introduce a new centrality called Katz Centrality Leo Katz, 1953)
Katz centrality extends degree centrality by considering not only a node’s immediate neighbors, but also neighbors-of-neighbors and more distant nodes. Influence propagates through the network along all possible walks, with longer walks receiving exponentially smaller weights.
Katz centrality fixes this by adding a constant bias term (\(\beta\)), and an attenuation factor \(\alpha\) (weight given to neighbors’ scores) which grants every node a baseline injection of intrinsic importance.
\[x_i = \alpha \sum_{j} A_{ji} x_j + \beta\]
How it fixes the DAG: Source nodes (in-degree = 0) no longer get a score of zero; they retain a baseline score of \(\beta\).
The Mechanism: This baseline importance propagates down the DAG’s edges. A node’s score becomes a weighted sum of all upstream paths leading into it.
The Result: Katz centrality successfully ranks nodes in a DAG, establishing a clear hierarchy based on a node’s downstream position relative to its upstream ancestors.
Fixes the “Zero-In-Degree” Problem: In directed networks, standard eigenvector centrality assigns a score of 0 to any node with no incoming links, causing a domino effect that zeroes out downstream nodes.
The Katz centrality of node \(i\) is defined recursively:
\[ x_i = \alpha \sum_{j} A_{ji}\, x_j + \beta \rightarrow \mathbf{x} = \alpha A^T \mathbf{x} + \mathbf{\beta}\mathbf{1} \]
\(\mathbf{1}\) is the all-ones vector: a column vector with a \(1\) in every entry,
\(A\), adjacency matrix (\(A_{ji} = 1\) if there is an edge \(j \to i\))
\(\alpha\), attenuation factor (weight given to neighbors’ scores)
\(\beta\), constant baseline added to every node (typically \(\beta = 1\))
Analytic solution: (for \(\alpha < 1/\lambda_{max}\)): \(x=(I - \alpha A^{T})^{-1}\beta\mathbf{1}\)
The model converges only if
\[ \alpha < \frac{1}{\lambda_{\max}} \]
alpha=0.1, beta=1.0. The small fixed \(\alpha\) is conservative and works for many graphs, but it can violate the convergence rule when \(\lambda_{max} > 10\), so check it on dense or high-degree networks.\[ x_i = \alpha \sum_{j} A_{ji}\, x_j + \beta \;\rightarrow\; \mathbf{x} = \alpha A^{T}\mathbf{x} + \beta\mathbf{1} \]
\[ \mathbf{x} = \beta \sum_{k=0}^{\infty} \left( \alpha A^{T} \right)^{k} \mathbf{1} = \beta \left( I - \alpha A^{T} \right)^{-1} \mathbf{1} \]
\[ \mathbf{x} = \beta\mathbf{1} + \alpha A^{T}\mathbf{x} = \beta\mathbf{1} + \alpha A^{T}\beta\mathbf{1} + (\alpha A^{T})^{2}\mathbf{x} = \beta\sum_{m=0}^{k}(\alpha A^{T})^{m}\mathbf{1} + (\alpha A^{T})^{k+1}\mathbf{x} \]
When \(\alpha < 1/\lambda_{max}\) the trailing term \((\alpha A^{T})^{k+1}\mathbf{x} \to 0\) as \(k \to \infty\), leaving exactly the walk-sum.
Recall eigenvector centrality: \(\mathbf{x} = \frac{1}{\lambda_{\max}} A^{T} \mathbf{x}\), a node’s score is proportional to the sum of its neighbors’ scores.
Failure mode in directed graphs:
Katz’s fix: the \(\beta\) term seeds every node with baseline centrality, which then flows along edges. Every node gets a meaningful, nonzero score.
| Situation | Recommended measure |
|---|---|
| Undirected, connected graph | Eigenvector, simple, parameter-free, well-behaved |
| Directed graph with strong connectivity (one big SCC) | Either works; eigenvector is simpler |
| Directed graph with sources, DAG structure, or many weak components | Katz, eigenvector collapses to zero |
| Citation networks, web graphs, follower networks | Katz (or PageRank) |
| You want a tunable “reach” parameter (local ↔︎ global) | Katz, adjust \(\alpha\) |
Rule of thumb: Eigenvector centrality is the special case; Katz is the safe general-purpose choice for directed networks.
Katz centrality calculates network influence via the matrix equation:
\[ \mathbf{x}^{(k+1)} = \alpha A^{T}\mathbf{x}^{(k)} + \beta\mathbf{1} \]
\[\mathbf{x} = \alpha A^T \mathbf{x} + \mathbf{\beta}\]
Computing the centrality vector \(\mathbf{x}\) is fundamentally treated as solving a standard linear system, \(M\mathbf{x} = \mathbf{b}\), where \(M = (I - \alpha A^T)\) and \(\mathbf{b} = \mathbf{\beta}\). Computers use two primary approaches depending on graph size:
The equation is algebraically rearranged to isolate \(\mathbf{x}\):
\[\mathbf{x} = (I - \alpha A^T)^{-1} \mathbf{\beta}\]
scipy.linalg.solve).To avoid heavy matrix operations on massive networks, the computer approximates the solution by iterating until convergence.
A 4-node directed graph:
\[ 1 \to 2, \qquad 1 \to 3, \qquad 2 \to 3, \qquad 3 \to 4 \]
(1) ──────► (2)
\ │
\ │
▼ ▼
(3) ──► (4)
Adjacency matrix (row = source, column = target):
\[ A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix} \]
Set \(\alpha = 0.1\), \(\beta = 1\). Apply \(x_i = \beta + \alpha \sum_j A_{ji}\, x_j\) node by node (sum over in-neighbors). Since the graph is acyclic, we can solve sequentially:
Node 1 (no incoming edges):
\[ x_1 = 1 + 0.1 \cdot (0) = 1.000 \]
Node 2 (incoming from 1):
\[ x_2 = 1 + 0.1 \cdot x_1 = 1 + 0.1(1.000) = 1.100 \]
Node 3 (incoming from 1 and 2):
\[ x_3 = 1 + 0.1 \cdot (x_1 + x_2) = 1 + 0.1(1.000 + 1.100) = 1.210 \]
Node 4 (incoming from 3):
\[ x_4 = 1 + 0.1 \cdot x_3 = 1 + 0.1(1.210) = 1.121 \]
Result: \(\;x_1 = 1.000,\; x_2 = 1.100,\; x_3 = 1.210,\; x_4 = 1.121\)
Node 3 ranks highest, it receives walks from the most upstream structure. Eigenvector centrality would have ranked all four nodes equally at zero.
import networkx as nx
G = nx.DiGraph([(1, 2), (1, 3), (2, 3), (3, 4)])
katz = nx.katz_centrality_numpy(G, alpha=0.1, beta=1.0,
normalized=False)
print(katz)Output:
{1: 1.0, 2: 1.1, 3: 1.21, 4: 1.121}
normalized=False, by default NetworkX rescales the vector to unit Euclidean norm, which preserves the ranking but changes the raw valueskatz_centrality_numpy solves the linear system directly; katz_centrality uses power iteration (needs max_iter/tol)