Node Centrality Algorithms Explained
A Survey of Fundamental Node Statistics in Graph Theory
This article is intended for readers who are already familiar with the very basic concepts in Graph Theory, such as nodes, edges, directions, and components. The focus here is to facilitate in-depth understanding of the different node centrality algorithms often available in programming libraries in terms of their mathematical explanations.
There are many available metrics to measure the importance of a single node within a connected or disconnected graph. Below metrics will be covered:
- Degree Centrality
- Eigenvector Centrality
- Katz Centrality
- PageRank Centrality
- ArticleRank Centrality
- Hubs and Authorities
- Closeness Centrality
- Harmonic Centrality
- Betweenness Centrality
Degree Centrality
Degree centrality is the most intuitive and straightforward metric in a network. The degree of a node refers to the number of edges attached to the node within the context of a non-directional network. The idea is that nodes with more connections tend to have more influence.
The math behind is simple: suppose we have a total of n nodes in the network, with a total of m edges connecting them, and for a certain node i with number of edges kᵢ, its degree centrality xᵢ is calculated as the number of edges on itself normalized by the total number of edges in the network:
When used within a directional network, we also need to differentiate in-degree and out-degree for each node. For future simplicity, all the below examples will refer to directional networks unless explicitly specified.
Note that the degree centrality returned is a floating-point vector with its elements summing up to 1, which is also a probability distribution. This is a neat characteristic, hence degree distribution can be used in graph modeling practices such as configuration models.
Eigenvector Centrality
While degree centrality certainly makes sense, it only considers the influence of individual nodes within their local neighborhood and does not count in the transitivity of influence within the entire network. The idea of eigenvector centrality is that influence can be seen as a dynamic process that pass through layers of connections instead of remaining static.
Taking social media for example, person A may have one thousand connections. However, none of them has been publicly known for anything. Person B may only have three connections, who are respectively Bill Gates, Elon Musk and Dwayne Johnson. Eigenvector centrality aims to allocate higher centrality scores to nodes like person B.
The eigenvector centrality of a single node is defined to be proportional to the sum of the eigenvector centrality of all of its neighbors, which is apparently a recursive problem with no base case. That is, for every node whose centrality is adjusted, the centrality must also be adjusted for all other nodes accordingly based on this transitivity rule.
Fortunately, the adjacency matrix provides a shortcut to find the centrality distribution values such that all the proportions work out perfectly and need not to be adjusted further. Each element of the matrix, Aᵢⱼ, encodes the directional connection from node j (column index) to node i (row index). For now assume the connections has no weights so the matrix is binary.
It happens that what we are looking for is exactly the stationary distribution of the adjacency matrix as a Markov Chain. The leading eigenvector x of the adjacency matrix A produces the desired centrality distribution such that when it’s multiplied by the matrix itself, the result is equivalent to multiplying the distribution by a scalar, hence the distribution produced is in proportion to the existing distribution.
To calculate the eigenvector centrality, we simply need to find the leading eigenvector x, and each of its element xᵢ is the centrality score for node i:
A very useful mathematical theory guarantees that we can find the leading eigenvector for all adjacency matrices, that is the Perron-Frobenius Theorem, which states that one and only one non-negative eigenvector exists for a non-negative matrix, and that is the leading eigenvector, the one corresponding to the largest eigenvalue. This is why I love the beauty of linear algebra!
Katz Centrality
Amazing as it is, there is one deficiency about the eigenvector centrality — the eigenvector only examines the out-component, for the left-eigenvector needs to be calculated for the eigenvector centrality of the in-component. If a directional path origins at a node, which does not have an incoming edge, the eigenvector centrality for that node will be zero, regardless the many outgoing edges it has (which is, however, a good example of an authority node, which will be explained later). As a result of the transitivity rule, all the nodes down the path without other incoming sources will also have eigenvector centrality zero regardless of their outgoing activities. Oops!
One simple solution is to assign a small positive constant to all the eigenvector centrality scores to begin with and activate the chain reaction. Once the nodes previously assigned with zero scores received the small positive amount, it will be passed along to all of its outgoing neighbors. That is
So we can deem the Katz centrality as a modification of the eigenvector centrality with a weight coefficient α, and an added bias term β. This will end up with a different stationary distribution. Since we only care about the node importance in relative terms, the actual scale of these scores doesn’t matter, and we can arbitrarily choose the constant to be 1 to ease computation. Choosing any α bounded by the eigenvalue multiplicative inverse will converge to a distribution satisfying the above equations of Katz centrality, but using a weight close to the supremum as possible preserves the effectiveness produced by the eigenvector centrality distribution.
PageRank Centrality
The PageRank centrality aims to further improve the Katz centrality. The challenge is that one node with a high number of outgoing edges can pass its own high centrality score to all the downstream nodes using eigenvector or Katz centrality scores. The question is how exclusive the connections are.
Using social media for example again, if I have a YouTube channel and Bill Gates subscribed to it, it is not a big deal if he also subscribed to a thousand other channels, but it would be a big deal if he only subscribed to three and one is mine, which immediately speaks for the importance.
The idea is to dilute the transitive influence proportionally to the number of nodes sharing the influence by normalizing incoming influence that node i received from node j by node j ’s out-degree kⱼ^out. For nodes without out-degrees, we can arbitrarily set the denominator to 1 and not to worry about it since the numerator is meant to be 0. Mathematically, that is
Most interesting is its matrix form:
where D is the diagonal matrix filled with the out-degrees with index order, which is really machine-efficient when it comes to numerical evaluation.
It’s worth mentioning that Google named this algorithm PageRank primarily not because it is useful for finding relevant webpages, but after its founder Larry Page, or we could say it’s a really nice double entendre.
ArticleRank Centrality
ArticleRank is a novel algorithm adapted from PageRank, designed specially to measure influence of journal articles within citation networks. Based on the fact the PageRank algorithm normalizes incoming centrality by the out-degree of source node, it means that transitive centrality received from high-connectivity nodes are lower and vice versa. The ArticleRank algorithm aims to counteract with this artificial correction and lower the influence originated from low-connectivity nodes with an iterative scheme.
It employs a damping ratio d which is a scaling parameter between 0 and 1 to lower incoming node importance over iterations. Adapting notations from the original paper to the convention used in this article we get:
where t is the iteration epoch index. This algorithm does not apply to most of the networks we are interested in so it won’t be discussed in details.
Hubs and Authorities
The above centralities more or less focus on the spread of influence a single node can exert within the network, which makes most sense within the context of social networks. In certain situations when the network itself represents flow of information or resources, such as citation network or money transfer network, the interactions are often one-way traffic. The graph structures under these circumstances are acyclic and hierarchical.
Hubs and authorities are important nodes within hierarchical networks. Simply put, the authorities are the nodes that possess the most information who everyone else resorts to and the hubs are those who can access the authorities and bridge the information to others.
Using homework help for example, 5 students all need to answer the same questions for homework and only student A knows how but they are allowed to help each other. Student A only helped student B, who then helped students C, D, and E. In this case, student A has only 1 outgoing connection but is the ultimate source of information and therefore is the authority node, student B served as the proxy of information and distributed it to rest of the network and therefore is the hub node.
The concepts were first introduced along with an algorithm called Hyperlink-Induced Topic Search (HITS). The official definitions are: a node with high authority centrality is pointed to by many nodes with high hub centrality. And vice versa, a node with high hub centrality points to many nodes with high authority centrality. Accordingly, the mathematical expressions are:
The two equations seem intertwined, but easy to solve when using matrix form with variable substitution:
Hubs and authorities as centrality metrics are formulated differently from others. Student A doesn’t have many connections (and no incoming edge) but played a very important role in the information dispersion process. These concepts are very useful in real-world practices when it comes to intercepting unwanted network activities such as organized crimes, public misinformation or epidemic spread.
Closeness Centrality
The closeness centrality is calculated based on the concept of distance between nodes, which projects the graph into a geometric space. The distance between any two nodes is the integer steps taken along the shortest path possible to connect these two nodes. One caveat is that if two nodes are not connected via any path, the distance between is infinity, which we will discuss later. The distance from one node to itself is zero.
The idea is to not only consider the first-depth connections when measuring node importance, but also to count in how many nodes can be indirectly influenced on each of the depth within the network. Apparently, those who are closer to more nodes should be considered more important than those whose connections are mostly remote (probably on the margin of the graph). The closeness centrality score is designed for this exact purpose.
First, consider the mean shortest distance from node i to every node in the network which has a positive correlation with the total distances:
We want the nodes with overall shorter distances to have a high centrality score, so use the inverse of above to produce closeness centrality score:
The most obvious problem with this metric happens when the graph is disconnected. Say, if two nodes respectively belongs two disconnected components, their distance will be infinity, which becomes a numerical nightmare. Therefore, the closeness centrality is usually used within the precondition that for each node it is calculated within its own component.
Harmonic Centrality
A better way to measure the distance-based centrality is to invert it before taking the average. This way shorter distances automatically contribute to higher scores. The harmonic centrality is a modification of the closeness centrality by taking the average of inverse shortest distances:
This time we don’t consider the measured node itself, since the distance from itself is zero, which cannot be divided. In the case of disconnected nodes when the distance is infinity, we can algorithmically assign the rational term to be 0, which won’t make a difference to the final score, but will work fine for disconnected graphs as well.
Betweenness Centrality
Betweenness centrality examines node importance from a totally different perspective. Instead of caring about the magnitude of connections, this metric checks how often a node stays in between others.
A drama-version example would be two feuding families connected through one mediator. All members within each family are all close to each other thus forming a dense social network cluster but not directly connected to anyone in the other family. Each family sends out one representative who can talk to the mediator. The mediator, the person in between two large dense clusters, only has two direct connections in the entire network, but plays a non-neglectable role in the social interchanges. Any communication between any two people from the different families has to go through the mediator who stays on the most paths within the network. Similarly, the two family representatives are equally important because they are topologically equivalent (homotopic) to the mediator and have the same betweenness centrality.
Mathematically, betweenness centrality for a node i on a network is defined as the sum of betweenness factors, each such factor considering a pair of source node s and target node t, and calculating the ratio of number of shortest paths from s to t through node i to the total number of shortest paths available in the network from s to t, permutating all possible source and target nodes.
Betweenness centrality is useful for practicing node removal procedures, similarly to hubs and authorities, but different in that it applies not only to hierarchical networks but the general ones. Additionally, it can be incorporated into graph partitioning algorithms that satisfies certain requirements such as subgraph compactness or minimum cut-edges, etc.
References:
- Mark Newman, Networks (2nd Edition), Oxford
- Neo4j Graph Data Science Library Documentation
Disclaimer: Many of the mathematical explanations used in this article are based on Prof. Newman’s work. A ton of valuable information are left out from the original book since this article serves a specific audience. If one is truly interested in learning Graph Theory in depth, I strongly recommend buying his book. I myself am a huge fan.
