Centrality Algorithms

Centrality algorithms

In network analysis, centrality measures identify the most important or influential nodes within a graph. The centrality concepts were first introduced in social network analysis to identify key players within a social network, but have since found applications in a variety of industries and fields.

Product supported:

  • PageRank

  • Betweenness Centrality

Labs implementations:

  • Degree Centrality

  • ArticleRank

  • Closeness Centrality

  • Harmonic Centrality

  • Eigenvector Centrality

PageRank

PageRank is Google’s popular web page ranking algorithm.

It works by counting the number and quality of links to a node to estimate its significance. The underlying assumption is that a node is only as important as the nodes that link to it. An example of this type of influence might be having the ear of a general that considers you very credible will likely make you more powerful than being popular with your fellow foot soldiers.

PageRank step 1

PageRank measures importance in comparison to other nodes using an iterative process to update ranks. It starts by assigning values to nodes as 1/n (n is the total number of nodes linked to) and value to relationships as that nodes value/number of its outgoing links.

PageRank step 2

It then starts to update values for nodes as the sum of the prior in-link values. The relationship values are updated the same way they were initially assigned.

PageRank step 3

PageRank then continues to update values until an iterate value is reached.

There are many domain-specific variations for differing analyses, e.g. Personalized PageRank for personalized recommendations. Personalized PageRank is a variation of PageRank, which is biased towards a set of predefined source nodes.

Why use PageRank?

Here is why you use PageRank:

  • Recommendations

  • Fraud Detection

  • Feature engineering for machine learning

Here are some examples:

  • Twitter uses Personalized PageRank to present users with recommendations of other accounts that they may wish to follow. The algorithm is run over a graph that contains shared interests and common connections.

  • PageRank has been used to rank public spaces or streets, predicting traffic flow and human movement in these areas. The algorithm is run over a graph of road intersections, where the PageRank score reflects the tendency of people to park, or end their journey, on each street.

  • PageRank is also used as part of an anomaly and fraud detection system in the healthcare and insurance industries. It helps reveal doctors or providers that are behaving in an unusual manner and then feeds the score into a machine learning algorithm.

  • Find the most influential features for extraction in machine learning and rank text for entity relevance in natural language processing.

Guided Exercise: Getting Started with the PageRank algorithm

Follow along with this video to become familiar with PageRank in Neo4j NEuler.

Exercise: PageRank

  1. In NEuler:

    1. Perform the PageRank analysis on different seasons of GOT.

  2. In Neo4j Browser: :play 4.0-intro-graph-algos-exercises and follow the instructions for PageRank.

Estimated time to complete: 15 minutes

Betweenness Centrality

Sometimes the most critical cog in the system is not the one with the most overt power or the highest status. Sometimes it is the middlemen who connect groups or brokers with the most control over resources or information flow.

Betweenness Centrality is a way of detecting the amount of influence a node has over the flow of information in a network. It is typically used to find nodes that serve as a bridge from one part of a graph to another.

Betweenness centrality

The Betweenness Centrality algorithm first calculates the shortest path between every pair of nodes in a connected graph. Each node receives a score based on the number of these shortest paths that pass through the node. The more shortest paths that a node lies on, the higher its score.

Betweenness Centrality does not scale well on large graphs as the algorithm has to calculate the shortest path between all pairs of nodes in a network. Because of this, approximation algorithms of Betweenness Centrality were developed to allow for a faster calculation. The RA-Brandes algorithm is the best-known algorithm for calculating an approximate score for Betweenness Centrality. Rather than calculating the shortest path between every pair of nodes, the RA-Brandes algorithm considers only a subset of nodes. Brandes defines several strategies for selecting the subset of nodes. The GDSL implementation is based on the random degree selection strategy, which selects nodes with a probability proportional to their degree. The idea behind this strategy is that such nodes are likely to lie on many shortest paths in the graph and thus have a higher contribution to the Betweenness Centrality score.

Why use Betweenness Centrality?

Here is why you use Betweenness Centrality:

  • Identify bridges

  • Uncover control points

  • Find bottlenecks and vulnerabilities

Here are some examples:

  • Betweenness Centrality is used to identify influencers in various organizations. Powerful individuals are not necessarily in management positions, but can be found in “brokerage positions” using Betweeness Centrality. Removal of such influencers seriously destabilize the organization. This might be a welcome disruption by law enforcement if the organization is criminal, or may be a disaster if a business loses key staff it never knew about.

  • Betweenness Centrality uncovers key transfer points in networks such electrical grids. Counter-intuitively, removal of specific bridges can actually improve overall robustness by “islanding” disturbances.

  • Betweenness Centrality is also used to help micro-bloggers spread their reach on Twitter, with a recommendation engine for targeting influencers.

Guided Exercise: Getting Started with the Betweenness Centrality algorithm

Follow along with this video to become familiar with Betweenness Centrality in Neo4j Neuler.

Exercise: Betweenness Centrality

  1. In NEuler:

    1. View the Betweenness Centrality scores for other GOT seasons and examine the paths in Neo4j Browser for these nodes.

    2. View the approximate Betweenness Centrality scores for GOT seasons and see how various sampling sizes affect the results.

  2. In Neo4j Browser: :play 4.0-intro-graph-algos-exercises and follow the instructions for Betweenness Centrality.

Estimated time to complete: 15 minutes

Check your understanding

Question 1

Which of the following Centrality algorithms are fully-supported?

Select the correct answers.

  • Degree Centrality

  • PageRank

  • Closeness Centrality

  • Betweenness Centrality

Question 2

What are some practical use-cases for the PageRank algorithm?

Select the correct answers.

  • Recommendations

  • Find bottlenecks in a network

  • Fraud detection

  • Identify bridges in a network

Question 3

Which algorithm is used to determine the "middleman" in a network that might be used to connect parts of a graph?

Select the correct answer.

  • PageRank

  • Betweenness Centrality

  • Weakly Connected Components

  • Local Clustering Coefficient

Summary

In this lesson, you gained experience with the two Neo4j supported Centrality algorithms:

  • PageRank

  • Betweenness Centrality

You can read more about these algorithms and also the alpha (labs) algorithms in the Graph Data Science documentation