Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Graph Theory: Introduction
2.1.
What is a Graph?
2.2.
Mathematical representation of the graph
2.3.
A simple tool to analyse Graphs: Adjacency matrix
3.
Graph Theory: Centrality Measures
3.1.
Degree Centrality
3.2.
Closeness Centrality
3.3.
Betweenness Centrality
3.4.
Eigenvector Centrality
3.5.
Pagerank centrality
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Centrality Measure in Graph Theory

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

One of the essential aspects of Graph Theory is that it offers a concept of how objects can be related through nodes and edges. One of its main applications is comprehending networks and applying graph theory to complex networks. The insights it reveals may appear more magical than math. For example, Facebook and other social networks employ a graph structure to model users and their connections with their friends. In this article, we are going to learn different centrality measures and a few basics of graph theory.

Graph Theory: Introduction

Before we learn different centrality measures, we need basic ideas on graph theory and relevant concepts. So, we cover all the essential topics below.

What is a Graph?

A graph is a diagram made up of points and lines which connect the points. It has at least one line linking a pair of vertices, but no vertex connects itself. Understanding the notion of graphs in graph theory involves fundamental terms such as point, line, vertex, edge, degree of vertices, characteristics of graphs, etc.

Consider the following graph.

 

(an example of a graph with six nodes and eight edges)

A graph has two components:

  1. A node or a vertex.
  2. An edge E, also known as an ordered pair, links two nodes u,v; and the unique pair(u,v) identifies them.

Mathematical representation of the graph

A graph can be a very complex structure sometimes. It will be tough to analyse such graph structures visually. Thus, we need to build mathematical formulations to understand and analyse the graph.

We begin with the definition of the graph as a mathematical entity. A graph is defined by its set of nodes and set of edges. So, ‘G’ is defined as:

(The mathematical representation of a graph)

The set of nodes in our graph is denoted by ‘N’, while ‘E’ represents the set of edges. We also define the norm of our graph as the number of nodes.

A simple tool to analyse Graphs: Adjacency matrix

We can't merely evaluate graphs based on their geometrical shape; we need tools that encapsulate the information in our graphs while also making mathematical analysis simple.

The adjacency matrix represents a binary 2d array n*n, where n specifies the number of nodes. Each value can be either ‘1’ if the two nodes are linked or ‘0’ otherwise.

(Adjacency matrix example)

In the above example, we have created a matrix ‘A’ from the graph. The respective cell value is ‘1’ if the two nodes are connected or ‘0’ otherwise.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 centralitycloseness 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!

 

Live masterclass