**WHAT IS GRAPH THEORY AND NETWORK ANALYSIS**Graph Theory is the mathematical study of the properties and applications of graphs. Graphs are mathematical structures used to model pairwise relations between objects. Graphs are also referred to as networks and contain a set of vertices/nodes/points connected by edges/links/lines.

Graph Theory can be applied to Network Analysis, Link Analysis and Social Network Analysis. These types of analysis borrow notations from Graph Theory and are focused on investigating social structures represented as networks, by applying a variety of mathematical, computational and statistical techniques.

HISTORY OF GRAPH THEORYHISTORY OF GRAPH THEORY

Graph Theory was first introduced and studied in 1736 by Leonhard Euler who was interested in solving the Konigsberg Bridge Problem. Konigsberg was a city in Prussia, Russia with the river Pregel flowing through it creating two islands. The city and islands were connected by seven bridges. The goal of the Konigsberg Bridge Problem was to devise a walk through the city that would cross each of the 7 bridges once and only once with no doubling back, ensuring that you ended where you started.

Leonhard Euler's work with Graph Theory was used to prove that the Konigsberg Bridge Problem was unsolvable. More notable names in the evolution and growth of Graph Theory are A.F Mobius (1840), Gustav Kirchhoff (1845), H.Dudeney (1913) and Heinrich (1969), among others.

NETWORKXNETWORKX

One way of utilizing Graph Theory in Network Analysis is by using a powerful python library called NetworkX. NetworkX is a python language software package and an open-source tool for the creation, manipulation and study of the structure, dynamics and functions of complex networks.

EXAMPLE APPLICATION OF NETWORK ANALYSIS USING GRAPH THEORY - AIRPORT DATAEXAMPLE APPLICATION OF NETWORK ANALYSIS USING GRAPH THEORY - AIRPORT DATA

The following python code will provide an in depth illustration of how Graph Theory can be used in Network Analysis. It will be applied to Airport Data where the nodes are Airport Abbreviations and the edges represent the Distance between those Airports.

**STEP 1 - IMPORT LIBRARIES**

**STEP 2 - DEFINE FUNCTIONS**

**STEP 3 - READ THE AIRPORT DATASET**

**STEP 4 - PREPROCESS THE DATASET**

**STEP 5 - GENERATE UNDIRECTED GRAPH**

**STEP 6 - CALCULATE THE DEGREE OF EACH NODE**

**STEP 7 - CALCULATE THE DEGREE CENTRALITY OF EACH NODE**

**STEP 8 - CALCULATE THE CLOSENESS CENTRALITY OF EACH NODE**

**STEP 9 - CALCULATE THE BETWEENNESS CENTRALITY OF EACH NODE**

**STEP 10 - CALCULATE THE EIGENVALUE CENTRALITY OF EACH NODE**

**STEP 11 - CALCULATE THE PAGERANK OF EACH NODE**

**STEP 12 - CALCULATE THE NETWORK DENSITY**

**STEP 13 - CALCULATE THE NETWORK ECCENTRICITY, DIAMETER AND RADIUS**

**STEP 14 - CALCULATE THE NETWORK TRANSITIVITY**

**STEP 15 - CALCULATE THE NETWORK ASSORTATIVITY**

**STEP 16 - CALCULATE THE AVERAGE SHORTEST PATH OF THE NETWORK**

**STEP 17 - CONNECTED COMPONENTS**____

**STEP 18 - CENTER AND PERIPHERY OF GRAPH**

**STEP 19 - DEGREE DISTRIBUTION AND HISTOGRAM**

**STEP 20 - DRAW THE ENTIRE GRAPH**

**STEP 21 - EGO-CENTRIC ANALYSIS AT A PARTICULAR NODE**__NetworkX is a powerful python library that can be used to experiment with Graph Theory and Network Analysis. It is a strong tool for studying the connections between nodes and can be used to derive statistics that pull out useful information about the structure, distribution and dynamic of a Graph.__

**CONCLUSION**