## 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:

- A
**node**or a**vertex**. - 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.