4 Centrality
Open the live notebook in Google Colab here.
With our foundational mathematical and computational tools about networks in hand, we turn our attention toward measuring structural features in a network.
The first question we’ll tackle is importance: Which nodes are the most important in a network? The answer depends on how you define importance! We’ll discuss possible interpretations of this question and the resulting centrality measures.
Centrality measures quantify the relative importance of nodes in a network by assigning numbers to each node; these numbers are sometimes called centrality scores. A node’s centrality score allows for comparison with another node in the same network.
Depending on the application, having good answers to the question of importance could help determine how to target interventions, predict how diseases or information might spread, or create rankings and search algorithms. Boldi and Vigna (2014) provide a good historical account of centrality measures, as well as a useful mathematical exploration of their properties.
Degree-based Centrality Measures
Degree Centrality
One natural definition of importance would be to suppose that important nodes have lots of connections to other nodes. Conveniently, we already have a way to measure this quantity: this is captured by degree!
If \(k_i\) is the degree of node \(i\) and we have a network with \(n\) nodes, then we can define the \(n \times 1\) vector \({\bf c}_{deg} = \left(k_1, k_2, \dots, k_n \right)\) to contain the centralities of each node. Using what we know about degree, that means we can calculate centrality directly from the adjacency matrix \(A\):
\[ {\bf c}_{deg} = {\bf A}{\bf 1} \]
where \({\bf 1}\) is the vector containing all ones.
For a directed network, we could use either in- or out-degree as centrality measures, depending on what is useful for the context or application.
Show code
from matplotlib import pyplot as plt
import networkx as nx
import numpy as np
plt.style.use('seaborn-v0_8-whitegrid')
def unweight(G):
for source, target in G.edges():
G[source][target]['weight'] = 1
return G
G = unweight(nx.karate_club_graph())
## Degree
deg = nx.degree_centrality(G)
deg = np.array([deg[i] for i in deg.keys()])
nx.draw(G, with_labels = True, node_size = 1000*deg, node_color = deg, cmap = "Blues", font_size = 8, edge_color = "gray", edgecolors = "black", pos=nx.kamada_kawai_layout(G))
Advantages and Disadvantages
Degree centrality is quick to calculate and interpret, which makes it an attractive choice of centrality measure. The link between network structure and centrality is very clear.
However, we might miss a key feature of relative importance using this simple measure. Perhaps what matters is not only how many connections a node has, but whether or not it is connected to other important nodes. For example, if I have two friends, you may view me as more important if my two friends are Beyonc'{e} and Taylor Swift than if they were two people you had never heard of.
Eigenvector Centrality
Eigenvector centrality accounts for the phenomenon described above by assuming that a node with an important connection is more important. The idea is to “weight” each connection for a node by the centrality of the adjacent neighbor. In this way, high centrality is achieved either by having lots of connections, or by having a few important connections.
Suppose we have an undirected network with \(n\) nodes. We calculate the centrality \(c_i\) of node \(i\) by summing the centralities of its neighbor, using some proportionality constant \(\frac{1}{r}.\) This gives the equation
\[\begin{align} c_i &= \frac{1}{r}\sum_{j \in \text{neighbors of } i} c_j \, \\ &= \frac{1}{r} \sum_{j=1}^n A_{ij}c_j \,. \end{align}\]
Let \({\bf c}_{eig}\) be our new centrality vector. Writing the formula above in matrix notation gives
\[ {\bf c}_{eig} = \frac{1}{r}{\bf A}{\bf c}_{eig} \implies r{\bf c}_{eig} = {\bf A}{\bf c}_{eig} \,. \]
Now the name of this centrality measure is very clear: \({\bf c}_{eig}\) is an eigenvector of \({\bf A}\) with associated eigenvalue \(r\)!
This leads us to a challenge: which eigenvector should we choose? We have up to \(n\) linearly independent eigenvectors to choose from, as well as linear combinations of these, so our task of making a meaningful choice seems quite daunting. One constraint we’d like to impose is that we’d like our centrality scores to be nonnegative. Will we always be able to find such an eigenvector for any graph?
Fortunately, we have a powerful theorem that can help us with this task.
Perron–Frobenius Theorem
We won’t reproduce the entire theorem here. Horn and Johnson (2012) provides a comprehensive discussion of the proof of this theorem. Keener (1993) also provides a concise proof and interesting applications to ranking.
From the Perron–Frobenius theorem, we know we are guaranteed to have at least one nonnegative eigenvector for \(A\). This is good news! For the case where we have a strongly connected graph, then we have a nice unique answer to our problem. We should choose an eigenvector associated with the largest eigenvalue (i.e., the leading eigenvalue). Notice that an scalar multiple of this eigenvector will also work, as the relative rankings of nodes is still preserved. Many people will choose to use a normalized eigenvector for convenience.
If you have multiple strongly connected components, the second statement of the theorem will not hold. However, you can still calculate the eigenvector centrality of each component separately, as each strongly connected component satisfies all conditions for the theorem.
Let’s implement eigenvector centrality for the same network
Show code
from matplotlib import pyplot as plt
import networkx as nx
import numpy as np
plt.style.use('seaborn-v0_8-whitegrid')
def unweight(G):
for source, target in G.edges():
G[source][target]['weight'] = 1
return G
G = unweight(nx.karate_club_graph())
## Eigenvector
eig = nx.eigenvector_centrality(G)
eig = np.array([eig[i] for i in eig.keys()])
nx.draw(G, with_labels = True, node_size = 1000*eig, node_color = eig, cmap = "Blues", font_size = 8, edge_color = "gray", edgecolors = "black", pos = nx.kamada_kawai_layout(G))
Complications with directed networks
- Should this centrality use in-edges or out-edges? This depends on the context! In-edges correspond to right eigenvectors; and out-edges correspond to left eigenvectors.
- Only nodes that are in a strongly connected component of two or more nodes, or in the out-component of such a strongly connected component, have nonzero eigenvector centrality.
We will see this challenge in the network below. Calculate the in-degree eigenvector centrality \(x_i\) of each node, using the component-wise formula:
\[ x_i = \frac{1}{r} \sum_j A_{ij} x_j \,. \]
Show code
from matplotlib import pyplot as plt
import networkx as nx
plt.style.use('seaborn-v0_8-whitegrid')
DG = nx.DiGraph()
DG.add_edges_from([(1,2), (1, 4), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5)])
nx.draw(DG, with_labels = True, arrowsize = 20, font_color = 'white', font_weight = 'bold')
Katz Centrality
It would be nice to be able to generalize eigenvector centrality while being able to avoid some of the issues that arose with nodes having zero centrality if they have zero in-degree.
We could try to introduce an intuitive fix by giving each node some centrality “for free.” That is,
\[ c_i = \alpha \sum_j A_{ij}c_j + \beta \, \]
where \(\alpha, \beta >0\) are constant. The first term follows the form we derived for eigenvector centrality, and the second is the baseline level of centrality (the “free centrality”).
Writing in matrix-vector form, we arrive at a centrality measure \({\bf c}_{Katz}\) due to Katz (1953):
\[ {\bf c}_{Katz} = \alpha A {\bf c}_{Katz} + \beta {\bf 1} \,. \]
If \(I-\alpha A\) is invertible, then we will be able to write a nice expression for \({\bf c}_{Katz}\). We know this matrix is not invertible when \(det(I-\alpha A) = 0\), which is equivalent to the scalar multiple \(det(\frac{1}{\alpha}I - A) = 0\). We deduce that this occurs when \(\lambda = \frac{1}{\alpha}\), where \(\lambda\) are the eigenvalues of the adjacency matrix.
Thus, if we want to be safe and guarantee convergence of our centrality measure, then we should choose \(\alpha < \frac{1}{\lambda_1}\), where \(\lambda_1\) is the largest (most positive) eigenvalue of \(A\).
Often, we will choose to set \(\beta = 1\), since it doesn’t have any impact on the relative ordering of our centrality scores.
Notice that within this constraint, \(\alpha\) acts like a tunable parameter: As \(\alpha \to 0\), all the nodes have the same centrality. As \(\alpha \to \frac{1}{\lambda_1}\), we recover eigenvector centrality.
Now let’s implement Katz centrality in NetworkX. Calculate an appropriate range for \(\alpha\), and then explore how varying \(\alpha\) changes the centrality scores.
Show code
from matplotlib import pyplot as plt
import networkx as nx
import numpy as np
plt.style.use('seaborn-v0_8-whitegrid')
def unweight(G):
for source, target in G.edges():
G[source][target]['weight'] = 1
return G
G = unweight(nx.karate_club_graph())
## Katz centrality
beta = 1
A = nx.to_numpy_array(G)
alpha_max = min(np.abs(1/np.linalg.eig(A)[0]))
katz = nx.katz_centrality(G, 0.5*alpha_max, beta)
katz = np.array([katz[i] for i in katz.keys()])
nx.draw(G, with_labels = True, node_size = 1000*katz, node_color = katz, cmap = "Blues", font_size = 8, edge_color = "gray", edgecolors = "black", pos = nx.kamada_kawai_layout(G))
Advantages and disadvantages
Katz centrality keeps several of the nice features of eigenvector centrality while avoiding the zero-centrality pitfalls. It’s also relatively quick to calculate.
However, if a node with high Katz centrality points to many other nodes in a directed network, then they will all “inherit” this high centrality as well, which may be undesirable.
PageRank
Neither eigenvector nor Katz centrality measures penalize high-centrality nodes with a large number of edges. Suppose we wanted to think more of centrality like currency: each node has an allotted amount that it may divide among its edges, so that if you were sharing with more edges, you would have to give a smaller amount to each. This idea would essentially “dilute” centrality based on the number of out-edges. This might be relevant in the example of webpages: Just because a page is linked from a very popular site (say, Wikipedia) does not mean that linked page is itself important. Wikipedia links to many, many, many pages!
We implement this idea with a small modification to Katz centrality, where we divide by out-degree of each node.
\[ x_i = \alpha \sum_j A_{ij} \frac{x_j}{k_{j}^{out}} + \beta \]
where we define \(k_j^{out} = 1\) for nodes that have no out-edges to make our mathematical expression well-defined.
Following the same arguments as for Katz centrality, this means we can write our PageRank centrality \({\bf c}_{PR}\) as \[ {\bf c}_{PR} = \alpha A D^{-1} {\bf c}_{PR} + \beta {\bf 1} \,, \]
where \(D\) is the diagonal matrix with diagonal elements \(D_{ii} = \max\{k_i^{out}, 1\}\). If we set \(\beta = 1\) and as long as we have chosen \(\alpha\) appropriately (using similar arguments as before), we can write PageRank centrality in closed form.
The name PageRank comes from Google, who used this idea as a basis of their original web search algorithm. See Langville and Meyer (2005) for a survey on PageRank and related methods. We will explore PageRank further in future lectures.
Show code
from matplotlib import pyplot as plt
import networkx as nx
import numpy as np
plt.style.use('seaborn-v0_8-whitegrid')
def unweight(G):
for source, target in G.edges():
G[source][target]['weight'] = 1
return G
G = unweight(nx.karate_club_graph())
## PageRank
A = nx.to_numpy_array(G)
D_inv = np.diag(1/np.sum(A, axis = 1))
alpha_max = min(np.abs(1/np.linalg.eig(np.dot(A,D_inv))[0]))
pr = nx.pagerank(G, 0.85*alpha_max)
pr = np.array([pr[i] for i in pr.keys()])
nx.draw(G, with_labels = True, node_size = 1000*pr, node_color = pr, cmap = "Blues", font_size = 8, edge_color = "gray", edgecolors = "black", pos = nx.kamada_kawai_layout(G))
Summary
We have derived a family of centrality measures that are all centered around degree. We could provide a neat summary of these four measures we’ve seen so far in the table below.
| With Constant | Without Constant | |
|---|---|---|
| Divide by out-degree | PageRank: \({\bf c} = \left(I-\alpha D^{-1}\right)^{-1}{\bf 1}\) | Degree: \({\bf c} = AD^{-1} {\bf c}\) |
| No division | Katz: \({\bf c} = (I-\alpha A)^{-1}{\bf 1}\) | Eigenvector: \({\bf c} = r A {\bf c}\) |
Path-based Centrality Measures
All of the centrality measures we’ve explored thus far are built off variations on the theme of scoring importance based on the number of adjacent nodes. However, an alternate way to think about importance is through a node’s impact on network connectivity through paths.
Closeness Centrality
One way to encode this type of importance would be to start with the assumption that a node should have high centrality if it was a small distance to many other nodes. This might be important in transportation or geographic networks, for example.
Consider a connected graph \(G\). Suppose \(d_{ij}\) is the shortest (geodesic) distance from node \(i\) to node \(j\) (that is, the walk of minimum length from \(i\) to \(j\)). Then, the mean shortest distance \(l_i\) from node \(i\) to any other node in the network is
\[ l_i = \frac{1}{n-1} \sum_{j=1}^n d_{ij} \,. \]
Notice that the qualitative behavior of this quantity is the opposite of what we might usually define for centrality: it has small values for nodes that are separated by others only a short distance (on average) and larger values for longer average distances. If we want our centrality score to be larger for nodes that are close to many other nodes, one way to achieve this is to take the reciprocal. This strategy gives the closeness centrality \(c_i = \frac{1}{l_i}\) of node \(i\). This centrality measure dates back to (at least) 1950 from Bavelas (1950).
Show code
from matplotlib import pyplot as plt
import networkx as nx
import numpy as np
plt.style.use('seaborn-v0_8-whitegrid')
def unweight(G):
for source, target in G.edges():
G[source][target]['weight'] = 1
return G
G = unweight(nx.karate_club_graph())
## Closeness
closeness = nx.closeness_centrality(G)
closeness = np.array([closeness[i] for i in closeness.keys()])
nx.draw(G, with_labels = True, node_size = 1000*closeness, node_color = closeness, cmap = "Blues", font_size = 8, edge_color = "gray", edgecolors = "black", pos = nx.kamada_kawai_layout(G))
This centrality measure has a clear disadvantage for directed or disconnected networks, as it requires the geodesic distance to be defined for all nodes. One simple strategy to fix this would be to compute closeness by only summing geodesic distance to nodes in the same (strongly) connected component. However, be aware that you may not be able to compare centralities between components if you use this strategy: nodes in smaller components will tend to have higher closeness than they would in larger components.
Another strategy is to compute the reciprocal of the harmonic mean of the distances, which is a modification by Beauchamp (1965) sometimes referred to as harmonic centrality:
\[ c_i = \frac{1}{n-1} \sum_{j \neq i, \ d_{ij}<\infty} \frac{1}{d_{ij}} \] where we take the convention \(\frac{1}{d_{ij}} = 0\) if \(i\) and \(j\) are not path-connected.
Betweenness Centrality
Another possibility in using paths to measure importance is to encode the idea that a node is important if it lies on paths between many other nodes. Nodes like this might be important because their removal could disrupt paths. Depending on the application, nodes that lie on many paths may have information, goods, data, etc. that pass through frequently.
Let’s start by considering an undirected network with at most one shortest path between nodes. Let \(n_{st}^i = 1\) if node \(i\) lies on the shortest path from node \(s\) to node \(t\) and 0 otherwise. Then, we could sum the number of these unique shortest paths for node \(i\) as
\[ x_i = \sum_s \sum_t n_{st}^i \,. \]
Accounting for the fact that shortest paths may not be unique gives us our definition of betweenness centrality below.
Direction of travel is accounted for in this definition, and so this can be used without modification in directed networks.
Show code
from matplotlib import pyplot as plt
import networkx as nx
import numpy as np
plt.style.use('seaborn-v0_8-whitegrid')
def unweight(G):
for source, target in G.edges():
G[source][target]['weight'] = 1
return G
G = unweight(nx.karate_club_graph())
## Betweenness
betweenness = nx.betweenness_centrality(G)
betweenness = np.array([betweenness[i] for i in betweenness.keys()])
nx.draw(G, with_labels = True, node_size = 1000*betweenness, node_color = betweenness, cmap = "Blues", font_size = 8, edge_color = "gray", edgecolors = "black", pos = nx.kamada_kawai_layout(G))
This centrality measure seems to have originated from Freeman (1977). There are many additional variants and generalizations of betweenness centrality that can be found in the literature.
References
© Heather Zinn Brooks and Phil Chodrow, 2024