What is centrality?

Every centrality algorithm provides each node with a score, ranking nodes by importance. Each algorithm's definition of "importance" varies.

In this lesson, you will consider how these behaviors interact with the following example graph; it holds eight nodes and nine relationships.

For mnemonic purposes, we can arrange centrality algorithms into six loose families.

The six initials spell TARGET.

Although there are behavioral variations, even within each family, family-members share a certain approach or perspective.

For some families, the Graph Data ScienceiGo to glossary for graph data science (opens in a new tab)Analysing data through the structure of its connections. Also the name of the Neo4j library that implements it. library contains many variations on a theme. For others, it provides only one.

Algorithms in the Ties family describe each node's local characteristics.

Count the relationships on each node in the example graph, then compare your counts with the table that follows.

The Graph Data Science library offers Degree CentralityiFull definition for degree centrality (opens in a new tab)A score for each node equal to its number of outgoing relationships. as the only member of this family.

Algorithms in the Articulation family rank nodes and/or relationships by their "importance" to structure.

Go back to your example graph. Consider what would happen to the entire graph if you removed one, and only one, node. Run the experiment for all nodes.

The following table outlines what would happen.

The Graph Data Science Library provides Articulation Points and Bridges as members of this family.

Algorithms in the Reach family rank nodes by how far they sit from every other node.

Pick two nodes in the example graph. Count the hops along the shortest path from each one to the other seven nodes. Then, decide which one can reach more nodes, faster than the other.

The following table holds the full count for every node.

The Graph Data Science library provides Closeness Centrality and Harmonic Centrality as members of this family.

Algorithms in the Gatekeeping family rank nodes by how often they sit on the shortest path between two other nodes. They consider a node's position relative to every other node in the graph.

Take a look at your example graph. See if you can intuit which node would lie on the most shortest paths between all pairs.

The following table counts the pairs whose shortest path runs through each node.

The Graph Data Science library offers Betweenness CentralityiFull definition for betweenness centrality (opens in a new tab)A score for each node equal to how often it lies on the shortest paths between other nodes. as the only member of this family.

Algorithms in the Endorsement family rank nodes by the importance of the nodes attached to them. A relationship from a high scorer is worth more than a relationship from a low-scoring node.

Go back to your example graph. Take each node in turn, and count the relationships held by each of its neighbours.

The following table ranks each node by the number of relationships held by its neighbors.

Every node's score depends on the scores of its neighbours. Those neighbour scores are themselves still being worked out. Each algorithm in this family resolves that circularity by iterating over the graph until the scores stop moving.

The Graph Data Science library provides Page Rank, Article Rank, Eigenvector Centrality and HITS as members of this family.

Algorithms in the Teams family score a group of nodes rather than a single node.

Go back to your example graph. Try to intuit which two nodes together would reach the greatest number of nodes.

The following table holds that count for four of the best possible teams.

A node that reaches a great many nodes adds little to a team when somebody already chosen reaches the same nodes.

The Graph Data Science library offers CELF (Cost-Effective Lazy Forward) as the only member of this family.

Each of the families you have just considered defines "centrality" or "importance" differently.

How those differences impact your analyses relies on your analytical intent.

To make each one more comprehensible, you could reframe their behaviors as questions, instead.

These are generalized examples — your specific questions could differ, depending on your graph's structure.

Regardless, you can pick the family required by identifying which of these kinds of questions the algorithm could answer.