Centrality & Maximal Entropy Random Walks
Node centrality can be tricky to measure if it is not assumed the whole graph structure is accessible. However, approximation techniques can be used (in particular, an approximation to maximal entropy random walks) to determine central nodes.
One of the definitions of centrality for a graph is eigenvalue centrality. Eigenvalue centrality is useful in that it takes into account the centrality of neighbors (and, recursively, neighbors of neighbors and so on). Solving the eigenvalue problem for a graph adjacency matrix is best done numerically. Once finished, every node in the graph receives an appropriate centrality score.
However, it may be that the structure of the whole graph is not available all at once. For example, consider the social network of friends as defined on all people- obtaining the structure of this graph requires interviewing every person on Earth and asking them to list their friends out. If we permit the existence of local information (for example, the results of interviewing one person), then it may be possible to determine approximate notions of centrality.
In the case of degree centrality this is easy and uninteresting: each person’s score is simply the number of people they know. However, it turns out more sophisticated notions of centrality can also be
The idea is to employ random walks that have high probabilities of being in more central nodes. Random walks on graphs are defined by the probability of travelling along edges conditioned on the current location of the walker. The maximal entropy random walk is essentially the random walk given by uniformly choosing at random a direction among all possible paths in the graph that go through that edge (contrast this with the uniform random walk, which chooses each edge uniformly at random).
But wait! Isn’t it the case that one would need the global structure of the graph in order to determine the space of “all possible graphs through an edge”? This is in fact the case; however, an approximation to the maximal entropy random walk is possible to define up to an order which represents neighbor distance; for example, using an order 2 approximation to the random walk in the social network problem would consist in interviewing all people with a degree of separation equal to 2 from the current person.
A lot of these subjects were really cool to investigate. Eigenvalue centrality (and other more exotic notions of centrality based on it) introduced me to spectral graph theory, which is a fascinating subject on its own; but better yet, my existing love for numerical analysis, linear algebra, and approximation algorithms blends perfectly with spectral graph theory because all-too often the underlying graph is simply too large for any other technique to work (for example, links between webpages).
In a similar vein, random walks (and maximal entropy random walks in particular) fall almost exactly into the same niche, except with probability theory thrown in. Once again, approximation is necessary.
For those interested in proofs and pretty diagrams, I have written up a more rigorous and detailed treatment on the subject.
I have also given presentations about this exact topic; here is the slide deck I use.
The implementation and diagrams are from the following Mathematica files.
Notebook 1, Notebook 2
Next: Dota 2 Drafting Part 1: Data Collection