Skip to main content

A Comparison of Harmonic Centrality and PageRank

In class, we learned about the PageRank algorithm, which is used as a measure of centrality to determine the importance of websites. The PageRank algorithm uses a node’s neighborhood to determine its importance. Essentially, the more important pages that point to a given page A, then the more important page A becomes. This article discusses other measures of centrality, specifically Harmonic Centrality, which is a distance-based centrality measure. Harmonic Centrality differs from the PageRank algorithm, in that it looks at the distances of a node’s neighbors.

Here is an example of how harmonic centrality works. If there are 50 pages linking directly to a page A, they are called pages at distance 1, so the count begins at 50. Next, there may be pages linking to page A indirectly at a distance of 2. If there are 100 of these pages, the count is 100/2 = 50 so we add 50 to get a score of 100. There might also be pages at distance 3 from page A with 150 links, so the count is 150/3 = 50, which makes the total score of 150.

Comparing PageRank and Harmonic Centrality on small graphs gives similar results, but the computation time for Harmonic Centrality is much less. On large graphs, PageRank and Harmonic Centrality give the same results for top pages, but then begin to differ greatly on the rest of the pages. In the graphs below, the x-axis represents the score received from the algorithm and the y-axis represents the number of nodes with that score.

PageRank distributionHarmonic Centrality distribution

We can see that the PageRank distribution graph is highly right-skewed, which means that the majority of the pages have very low PageRank. Meanwhile, the Harmonic Centrality distribution is not highly right-skewed and more multi-modal.

This suggests that we can also look into measures of centrality besides the PageRank algorithm, and the differences between these two measures can be used to bring us many new insights to graphs.


Leave a Reply

Blogging Calendar

October 2019
« Sep   Nov »