Hey all,

I *just* finished week two of spring semester and I already have quality political science/math material? Say what? I got quite distracted this morning and fell-down the math rabbit hole. So, RIP to all the readings I should have been doing for class when I was instead doing this…

One of my classes this semester is Inferential Network Analysis, which so far I am loving!

In the abstract, the term network in political science is synonymous to graph in mathematics. However, instead of caring about the combinatorial curiosities some graph theorists are interested in, political scientists care about the substantive meaning of the edges and how they impact the network structure, and what they can tell us about relationships between vertices.

A Graph, G, is any collection of vertices and edges, a network has the exact same structure, except the vertices could correspond to Senators, and the edges between them represent if they have cosponsored the same bill.

One of the statistics of interest for a given network at the node-level (as opposed to the network-level) is how influential a node is in a network. This can be measured in multiple ways, the three most common are: degree centrality, closeness centrality, and eigenvalue centrality.

In case you didn’t assume based on the title of this post, this post explores the mathematics behind eigenvector centrality.

Eigenvector centrality is a measure of a vertex’s influence within a network. It measures a vertex’s “power” and it does so by summing the relative influence of a node’s connections. This implies that a vertex’s power will depend on how powerful it’s friends are.

ex: Frankie Jonas is only famous because he is connected to Joe, Nick and Kevin Jonas, but powerful friends can lead to influence, spending on the network of interest.

If a vertex has a high eigenvalue centrality score, this implies the vertex is connected to many vertices who themselves have high scores.

Let’s dig into some notation!

As a reminder, an adjacency matrix is commonly used to store graphs, it looks like this:

A Graph can either be directed or undirected. A direct graph doesn’t assume that the relationship (via the edge) is reciprocated. In adjacency matrix format, you can tell if a graph is directed if the matrix is symmetric, aka if you fold the matrix in half on the diagonal, it is the exact same.

Now that we have that notation down, we can move into the formal definition of eigenvector centrality (relative centrality).

The eigenvector centrality score of a vertex v is defined as:

 

It is important to note that this equation is defined recursively, it requires finding the eigenvector centrality of all of it’s neighbor nodes.

EX: For example, consider a small example where there are four vertices v1,v2,v3,v4. With graph (left) and corresponding adjacency matrix (right).

To find the eigenvector centrality scores for each vertex (v1,…v4), you apply the definition above like so:

Thankfully (for solving purposes), the original equation can then be written in vector notation as:

So, you just have to solve for lambda and you have the resulting x vector with centrality scores that you are looking for.

Now, how do you do this? Linear algebra. What is more interesting (at least to me) is in the political science literature they add, as a note, that all entries in the eigenvector must be non-negative, so only the greatest eigenvector gives the centrality scores (by Perron-Frobenius theorem).

They hide this math fact, when really they should be screaming:

(by Perron-Frobenius theorem)!

 

Why should they be screaming? Because it is so cool! How do you prove that the largest eigenvalue exists? It is intuitive that the largest eigenvalue gives you what you want (well, kinda, I’m just assuming it’s for the same reason you choose the largest eigenvalue in PCA, because it explains most of the variance). But it’s existence!? Wild, and your whole measure depends on it!

So, without further ado, the proof of the Perron-Frobenius theorem in question (as it turns out Perron-Frobenius did a lot, so we will focus on just one proof).

Theorem 1: If A is a positive matrix, then there exists a real positive eigenvalue r, which is strictly greater in absolute value than all other eigenvalues, hence r is the spectral radius of A.

Now, don’t panic! I know you are probably wondering what the heck is a spectral radius (I certainly was). And it is an example of math over math-ing things, all it means is the maximum eigenvalue in absolute value.

So, now that we have all the pieces we need, we can put it together to construct the proof!

And there you have it, proof of (one of) the Perron-Frobenius Theorem(s). This proof demonstrates that the largest eigenvalue exists. A big caveat is that this proof requires your matrix to be positive, which in our case isn’t an issue, as it is an adjacency matrix.

And, that’s it! We’ve done it! Don’t you feel warm and bubbly inside at having proved something? I sure do.

Happy Friday, folks! (I have a busy weekend of reading for Public Opinion ahead).

Also, s/o to Jacob Ogden for helping me understand some of the proof!

 

Resources:

https://en.wikipedia.org/wiki/Eigenvector_centrality

https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Proof_for_positive_matrices

Hafner-Burton, Emile M. and Alexander H. Montgomery. Centrality in Politics: How Networks Confer Power. http://opensiuc.lib.siu.edu/cgi/viewcontent.cgi?article=1007&context=pnconfs_2010