Graphs help us understand the real world better by mathematical abstractions and models in order to define the entities and the relations between them in structures.

Many real-world applications use graphs, including search engines.

Search engines use graphs for different purposes, such as understanding the popularity of pages or detecting spam links.

Centrality is an important concept used for graphs. We use a quantitive measure called centrality measure to discover the importance of the nodes which are essential units forming a graph.

A very popular search engine is known to identify the popularity of nodes (webpages) by using PageRank as the measure of centrality. PageRank has been the most famous centrality measure for graphs.

There are some other measures such as:

- Eigenvector.
- Betweenness.
- Katz.
- Closeness.
- Hits (Hyperlink-Induced Topic Search).
- Harmonic Centrality.

In this article, I will focus on “Harmonic Centrality” because it is a promising and, in theory, low-cost measure of centrality.

## Harmonic Centrality

Harmonic centrality is a much recent measure than most of the other centrality measures and a variant of another measure that is closeness centrality.

It was first proposed by Massimo Marchiori and Vito Latora in 2000, then by Dekker (2005) and Rochat (2009).

Harmonic Centrality is the distance-based centrality measure, unlike PageRank.

In the PageRank algorithm, the importance of a node is given by the importance of the neighborhood but not the distance. The more important pages point a page, the more important that page becomes.

To understand harmonic centrality in simple terms, here’s an example.

Imagine there is a page called example.

If there are 50 pages linking directly to this page, they are called as pages at Distance 1, and you begin your count as 50.

There may be pages linking to example page but not directly so we call them Distance 2. Let’s say there are 100 such pages, this time we count as 50 and add to the 50 we have making our score 100.

There can be pages in Distance 3 with 150 links this time. So we count as 50 which makes our total score of 150.

It is much easier to understand than PageRank, isn’t it?

## Best Centrality Measure

Harmonic centrality can be selected as one of the easiest centrality measures to understand and we can stop there.

However, it has also been selected as the best centrality measure in a scientific paper. The authors of the research, Paolo Boldi and Sebastiano Vigna describe the best centrality measure with these words:

“Our results suggest that centrality measures based on distances, which in the last years have been neglected in information retrieval in favour of spectral centrality measures, do provide high-quality signals; moreover, Harmonic Centrality pops up as an excellent general-purpose centrality index for arbitrary directed graphs.”

There is a compelling video titled “A Modern View of Centrality Measures” where Boldi talks about the centrality measures in general and harmonic centrality in particular.

In the video, he also presents a comparison of PageRank and harmonic centrality measurements on the Hollywood graph. In his specific example, harmonic centrality selects top nodes better than the PageRank.

Additionally, nonprofit organization Common Crawl which has been crawling the web since 2011 prefer this centrality measure.

Since 2017, Common Crawl has been using harmonic centrality in their crawling strategy for prioritization by link analysis.

When they list domain level information in their blog posts, the domains are ranked according to their harmonic centrality values, not to their PageRank values.

In this article, I will conduct data analysis to find out if its calculation cost is less than PageRank.

There is software that approximates harmonic centrality for very large graphs in order to further reduce its computation cost. I haven’t used it but it’s worth mentioning in case you want to try it out yourself.

For search engines and for SEO, harmonic centrality is a useful centrality measure because it:

- Is simple to understand and explain.
- Gives intriguing results on web graphs.
- Is not a metric which needs iteration, thus its calculation cost can be less in theory.

## Comparing Harmonic Centrality & PageRank

### Comparison on Small Graphs

**Homemade Graphs**

**Dataset information**

I created some very small web graphs and calculated the nodes(pages) PageRank and five other centrality measure values in order to compare them and give you a better understanding of Harmonic Centrality measure.

Imagine very small websites having a homepage, as well as category and product pages. Let’s use H, C1, C2, P1, P2, P3, P4 as aliases for the homepage, first, second category pages and first, second, third and fourth product pages, respectively.

- H = Homepage
- C1 = Category page 1
- C2 = Category page 2
- P1 = Product page 1
- P2 = Product page 2
- P3 = Product page 3
- P4 = Product page 4

I calculated PageRank and five centrality measures on these very small datasets and visualized them as graphs.

For simplicity, only PageRank and Harmonic Centrality graphs are presented. On these graphs, the node sizes show the importance of their chosen centrality measure values.

Centrality measure values compute times on homemade graphs and Stanford-web graph are calculated on MacBook Pro with four cores and 16GB RAM.

**Graph 1**

**Dataset Information**

Pages: 7

Links: 16

**Compute Time**

PageRank

CPU times: user 1.01 ms, sys: 0 ns, total: 1.01 ms

Wall time: 1.02 µs

Eigenvector

CPU times: user 392 µs, sys: 1 µs, total: 393 µs

Wall time: 398 µs

Betweenness

CPU times: user 242 µs, sys: 1e+03 ns, total: 243 µs

Wall time: 247 µs

Katz

CPU times: user 576 µs, sys: 13 µs, total: 589 µs

Wall time: 613 µs

Closeness

CPU times: user 235 µs, sys: 1e+03 ns, total: 236 µs

Wall time: 240 µs

Harmonic

CPU times: user 665 µs, sys: 9 µs, total: 674 µs

Wall time: 689 µs

**Statistics**

**Correlations with PageRank**

Eigenvector: 0.990128

Betweenness: 0.995301

Katz: 0.973233

Closeness: 0.966720

Harmonic: 0.987344

**Graph 1 PageRank**

**Graph 1 Harmonic Centrality**

**Graph 2**

**Dataset Information**

Pages: 7

Links: 14

**Compute Time**

PageRank

CPU times: user 1.01 µs, sys: 0 ns, total: 1.01 µs

Wall time: 1.01 µs

Eigenvector

CPU times: user 393 µs, sys: 1e+03 ns, total: 394 µs

Wall time: 398 µs

Betweenness

CPU times: user 241 µs, sys: 0 ns, total: 241 µs

Wall time: 247 µs

Katz

CPU times: user 499 µs, sys: 1 µs, total: 500 µs

Wall time: 505 µs

Closeness

CPU times: user 224 µs, sys: 1 µs, total: 225 µs

Wall time: 229 µs

Harmonic

CPU times: user 597 µs, sys: 9 µs, total: 606 µs

Wall time: 625 µs

**Statistics**

**Correlations with PageRank**

Eigenvector: 0.999605

Betweenness: 0.917375

Katz: 0.986605

Closeness: 0.946069

Harmonic: 0.975830

**Graph 2 PageRank **

**Graph 2 Harmonic Centrality**

**Graph 3 **

**Dataset Information**

Pages: 7

Links: 10

**Compute time**

PageRank

CPU times: user 2.85 µs, sys: 148 µs, total: 2.99 µs

Wall time: 2.92 µs

Eigenvector

CPU times: user 505 µs, sys: 1e+03 ns, total: 506 µs

Wall time: 510 µs

Betweenness

CPU times: user 153 µs, sys: 1 µs, total: 154 µs

Wall time: 158 µs

Katz

CPU times: user 436 µs, sys: 0 ns, total: 436 µs

Wall time: 442 µs

Closeness

CPU times: user 142 µs, sys: 0 ns, total: 142 µs

Wall time: 146 µs

Harmonic

CPU times: user 283 µs, sys: 1e+03 ns, total: 284 µs

Wall time: 289 µs

**Statistics**

**Correlations with PageRank**

Eigenvector: 0.930335

Betweenness: 0.873700

Katz: 0.996401

Closeness: 0.979220

Harmonic: 0.952115

**Graph 3 PageRank**

**Graph 3 Harmonic Centrality **

**Graph 4**

**Dataset Information**

Pages: 7

Links: 10

**Compute time**

PageRank

CPU times: user 2.76 µs, sys: 374 µs, total: 3.13 µs

Wall time: 2.77 µs

Eigenvector

CPU times: user 730 µs, sys: 177 µs, total: 907 µs

Wall time: 722 µs

Betweenness

CPU times: user 242 µs, sys: 0 ns, total: 242 µs

Wall time: 248 µs

Katz

CPU times: user 330 µs, sys: 0 ns, total: 330 µs

Wall time: 335 µs

Closeness

CPU times: user 210 µs, sys: 0 ns, total: 210 µs

Wall time: 215 µs

Harmonic

CPU times: user 740 µs, sys: 1 µs, total: 741 µs

Wall time: 745 µs

**Statistics**

**Correlations with PageRank**

Eigenvector: 0.993543

Betweenness: 0.998952

Katz: 0.962346

Closeness: 0.998952

Harmonic: 0.997933

**Graph 4 PageRank**

**Graph 4 Harmonic Centrality**

**Plot of the Correlations of 5 Centrality Measures with PageRank on 4 Homemade Graphs**

Labels on X-axis

ec: Eigenvector Centrality

bc: Betweenness Centrality

kc: Katz Centrality

cc: Closeness Centrality

hc Harmonic Centrality

**Mean of the Correlations of 5 Centrality Measures with PageRank on 4 Homemade Graphs**

Eigenvector: 0.979369

Betweenness: 0.938920

Katz: 0.976432

Closeness: 0.975019

Harmonic: 0.97649

Harmonic Centrality has the second highest mean of correlations on four graphs with PageRank after Eigenvector Centrality which is a cousin of PageRank.

**Comparison on Large Graphs**

**Stanford-Web Graph**

**Dataset Information**

This web graph is available here.

Nodes represent pages from Stanford University (stanford.edu) and directed edges represent hyperlinks between them. The data was collected in 2002.

Nodes: 281 903

Edges : 2 312 497

**Compute Time**

PageRank

CPU times: user 1min 17s, sys: 2.3 s, total: 1min 19s

Wall time: 1min 19s

Harmonic Centrality

CPU times: user 1min 18s, sys: 1.96 s, total: 1min 20s

Wall time: 1min 20s

**Statistics**

**PageRank**

mean, min, max of pr_val = 3.547319e-06, 5.681687e-07, 6.512977e-03

**Harmonic Centrality**

mean, min, max of harmonicc_val = 31132.897898, 1.001467, 106023.735213

**Statistics**

**Correlation on 282 K pages**

correlation(pr_val, harmonicc_val) = 0.013566

**Correlations of Top Pages Sorted According to Harmonic Centrality Values**

Top 100

Correlation(PageRank.Harmonic Centrality) = 0.916071

Top 1000

Correlation(PageRank.Harmonic Centrality) = 0.691981

Top 10 000

Correlation(PageRank.Harmonic Centrality) = 0.682505

Top 100 000

Correlation(PageRank.Harmonic Centrality) = 0.012681

These correlation scores above show us that PageRank and Harmonic Centrality algorithms agree on almost the top 10 K pages (not on the pages but the distribution of the importance of the pages) but afterwards, they don’t share the same opinion on other pages’ popularity distribution.

**Number of Intersected Top Pages Between Pagerank and Harmonic Centrality**

In top 100: 8

In top 1000: 66

In top 10 000: 299

In top 100 000: 41 138

**Number of Intersected Weakest Pages Between Pagerank and Harmonic Centrality**

There is no intersection till 10 000 weakest pages but for 100 000 weakest pages the intersection is 23 417.

**Data Visualization **

**PageRank Distribution**

The PageRank distribution graph shows us that this distribution is highly right-skewed meaning the majority of the pages have very low PageRank.

**Harmonic Centrality Distribution**

The Harmonic Centrality distribution is not highly right-skewed so we can’t say that majority of the pages have low values like PageRank. This distribution is multi-modal.

**Scatter Plot of PageRank and Harmonic Centrality **

When we scatter plot the PageRank and Harmonic Centrality values of pages we observe what we have seen in the statistics part which is PageRank and Harmonic Centrality values of domains are not correlated.

**Common Crawl Graph**

**Dataset Information**

On Common Crawl’s recent blog post, they shared a file (cc-main-2018-aug-sep-oct-domain-ranks.txt.gz [1.89 GB]) that provides 87 million domains’ most recent Harmonic Centrality and PageRank values.

Below are the statistics from this file about PageRank and Harmonic Centrality values of 87 million domains.

**Compute Time**

Sebastian Nagel from Common Crawl technical team kindly answered my question about computing time differences between PageRank and Harmonic Centrality algorithms calculations on Common Crawl graph and also allowed me to share his response with you:

“Computation was done on a machine with 48 CPUs and 384 GB RAM using the web graph resp. the law library which was written by Vigna and Boldi.

At a first glance, a look on the “real” wall-clock time and “user” time (used CPU-seconds) would even suggest that the harmonic centrality is faster for the larger host-level graph. However, my guess would be that the processing time is mostly influenced by:

- Graph structure (e.g., amount of dangling nodes).
- The number of iterations until the scores converge.
- (Hyperball / harmonic centrality) size of the hyperloglog counters.”

**Statistics**

**PageRank**

mean, min, max of pr_val = 1.1473075614418515e-08, 4.48131407e-09, 1.72100302e-02

**Harmonic Centrality**

mean, min, max of harmonicc_val = 9421776.2697027, 0. , 24993276.

**Correlations**

**Correlation on 87 Million Domains**

correlation(pr_val, harmonicc_val) = 0.00432823

**Correlation of Top Pages Sorted According to Harmonic Centrality Values**

Top 100

Correlation(PageRank.Harmonic Centrality) = 0.94826372

Top 1000

Correlation(PageRank.Harmonic Centrality) = 0.87727728

Top 10 000

Correlation(PageRank.Harmonic Centrality) = 0.63744096

Top 100 000

Correlation(PageRank.Harmonic Centrality) = 0.31725445

**Data Visualization **

**Pagerank Distribution**

The graph below presents the plot of the count of PageRank values. It shows us that the distribution of PageRank on 87 million domains is highly right-skewed meaning the majority of the domains have very low PageRank.

**Harmonic Centrality Distribution**

The graph below presents the plot of the count of Harmonic Centrality values of 87 million domains. It shows us that the distribution of Harmonic Centrality on 87 million domains is not highly right-skewed like the PageRank.

It is not a perfect Gaussian distribution but more Gaussian than the distributions of PageRank. This distribution is multi-modal too.

**Scatter Plot of Pagerank and Harmonic Centrality**

When we scatter plot the PageRank and Harmonic Centrality values of domains we observe what we have seen in the statistics part which is PageRank and Harmonic Centrality values of domains are not correlated.

However what is also interesting to point out is that we observe the beginning of the domains’ PageRank values detachment when their Harmonic Centrality value is closer to 1e7 and accelerates when it is greater than.

What we remark from web Stanford and Common Crawl, large web graphs data analysis above is that Harmonic Centrality and PageRank agree more or less on the popularity of top and middle tail nodes but not the long tail.

## Conclusion

To begin with, Harmonic Centrality is a measure of centrality that is easy to understand and explain.

Furthermore, it gives interesting results, especially for the top nodes of the graphs.

Last but not least, some organizations are already using this measure, for instance, Common Crawl, a nonprofit organization that has been crawling the web for several years, uses this measure in its crawling strategy.

On small graphs:

- PageRank and Harmonic Centrality give resembling results with PageRank.
- The computation time of Harmonic Centrality is much less than PageRank.

As the size of the graph increases their computation times tend to be similar.

For the sake of clarity, computation times are calculated on small graphs and web Stanford graph with an unoptimized Harmonic Centrality algorithm on a MacBookPro with four cores and 16 GB RAM.

On larger graphs, although PageRank and Harmonic Centrality have similar considerations on the distribution of the importance of top pages, at least for top 10 K pages, their opinions on the popularity distribution of the rest of the pages change dramatically afterwards. They agree more on top and middle tail nodes but less on the long tail.

Common Crawl’s technical team calculated Harmonic Centrality and PageRank on the recent Common Crawl graph with 48 CPUs and 384 GB RAM.

Consequently, Harmonic Centrality’s compute time is less than PageRank on paper. However, there are some lurking variables which may affect the result. Therefore, this issue requires further study.

In conclusion, I highly recommend you to look further into Harmonic Centrality. Its differences with PageRank aren’t negative points, on the contrary, they are positive since it brings us new insights.

Therefore, it will be beneficial for SEO to calculate the Harmonic Centrality values for the pages of your clients’ sites.

Accordingly, this may reveal striking information on those pages which you have not discovered by the help of PageRank. Besides, it is always a good idea to listen to what other algorithms want to tell us.

**More Resources:**

- How Search Engine Algorithms Work: Everything You Need to Know
- PageRank Patent Update – How it Impacts SEO
- 7 Useful Facts About PageRank

**Image Credits**

*In-Post Images: Created by author, January 2019*

### Subscribe to SEJ

Get our daily newsletter from SEJ's Founder Loren Baker about the latest news in the industry!