Centrality Measure in Graph Theory

Graph Theory: Centrality Measures

We have learned the basics of graph theory. Now we can move ahead to learn different centrality measurement methods. Based on an assumption, centrality measurements are scalar values assigned to each node in the graph to assess its significance.

In graph theory, we can define centrality as significance (influence or priority). We assign an importance (centrality) value to the entire graph when we compare graphs. This concept is known as graph centrality. However, when we have a network, we may analyse which vertices are more significant by assigning a value of importance (centrality) to each vertex. This concept is point centrality.

Degree Centrality

The stronger the influence of a specific node, the more neighbours it has. In human culture, we assume a person with many friends is in a better position than someone with less. A person like this can operate as an influencer and play an essential role in a social network. This concept gives rise to degree centrality, which refers to the degree of a particular node in a graph representing a social network.

Each vertex's relevance is determined by calculating the total number of its neighbours (known as the vertex's degree) and dividing it by the sum of the degrees of all the vertices in the graph. As a result, a vertex's degree centrality is:

where is the degree of a vertex and , and is equal to the total of all the degrees of all the vertices of . As a result, the more neighbours a vertex has, the more important it is thought to be.

Closeness Centrality

Closeness centrality assigns a value to each node based on its "closeness" to all other nodes in the network. This metric computes the shortest pathways connecting all nodes and then provides a score to each node based on the sum of its shortest paths. Now we can identify individuals who have the best positions to affect the entire network in the shortest amount of time.

Nodes that can reach other nodes via short paths or "more reachable" by other nodes via short routes have a higher ranking. These nodes are "central" to the network because they can reach the whole network faster than non-central nodes. This structural advantage translates into power, giving rise to the concept of closeness centrality. It is the average distance between a specific starting node and the rest of the network's nodes.

Betweenness Centrality

The betweenness centrality is a relative measure of closeness centrality in terms of prioritising shortest paths. It calculates the fraction of shortest paths that include our studied node. As a result, a node with a high betweenness centrality may significantly influence information moving between other nodes. As a result, they are an essential aspect of your network because eliminating them will break links between vertices (nodes) in your graph.

Where = total number of shortest paths from node ‘s’ to node ‘t.’

= a number of those paths that pass through ‘v.’

Eigenvector Centrality

Eigenvector centrality calculates a node's importance while taking into account its neighbours. It calculates the node degree and counts the number of links between its connections (neighbours). It makes use of the adjacency matrix's decomposition. The 'ith' entry of the A matrix eigenvector with the largest eigenvalue is the Eigen centrality for each node ‘i’.

Pagerank centrality

When the Google founders were thinking about quantifying the value of web pages using the web's hyperlink network structure, they came up with the page rank. The primary distinction between PageRank and EigenCentrality is that PageRank considers link direction. The amount of incoming links (the 'indegree') allocated to each node in a network determines its score. These linkages are also weighted based on the originating node's relative score.

( When calculating page rank centrality, a damping factor to control the effect of neighbours on your node while determining its importance. )

PageRank's mathematics is universal, and any graph or network can use this measure for further analysis. PageRank is now widely used in bibliometrics, social and information network analysis, link prediction, and recommendation. It has extensive application in biology, chemistry, neuroscience, physics, and systems analysis of road networks.

FAQs

1. What are real-life applications of centrality measures?
   Centrality measurements have real-life applications in various fields:
   →Air Transportation Networks
   →Biological Networks
   →Social Networks
   →Citation Networks
    
2. How are centrality measures used in network analysis?
   A network is a collection of components that are closely related. It could be individuals, cities, or anything else relevant. We can depict their interconnection in the form of networks, which are diagrammatic representations of their relationships.
    
3. What is PageRank? Why is the PageRank centrality measure popular?
   PageRank centrality measure is a variation of the Eigen Centrality measure that assigns a score to nodes based on their connections and the connections of their relationships. PageRank is different from other measures because it considers link direction and weight, implying that links can only convey influence in one way and in varying amounts.
   
   PageRank is one of the original Google search engine ranking algorithms (the 'Page' part of the name derives from its originator and Google founder, Larry Page). PageRank is helpful for understanding citations and authority because it considers direction and link weight.
    
4. When should you use which measure of centrality?
   You should select a centrality measure that fits your research case. If you want to go even further, you can combine other centrality measures into a single general centrality measure that satisfies your problem requirements.

Key Takeaways

This article covers a few basic graph theory concepts required for learning centrality measurement. We discussed four basic centrality measures: Degree centrality, closeness centrality, betweenness centrality, Eigenvector centrality and PageRank centrality.

Centrality measures assign a scalar score to each node, which helps interpret and analyse graphs. It helps to compare the relevance and criticality of nodes in your network.

Check out this problem - Matrix Median

We hope this blog has cleared all basic concepts regarding centrality measures in graph theory. If you want to learn more, check out our articles on ‘Introduction to Graphs’ and ‘Graph Theory.’ Please upvote our blog to assist other ninjas in their skill development.

Go to our practice platform Coding Ninjas Studio to practice top problems, take mock tests, read interview experiences, etc.

Happy Reading!